算法时间复杂度类型解释

Question

我读到了算法的时间复杂度，但我不知道我是否理解...下面的所有示例都是用 C++ 创建的。如果我错了请告诉我：

O(1):

int k;
k = 0;

O(n):

for(int i=0; i<n; i++) {
   k[i] = i%10;
}

O(n^2):

for(int i=0; i<n; i++) {
   for(int j=0; j<n; j++) {
      k[j] = i%10;
   }
}

O(n^k)（k 是已知数 - 语句有 k）：

for(int i=0; i<n; i++) {
   for(int j=0; j<n; j++) {
      .......
      for(int f=0; f<n; f++) {
         k[j][f] = p%10;
      }
      .......
   }
}

什么是O(k^n)？什么是 O(log n) 和 O(n * log n)？请给我每个算法（代码）示例。
我上面的例子有错吗？

Answer 1

网上有很多解释，Google对"big O notation"。您可以在 https://rob-bell.net/2009/06/a-beginners-guide-to-big-o-notation/

找到简单的介绍

示例：

O(k^n):生成n个字符的所有单词
O (log n)：通过重复减半来搜索 n 个元素的排序列表
O (n log n)：用例如快速排序算法

Space 复杂度与时间复杂度无关。搜索列表不会花费 space，但会花费时间。您可以对任何函数使用 "Big O" 表示法，因此消耗时间作为 n 的函数，或者消耗 space 作为 n 的函数。

你所有的例子都是正确的。

Answer 2

1。 O(k^n)：列出所有长度为 n 的二进制字符串 ( O(2^n) )

O(logn): 二分查找是一个最简单的例子

O(nlogn): 快速排序、堆排序等排序算法....

你说得对
不，space复杂度与时间复杂度不同示例：如果您将数据存储到一个二维数组中，那么您的复杂度为 O(n^2) space 但您只需要一个 for 循环遍历 n 个元素，那么您的算法的时间为 O(n)复杂。注意：在我的例子中使用 O(n^2) 和 O(n) 并不完全正确，我们最好使用 theta(n^2) 和 theta(n)

希望对您有所帮助。

算法时间复杂度类型解释

Algorithm time complexity types explaining

c++

algorithm

complexity-theory

big-o

time-complexity