执行效率是算法优劣的度量指标，而执行效率又是通过时间、空间复杂度分析。
为什么需要复杂度分析？
将代码跑一遍，通过统计、监控，就能得到算法执行时间和占用的内存大小。-----这叫事后统计法
存在局限性：
1 . 测试结果依赖于测试环境
2 . 测试结果受测试数据的规模影响
如何能不用具体的测试数据，就可以粗略估计算法的执行效率呢？
大O复杂度表示法
-
首先看个栗子：
int cal(int n){ int sum = 0; int i = 1; for (; i <= n; ++i) { sum = sum + i; } return sum; }
CPU角度分析
这段代码每一行都执行着操作：读数据-运算-写数据。
每行代码对应的CPU执行个数和执行时间不同，但假设每行代码执行时间为 unit_time。
那么上面一段代码的执行时间应为： (2n+2) * unit_time
总结
所有代码的执行时间 T(n) 与每行代码的执行次数成正比。
-
按照这个思路分析下面一段代码的执行时间T(n)
1 int cal(int n) { 2 int sum = 0; 3 int i = 1; 4 int j = 1; 5 for (; i <= n; ++i) { 6 j = 1; 7 for (; j <= n; ++j) { 8 sum = sum + i * j; 9 } 10 } 11 }
分析过程
对于2,3,4行，执行每行需要1个unit_time；执行5,6行需要n个unit_time；执行7,8行需要n * n个unit_time
总的执行时间为 T(n) = (2n * n + 2n + 3)*unit_time
规律总结
通过以上两段代码的执行时间推导，得到规律：
所有代码的执行时间 T(n) 与每行代码的执行次数 n 成正比。
公式表示
T(n) = O(f(n))
其中，T(n)表示代码执行时间；n 表示数据规模的大小；f(n) 表示每行代码执行的次数总和； O 表示代码的执行时间 T(n) 与 f(n) 表达式成正比。
那么以上两个例子的大O表示应为：
T(n) = O(2n + 2) -----> T(n) = O(n)
T(n) = O(2n * n + 2n + 3) -----> T(n) = O(n * n)
注：公式中的低阶、常量、系数三部分并不决定增长趋势，因而可以忽略。
大O时间复杂度实际上并不具体表示代码真正的执行时间，而是表示代码执行时间随数据规模增长的变化趋势。
因而，也叫作渐进时间复杂度，简称时间复杂度。
如何分析时间复杂度
1、只关注循环执行次数最多的一段代码
2、加法法则
总复杂度等于量级最大的那段代码的复杂度
-
举个栗子：分析下面这段代码的时间复杂度
int cal(int n) { int sum_1 = 0; int p = 1; for (; p < 100; ++p) { sum_1 = sum_1 + p; } int sum_2 = 0; int q = 1; for (; q < n; ++q) { sum_2 = sum_2 + q; } int sum_3 = 0; int i = 1; int j = 1; for (; i <= n; ++i) { j = 1; for (; j <= n; ++j) { sum_3 = sum_3 + i * j; } } return sum_1 + sum_2 + sum_3; }
分析
代码是要分别求sum_1、sum_2、sum_3。那么算时间复杂度就分别求每一部分的时间复杂度，再放在一起，取量级最大的那个作为整段代码的时间复杂度。
- sum_1处：执行100次，与n无关；是常量执行时间
注：即使循环100000次，只要是一个已知数，与n无关，那么就是一个常量执行时间。
因为时间复杂度表示的是一个算法执行效率与数据规模增长的变化趋势，所以不管常量的执行时间多大，都可以忽略。因为其本身对增长趋势没有影响。
- sum_2处：
O(n) - sum_3处：
O(n*n)
根据方法2，整段代码的时间复杂度就等于O(n*n)
将规律抽象成公式
若 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))).
3、乘法法则
嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
公式
若
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)).
几种常见时间复杂度实例分析
注
O(1) < O(logn) < O(n) < O(nlogn) < O(n*n)
以上罗列的复杂度量级，可以粗略分为两类：多项式量级、非多项式量级（指数阶和阶乘阶）
将时间复杂度为非多项式量级的算法问题叫作NP问题。当数据规模增大时，非多项式时间复杂度的算法效率非常低。
重点关注常见的多项式时间复杂度
1 . O(1)
明确：O(1)是常量级时间复杂度的一种表示方法，并不是指只执行了一行代码。
一般情况下，只要算法中不存在循环语句、递归语句，即使有成千上万行的代码，其时间复杂度也是Ο(1)。
2 . O(logn)、O(nlogn)
最难分析的一种时间复杂度
最常见的例子：
1 i=1;
2 while (i <= n) {
3 i = i * 2;
//i = i * 3;
4 }
分析：变量i从1开始取，每循环一次就乘以2。变量i的取值就是一个等比数列： 2的x次方为n，求解x为多少。x=logn(以2为底)
若循环体内的代码改成 i = i * 3;那么时间复杂度为O(logn)(以3为底)
我们把所有对数阶的时间复杂度都记为O(logn)
因为：log3n 就等于 log32 * log2n，所以 O(log3n) = O(C * log2n)，其中 C=log32 是一个常量。
基于我们前面的一个理论：在采用大 O 标记复杂度的时候，可以忽略系数，即 O(C*f(n)) = O(f(n))。
如果一段代码的时间复杂度是 O(logn)，我们循环执行 n 遍，时间复杂度就是 O(nlogn) 。
O(nlogn) 也是一种非常常见的算法时间复杂度。比如，归并排序、快速排序的时间复杂度都是 O(nlogn)。
3 . O(m+n)、O(m*n)
代码的时间复杂度由两个数据的规模来决定。无法评估m和n谁的量级更大，所以在表示复杂度时，就不能简单利用加法法则，而忽略掉其中一个。
针对这种情况，原来的加法法则应改为 T1(m) + T2(n) = O(f(m) + g(n))；乘法法则继续有效 T1(m)*T2(n) = O(f(m) * f(n))。
空间复杂度分析
渐进空间复杂度，表示算法的存储空间与数据规模之间的增长关系。
我们常见的空间复杂度就是 O(1)、 O(n)、 O(n*n )，像 O(logn)、 O(nlogn) 这样的对数阶复杂度平时都用不到。
小结
