全文内容主要源于极客大学的算法课，仅作为笔记使用。

学习计划

由于每天都需要写学习心得和作业，所以写此贴作为笔记。也希望可以帮助到有需要的同学。

1、时间复杂度

（1）时间复杂度的统计维度

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

（2）各时间复杂度的耗时曲线

从图中可以看出，当 n 小于 5 时，不同的时间复杂度耗时差不多。
当 n 增大时，不同时间复杂度算法耗时差距非常大。所以也就不难理解，大型公司对算法的要求越来越高，是因为当遇到大数据量处理时，不同的算法能力，需要的服务器成本和代码性能是有天壤之别的。

（3）算法面试题的四个套件

• 算法题的内容确认无误；
• 思考所有可能解决的办法；
• 比较这些方法的时间和空间复杂度；
• 找出最优的解决方案（时间复杂度最低，兼顾内容使用更少的）

（4）递归的时间复杂度分析

• 将递归的执行顺序画出树形结构，称为递归状态的递归树；
• 主定理计算时间复杂度

比如：斐波那契数列
Fib: 1, 1, 2, 3, 5, 8, 13, 21, 34...
方法定义：F(1)=1，F(2)=1, F(n)=F(n - 1)+F(n - 2)（n ≥ 3，n ∈ N*）

def fib(n: int):
    if n < 2: return n
    return fib(n-1) + fib(n-2)

绘制递归图，以 n=6 为例：

常用算法应用主定理：（记住如下算法对应公式，并尝试理解）

2、空间复杂度

空间复杂度和时间复杂度的情况类似，但是更加简单。

数组的长度

如果代码中开了数组，则数组的长度基本就是空间复杂度。
比如:

• 一维数组，数组长度等于元素个数，则空间复杂度就是 O(n)
• 二维数组，数组长度为 n^{2，则空间复杂度为 O(n2)}

递归深度

如果代码中有递归，那么递归最大深度，就是空间复杂度的最大值。如果递归里面又开了数组，那么两者中的最大值就是空间复杂度。

实战分析

详见 leetcode 的爬楼梯示例：爬楼梯题解

3、小结

• 常用工具配置
• 基本功和编程指法
• 常见的时间、空间复杂度分析 对于开发来说，掌握熟悉的工具和 TOP 用法，能节省开发中的工具使用效率。 对于顶级工程师来说，对自己代码的时间复杂度和空间复杂度了解，是必备技能。

总结

时间复杂度：假设入参为 n，程序运行的次数与 n 的关系，即为时间复杂度。
时间复杂度优化顺序：O(1) > O(log n) > O(n) > O(n²⁾ > O(n³⁾ > O(2ⁿ⁾ > O(n!)

空间复杂度：代码中数组的大小或递归深度的最大值。
空间复杂度优化顺序：O(1) > O(log n) > O(n) > O(n²⁾ > O(n³⁾ > O(2ⁿ⁾ > O(n!)

为什么复杂度对于代码来说如此重要？
从互联网公司成本来看：

• 硬件成本：时间复杂度低的代码，可以降低 CPU 压力，减少服务器的 CPU 成本；空间复杂度低的代码，可以降低内存占用，减少服务器的内存成本；
• 产品成本：时间复杂度和空间复杂度越低，程序执行时间越低和遇到的性能故障越少，产品的性能就会越好，越容易获取用户喜欢。
• 质量评估成本：对设计的算法性能有两种评测方法，一是运行耗时评估，成本高、不稳定、强依赖硬件，而就是时间复杂度和空间复杂度评估，成本低、准确性高。

参考资料：

• 如何理解算法时间复杂度的表示法
• 主定理