时空复杂度分析
1. 如何分析、统计算法的执行效率和资源消耗
前言：数据结构和算法本身解决的是“快”和“省”的问题，所以，执行效率是算法一个非常重要的考量指标。如何衡量编写的算法代码的执行效率，主要内容就是：时间、空间复杂度分析。
复杂度分析是整个算法学习的精髓，只要掌握了它，数据结构和算法的内容基本上就掌握了一半（仅供参考）。
1.1 为什么需要复杂度分析
- 测试结果非常依赖测试环境
- 测试结果受数据规模
结论：我们需要一个不用具体的测试数据来测试，就能粗略地估计算法地执行效率地方法。
1.2 大 O 复杂度表示法
定义：所有代码的执行时间T(n)与每行代码的执行次数n成正比。
公式：T(n) = O(f(n))
说明：T(n) 表示代码执行的时间；n 表示数据规模的大小；f(n) 表示每行代码执行的次数总和，因为这是一个公式，所以用 f(n) 来表示。公式中的 O，表示代码的执行时间 T(n) 与 f(n) 表达式成正比。
示例：T(n) = O(2n+2)、 T(n) = O(2n2+2n+3)，这就是大 O 时间复杂度表示法（2n2代表2乘以n的平方）。当n很大时，公式中的低阶、常量、系数三部分并不左右增长趋势，所以都可以忽略，我们只需记录一个最大量级即可：T(n) = O(n)； T(n) = O(n2)。
名称：大 O 时间复杂度表示代码执行时间随数据规模增长的变化趋势，也叫渐进时间复杂度，简称：时间复杂度。
1.3 时间复杂度分析
- 只关注循环中执行次数最多的一段代码
- 加法法则：总复杂度等于量级最大的那段代码的复杂度。抽象为公式为：如果 T1(n)=O(f(n))，T2(n)=O(g(n))；那么 T(n)=T1(n)+T2(n)=max(O(f(n)), O(g(n))) =O(max(f(n), g(n)))
- 乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积。抽象为公式为：如果 T1(n)=O(f(n))，T2(n)=O(g(n))；那么 T(n)=T1(n)*T2(n)=O(f(n))*O(g(n))=O(f(n)*g(n))
1.4 常见时间复杂度实例分析
上述常见时间复杂度量级，可以粗略地分为两类：多项式量级和非多项式量级。
多项式量级时间复杂度：比如O(1),O(log(n)),O(n^a)等，它的规模n出现在底数的位置；特点：随着数据规模的增长，算法的执行时间和空间占用统一呈多项式规律增长。
非多项式量级时间复杂度：比如指数阶O(2.^n)、阶乘阶O(n!）型复杂度，其复杂度计算机往往不能承受。特点：随着数据量n的增长，时间复杂度急剧增长，执行时间无限增加。
- O(1) 一般情况下，只要算法中不存在循环语句、递归语句，即使代码上万行，其时间复杂度也是O(1)
- O(logn)、O(nlogn) 在采用大 O 标记复杂度的时候，可以忽略系数，即 O(Cf(n)) = O(f(n))
- O(m+n)、O(m*n) 计算规则：T1(m) + T2(n) = O(f(m) + g(n))。乘法法则：T1(m)*T2(n) = O(f(m) * f(n))
1.5 空间复杂度分析
渐进空间复杂度：表示算法的存储空间与数据规模之间的增长关系。