在计算机科学中，算法的时间复杂度（Time complexity）是一个函数，它定性描述该算法的运行时间。当 n 很大时，公式中的低阶、常量、系数不能左右增长趋势，都可以忽略。

时间复杂度：随着自变量的增长，算法所需时间的增长情况。

常见的时间复杂度

运行时间 名称 英文名称
O(1) 常数时间 Constant time
O(log n) 对数时间 Logarithmic time
O(n) 线性时间 Linear time
O(n log n) 线性对数时间 linearithmic time
O(n^2) 平方时间 N square time
O(n^3) 次方时间 N cubic time
O(2^n) 指数时间 Exponential time
O(n!) 阶乘时间 Factorial

以上时间复杂度的量级依次递增。

我们在计算时间复杂度的时候，取其中最大的量级。当我们代码的时间复杂度有 O(n) 和 O(n^2) 的时候，那么时间复杂度就为 O(n^2)。总的时间复杂度等于量级最大的时间复杂度。

一些案例

O(1)

一般情况下，只要算法中不存在循环、递归语句，其时间复杂度是 O(1）

int n = 1000;
System.out.println("Hello, World " + n);
System.out.println("So... " + n);

O(N)

for (int i = 1; i <= n; i++) {
  System.out.println("Hello, " + n);
}

O(log n)

对数阶时间复杂度非常常见，同时也是最难分析的一种。

for (int i = 1; i <= n; i = i * 2) {
  System.out.println("Hello, " + n);
}

从代码中，变量 i 的取值就是一个等比数列。20 21 22…2k…2x = n。求解 x 等到的值：x = log2n，所以上面代码的时间复杂度 O(log2n)。

for (int i = 1; i <=n; i = i * 3) {
  System.out.println(n);
}

同理分析可得，上面代码的时间复杂度为 O(log3n)。

对数之间可以相互之间转换的，log3n 可以等于 log32 * log2n，所以我们可以忽略系数。而在对数阶的时间复杂度表示方法里，我们忽略对数的“底”，统一表示为 O(log n)。

O(n log n)

O(n log n) 是一种非常常见的算法时间复杂度，归并排序，快速排序的时间复杂度都是 O(n log n)。

O(N^2)

for (int i = 1; i <= n; i++) {
  for (int j = 1; j <= n; j++) {
    System.out.println("Hello, " + n);
  }
}

O(2^n)

int fib(int n) {
  if (n < 2) return n;
  return fib(n - 1) + fib(n -2);
}

几个概念

最好情况时间复杂度

最好情况时间复杂度(best case time complexity)，就是在最理想的情况下，执行这段代码的时间复杂度。

// n 表示数组 array 的长度
int find(int[] array, int n, inx x) {
  int pos = -1;
  for (int i = 0; i < n; i++) {
    if (array[i] == x) {
      pos = i;
      break;
    }
  }
  return pos;
}

在这段代码下，最理想的情况下，要查找的变量 x 刚好是数组的第一个元素，这个情况下对应的时间复杂度就是最好的情况时间复杂度。

最坏情况时间复杂度

最坏情况时间复杂度(worst case time complexity)，就是在最糟糕的情况下，执行这段代码的时间复杂度。

在上面的例子中，如果数组中没有要查找的变量 x，我们需要把整个数组都遍历一遍，这个情况下对应的时间复杂度就是最坏情况时间复杂度。

平均情况时间复杂度

平均情况时间复杂度(average case time complexity)，为了更好表示平均情况下的复杂度。

在上面的例子中，有 n + 1 种情况：在数组的 0 ～ n - 1 位置中和不在数组中。我们把每种情况下，查找需要遍历的元素的个数累加起来，然后再除以 n + 1，就可以得到需要遍历的元素个数的平均值。即：

1 + 2 + 3 + ... + n + n       n(n + 1) + 2n      n(n + 3)
------------------------ = ------------------ = -----------
       n + 1                   2 * (n + 1)       2(n + 1)

省略掉系数，低阶，常量，可以得到平均时间复杂度就是 O(n)。

这种推论是最大的问题就是，没有将各种情况发生的概率考虑进去，我们假设 x 在数组和不在数组中的概率均为 1/2。那么计算公式变成了

(1 + 2 + 3 + ... + n) * 1/2n + n * 1/2 = (3n + 1) / 4

去掉系数，低阶和常量，平均时间复杂度还是 O(n)。我们将这个值称为加权平均值，也叫期望值。

均摊时间复杂度

均摊时间复杂度(amortized time complexity)

空间复杂度

空间复杂度全称是渐进空间复杂度（asymptotic space complexity），表示算法的存储空间与数据的规模之间的增长关系。

常见的空间复杂度有 O(1)，O(n)，O(n2，而像 O(log n)，O(n log n) 这样的对数阶复杂度平时用不到。

思考题

  • 二叉树遍历-前序，中序，后序：时间复杂度是多少？
  • 图的遍历：时间复杂度是多少？
  • 搜索算法：DFS，BFS 时间复杂度是多少？
  • 二分查找：时间复杂度是多少？

参考链接