Skip to main content

时间空间复杂度

  1. 时间复杂度 Big O
  2. 常用复杂度量级分析
  3. 空间复杂度 Big O

问题​

我们如何判断一个算法的好坏？如何对比不同的算法？

时间复杂度 Big O​

「大 0 表示法」算法的渐进时间复杂度

T(n) = O(f(n))

Big O 的计算是当一个问题量级增加的时候，我的时间 T 增长的趋势。
T(n) 代表代码执行时间的复杂度，f(n)代表代码执行的次数, O 代表正比例关系。

例子​

例子 1​

例子 2​

例子 3​

常用的时间复杂度量级​

O(1)​

O(n)​

O(logN)​

O(nlogN)​

O(n^2)​

O(nm)​

其他复杂度指标​

空间复杂度​

「空间复杂度」: 内存空间增长的趋势

常用的空间复杂度​

O(1), O(n), O(n^2)

O(1)​

O(n)​

O(n^2)​

2d array, 矩阵 matrix

总结​

「时间空间复杂度」 = 时间和空间增长的趋势

来源​