全文内容主要源于极客大学的算法课，仅作为笔记使用。
学习计划
由于每天都需要写学习心得和作业，所以写此贴作为笔记。也希望可以帮助到有需要的同学。
1、时间复杂度
（1）时间复杂度的统计维度
O(1): Constant Complexity 常数复杂度
O(log n): Logarithmic Complexity 对数复杂度
O(n): Linear Complexity 线性时间复杂度
O(n2): N Square Complexity 平方
O(n3): N CubicComplexity 立方
O(2n): 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)
- 二维数组，数组长度为n2，则空间复杂度为O(n2)
递归深度
如果代码中有递归，那么递归最大深度，就是空间复杂度的最大值。如果递归里面又开了数组，那么两者中的最大值就是空间复杂度。
实战分析:
详见leetcode的爬楼梯示例：爬楼梯题解
3、小结
- 常用工具配置
- 基本功和编程指法
- 常见的时间、空间复杂度分析 对于开发来说，掌握熟悉的工具和TOP用法，能节省开发中的工具使用效率。 对于顶级工程师来说，对自己代码的时间复杂度和空间复杂度了解，是必备技能。
总结
时间复杂度： 假设入参为n，程序运行的次数与n的关系，即为时间复杂度。
时间复杂度优化顺序：O(1) > O(log n) > O(n) > O(n2) > O(n3) > O(2n) > O(n!)
空间复杂度： 代码中数组的大小或递归深度的最大值。
空间复杂度优化顺序：O(1) > O(log n) > O(n) > O(n2) > O(n3) > O(2n) > O(n!)
为什么复杂度对于代码来说如此重要？
从互联网公司成本来看：
- 硬件成本：时间复杂度低的代码，可以降低CPU压力，减少服务器的CPU成本；空间复杂度低的代码，可以降低内存占用，减少服务器的内存成本；
- 产品成本：时间复杂度和空间复杂度越低，程序执行时间越低和遇到的性能故障越少，产品的性能就会越好，越容易获取用户喜欢。
- 质量评估成本：对设计的算法性能有两种评测方法，一是运行耗时评估，成本高、不稳定、强依赖硬件，而就是时间复杂度和空间复杂度评估，成本低、准确性高。
网友评论