Time complexity & Space complexity

1 对题目的意思确认理解无误
2 想出所有的可能的解决办法,同时比较这些办法的时空复杂度
3 找出时空复杂度最优的方法
4 测试结果


时间复杂度和空间复杂度

Big O notation

七种常见复杂度

  • O(1):Constant Complexity 常数复杂度
  • O(log n):Logarithmic Complexity 对数复杂度
  • O(n):Linear Complexity 线性时间复杂度
  • O(n^2):N square Complexity 平方
  • O(n^3):N cubic Complexity 立方
  • O(2^n):Exponential Growth 指数
  • O(n!):Factorial 阶乘

只看高复杂度的运算,不需要关注常数系数O(3)、O(2)和O(1)是一样的


时间复杂度

O(n) 的情况

顺序执行两个循环的复杂度是O(2n)注意不考虑系数,所以也是O(n)

1
2
3
4
5
6
7
for (int i = 0; i < n; ++i){
cout << i << endl;
}

for (int i = 0; i < n; ++i){
cout << i << endl;
}

O(n^2) 的情况

1
2
3
4
5
for (int i = 0; i < n; ++i){
for (int j = 0; j < n; ++j){
cout << i << endl;
}
}

O(log(n)) 的情况

1
2
3
for (int i = 1; i < n; i = i * 2){
cout << i << endl;
}
  • 二分查找的复杂度就是O(log(n))

O(k^n) 的情况

O(k^n) 这里的k是一个常数,可以认为是2的n次方,3的n次方是一样的。

1
2
3
4
5
6
// 求斐波那契数列的第n项

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

  递归程序执行的时候计算复杂度,考虑递归语句总共执行了多少次,画出递归的执行顺序对应的树形结构即递归树。下图给出了求斐波那契数量n=6的情形。可以发现很多次的重复计算,导致算法的复杂度非常高,每个节点向下计算两次,以此类推就是2n2^n次。即复杂度为O(k^n)。

  • 二叉树前序遍历、中序遍历、后序遍历的复杂度都是O(n)。根据主定理,二叉树的时间复杂度线性于节点的总数,所以是O(n)

  • 图的遍历:时间复杂度同样也是O(n),n为节点的个数。

  • DBS和BFS都是O(n),n是搜索节点的总数

  • 针对于有序数列的二分查找法 O(log(n)),而有序的二维矩阵的算法二分查找 为O(n)


空间复杂度

  1. 数组的长度
  2. 递归的深度(特殊说明)
  • 一位数组O(n)
  • 二维数组O(n^2)
  • 递归的话,那么递归最深的深度就是空间复杂度。
  • 如果即有递归又有数组,那么最大值就是空间复杂度。

如果通过斐波那契数列来理解空间复杂度,由于这个问题的最大深度为n,所以其空间复杂度就为O(n)。
如果你开了一个长度为n的一维数组,那么复杂度就是O(n),二维数组O(n^2),…以此类推


CS中常见的时空复杂度

数据结构操作

数组排序算法

排序的最优算法的时间复杂度就是O(nlog(n))

图操作

堆操作

思考

  在不了解时空复杂度的概念的时候,我认为爬楼梯问题对应的递归解法就是一个比较不错的解法了,并没有考虑到有重复计算的问题,现在我知道了爬楼梯问题如果用递归来实现的话就会有很多重复的计算,而其优化方式也很容易,就是利用记忆缓存,复杂度就降为O(n)来减少重复计算。

  以后做LeetCode每道题的时候都要习惯性的对其时空复杂度进行计算,先从给的例子开始熟悉,避免计算错误。

刻意练习是很必要的

参考

https://www.zhihu.com/question/21387264
https://m.saikr.com/a/2692

Big things have small beginnings.