前章提到，为了提高代码质量，需要选择正确的数据结构与算法，就需考量代码的执行效率和资源消耗两个方面。
本章主要学习考量代码执行效率（时间）、资源消耗（空间）的方式方法。
事后分析法
首先，性能测试、时间统计、内存监控等方案可以直观的让我们看到时间与空间的使用情况，并且得到确切值。
但以上方案都有以下局限性：
- 1、测试结果依赖测试环境
随着测试环境的硬件不同，得到的测试结果差距也就越大。eg：i9 cpu 和 i3 cpu 执行同一段代码时，很明显i9所用的时间要小i3.
- 2、测试结果随数据规模的变化可能产出完全不一的结果
例如我们在做排序的时候，数据规模足够大快速排序优于插入排序；但如果数据规模很小，插入排序反倒会比快速排序要快（后面的章节会细讲）。
- 3、后滞性
我们只有在进行完测试后才能知道现在的算法是否优于之前的算法。
所以，有没有一种方法可以在不需要测试数据的情况下，就能 粗略估算 出当前代码的执行效率和资源消耗？
大O复杂度表示法
想必这段代码，大家都不陌生，求1+2+3+...+n的累加和。
我们开始尝试分析这段代码，先假设一个前提，代码的执行效率粗略的比作代码的执行时间，每行代码的执行完成的时间都一样，都占用一个单位时间，记作：unitTime.
那么，我们尝试以“肉眼”的形式来估算这段代码的执行时间，并在注释中标出每行代码执行时间：
int sum = 0; // 1 * unitTime（执行 1 次）
int i = 1; // 1 * unitTime（执行 1 次）
for (; i <= n; i++) { // n * unitTime（执行 n 次）
sum += i; // n * unitTime（执行 n 次）
}
执行总时间 = (1+1+n+n) * unitTime = (2+2n) * unitTime
如果用数学函数来表达这个公式：
- T(n) 表示 代码的执行总时间
- f(n) 表示代码的执行总次数
则：
f(n) = 2 +2n
T(n) = (2+2n) * unitTime = f(n) * unitTime
重点来了，这里引入一个复杂度分析概念：
当n取值趋近于无穷大时，f(n)的常数项和系数项相比于n的取值规模对整个函数的影响可以忽略不计，仅需关注函数的最大阶。
什么意思呢？拿上面的例子来说，n的取值无限大时，这段代码的执行时间也会成比的增长，反观常数项2、系数项2对整体的影响就小之又小，所以在估算复杂度时，我们往往省略影响小的部分，取影响最大的部分，则得到：
f(n)= 2+2n --> f(n) = n
这种分析方法，称之为“大O复杂度表示法”，有专门的公式来表示：
最终，这段累加和的示例代码，以大O复杂度表示法来表示:
T(n) = O(fn) = O( 2+2n) = O(n)
时间复杂度
通过上面的例子，我们已经计算出了累加和的代码时间复杂度就是：O(n)。
总结下时间复杂度概念：
时间复杂度 并不表示代码的实际执行时间，而是代码执行时间与数据规模发生增长的变化趋势，叫作 渐进时间复杂度，简称：时间复杂度。
复杂度分析
知道了什么是时间复杂度，下面介绍几种复杂度分析技巧：
- 1、执行次数最多的那段代码
还记得上面提到的复杂度分析概念吗？当n取值趋近于无穷大时，f(n)的常数项和系数项相比于n的取值规模对整个函数的影响可以忽略不计，我们仅关注函数的最大阶。
通过这个概念，分析一个算法时，我们只需关注被执行次数最多的那段代码，这段代码执行次数n的量级，就是这个它的时间复杂度。
int sum = 0; // 1 * unitTime（执行 1 次）
int i = 1; // 1 * unitTime（执行 1 次）
for (; i <= n; i++) { // n * unitTime（执行 n 次）
sum += i; // n * unitTime（执行 n 次）
}
累加和这个例子中，我们一眼看过去执行最多次的代码，就是for循环中的代码，并且执行次数随着n的改变而变化，所以它的时间复杂度就是：O(n)
再练习一个例子：
public int fun2(int n) {
int sum = 0; // 1 * unitTime
int i = 1; // 1 * unitTime
int j; // 1 * unitTime
for (; i <= n; i++) { // n * unitTime
j = 1; // n * unitTime
for (; j <= n; j++) { // n² * unitTime
sum = sum + i * j; // n² * unitTime
}
}
return sum;
}
我们还是标出每行代码的执行次数，会得到总次数为：
f(n)=3+2n+2n²
不过，我们知道了时间复杂度等于执行次数最多的那段代码n的量级，所以一眼就能看出它的时间复杂度是：O(n²）.
- 2、加法法则：总复杂度等于量级最大的那段代码复杂度
有时候，代码中出现多个时间复杂度的情况，例如：
public int fun3(int n) {
//1、第一段
int sum1 = 0;
int i = 1;
for (; i <= 100; i++) {
sum1 += i; // 100 * unitTime
}
//2、第二段
int sum2 = 0;
int j = 1;
for (; j <= n; j++) {
sum2 += j; // n * unitTime
}
//3、第三段
int sum3 = 0;
int k = 1;
int l;
for (; k <= n; k++) {
l = 1;
for (; l <= n; l++) {
sum3 = sum3 + i * j; // n² * unitTime
}
}
return sum1 + sum2 + sum3;
}
很明显，这里有三段代码的时间复杂度，我们分别为：
T1(n) = O(1)
T2(n) = O(n)
T3(n) = O(n²)
后面两段代码的时间复杂度根据执行次数最多的那段代码准则， 一眼可看出是O(n)和O(n²)；
第一个为什么是O(1)而不是O(100)，在这里说明下，前面概念提到过时间复杂度不是指代码的实际执行时间或次数，而是指两者之间的增长趋势，在这里面无论n如何增长，第一段代码的执行次数都是不会受到影响的，对于这种常量阶的时间复杂度，统统记为：O(1).
回归正题，上面这三段代码都有自己的时间复杂度，那整个算法的时间复杂度可以通过 加法法则：取最大阶 的方式获得：
T(n) = T1(n) + T2(n )+ T3(n) = max( O(1) , O(n) , O(n²) ) = O(n²)
- 3、乘法法则：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
根据描述可以看出这个法则适用于嵌套代码，那什么是嵌套代码？
其实fun2()的例子就是嵌套代码，只是我们一眼就看出第二层for循环里的代码执行次数为n²次，很多情况下代码并不能直观的让我们看到它的最大阶，例如这个例子的代码稍微改一下：
public int fun4(int n) {
int sum = 0;
int i = 1;
for (; i <= n; i++) {
sum = sum + fun5(n, i); // n * unitTime
}
return sum;
}
public int fun5(int n, int i) {
int sum = 0;
int j = 1;
for (; j <= n; j++) {
sum = sum + j * i; // n * unitTime
}
return sum;
}
我们只是把第二层循环放到了新的方法中，由于n在两个代码片段中，我们很难一眼看到n的最大阶，此时我们只需把嵌套内外代码都看成独立的代码片段，算出各自的时间复杂度后，做乘积即可：
T1(n) = O(n)
T2(n) = O(n)
T(n) = T1(n) * T2(n) = O(n) * O(n) = O(n*n) = O(n²)
以上就是常用的3种复杂度分析的方法，至于实际问题中使用哪种，只有多练习，熟能生巧。
常见的时间复杂度
虽然代码千差万别，但实际上常见的复杂度量级并不多。我们已经了解了3种常见的时间复杂度：
- 常量阶 O(1)
- 线性阶 O(n)
- 次方阶 O(n²)
既然我们嵌套两层n循环时间复杂度是O(n²)，三层则为O(n³),同理无论多少次方我们统称为次方阶。
除了这3种，还有：
- 对数阶 O(logn)
对数的概念还记得？（高中数学），比如：3² = 9 以对数的形式表示就是 2 = log9 ，读作：2是以3为底，9的对数；那么x = log
N，读作：x是以a为底N的对数。
知道了对数的基本概念后，什么样的代码是对数阶呢？
public void fun6(int n) {
int i = 1;
while (i <= n) {
i = i * 2; // ? * unitTime
}
}
也是一段很常见的代码，怎么证明它是对数阶呢？
很明显我们只要计算出
i = i * 2
这行代码的执行次数与n之间关系，就可得到它的时间复杂度
我们可以尝试给n带入一批测试数据，比如n=4时：
i=1 i = 1 * 2 = 2
i=2 i = 2 * 2 = 4
i=4 i = 4 * 2 = 8
n=10时：
i=1 i = 1 * 2 = 2
i=2 i = 2 * 2 = 4
i=4 i = 4 * 2 = 8
i=8 i = 8 * 2 = 16
我们会发现i的取值范围是个等比数列：2 2² 2³ ... 2的x次方 ，当2的x次方 > N 时停止循环 ， 那么我们就可以得到：f(n) = log2n.
通过换底公式我们可以继续推算： f(n) = logn = log
n / log
2 = log
n => logn
我们把对数形式的时间复杂度的底数都换为以10为底，那么就会得到logn除以某个对数常数 ，而大O复杂度表示法中我们忽略常数部分的影响，最终所有的对数复杂度都为： T(n) = O(logn)
- 线性对数阶 O(nlogn)
如果前面的对数阶已经了解，那么在对数阶的外层再加一层遍历n次，利用乘法法则它的时间复杂度便是：T(n) = O(n) * O(logn) = O(nlogn)，后续的归并排序，快速排序复杂度都是O(nlogn)，到对应章节时再细说。
- 指数阶(2的n次方) & 阶乘阶(n!)
这两种称之为非多项式量级，其它的称之为多项式量级。
非多项式算法，我们只需知道随着n的增大，算法执行时间会急剧增加，是一种非常低效的算法，实际开发中需避免出现这种代码。
- O(m+n)
这是一种特殊的时间复杂度表示形式，之前的示例代码都很理想，一个算法中只存在一个数据n在影响代码的执行时间，但往往我们代码会是这样的：
public int fun7(int n, int m) {
int sum1 = 0;
int i = 1;
for (; i < n; i++) {
sum1 = sum1 + i;
}
int sum2 = 0;
int j = 1;
for (; i < m; j++) {
sum2 = sum2 + j;
}
return sum1 + sum2;
}
出现了两个量级：T1(n) = O(n)、T2(m) = O(m)，这种情况下我们不能利用加法法则省略一个低阶量级（m、n的量级相同），所以它的时间复杂度：T(n) = T1(n) + T2（m）= O(n+m)
但如果是嵌套关系，乘法法则依旧是可用的，记作：O(m * n)
空间复杂度
前面长篇大论讲解时间复杂度，只要牢牢掌握它，空间复杂度相对简单多了，因为无论是空间复杂度分析，还是常见的空间复杂度，它们都是类似的。
重温下时间复杂度概念：时间复杂度并不表示代码的实际执行时间，而是代码执行时间与数据规模发生增长的变化趋势；
类比一下，总结出空间复杂度的概念：
空间复杂度也并不表示实际的内存存储大小，而是内存空间与数据规模增长的变化趋势。
写个简单例子就明白了：
public void fun8(int n) {
int[] arr = new int[n]; // n * unitSize
int i = 0; // 1 * unitSize
for (; i < n; i++) {
arr[i] = i;
}
}
分析方法跟之前是大致相同的，我们只关注内存趋势发生改变最大的代码，以它的量级作为空间复杂度，即：S(n)=O(n).
常见的空间复杂度
常见的空间复杂度一般有：
- O(1)
- O(n)
- O(n²)
像对数阶，线性对数阶基本都用不到。
空间复杂度的内容就不一一举例了，只要多加练习，真正理解了时间复杂度，空间复杂度自然迎刃而解。
小结
复杂度也称渐进复杂度，可分为时间复杂度和空间复杂度，使用大O表示法来表示；
可以粗略的认为，越高阶的复杂度算法，性能越低；
常见的复杂度由低到高：O(1)、O(logn)、O(n)、O(nlogn)、O(n²).
复杂度分析并不难，贵在练习！
