共计 4196 个字符，预计需要花费 11 分钟才能阅读完成。
数据结构与算法之美（一）
1. 复杂度分析
数据结构和算法本身解决的是“快”和“省”的问题，即让代码运行地更快，更省内存空间。
为什么需要复杂度分析：
需要一个不用具体测试数据来测试，就可以粗略地估计算法执行效率的方法。
int cal(int n) {
int sum = 0; //1
int i = 1; //1
for (; i <= n; ++i) {//n
sum = sum + i; //n
}
return sum;
}
首先看下上面的代码，执行的就是 1 - n 的累加操作，从 CPU 的角度来看，每一行执行的操作都是类似的：读数据 - 运算 - 写数据，我们把这个操作执行的时间定义为 unit_time（单位时间），在这个基础之上，估算整个代码需要执行多久（多少次这样的 unit_time）。不难看出，它执行的总时间是 T(n)=(2+2n)unit_time。
同样的在看到下面的代码：
int cal(int n) {
int sum = 0; //1
int i = 1; //1
int j = 1; //1
for (; i <= n; ++i) {//n
j = 1; //n
for (; j <= n; ++j) {//n*n
sum = sum + i * j; //n*n
}
}
}
同样，按照不难得出，这段代码的执行时间是 T(n)=(2n*n+2n+3)unit_time。
我们不必要知道 unit_time 的具体值是多少，从上面两次分析中可以得出一个规律，T(n) 与每行代码执行次数 n 成正比。我们用大 O（bigO）来表示这种关系。
于是有了第一个例子的 T(n)=O(2+2n)，第二个例子的 T(n)=O(2n*n+2n+3)，需要注意的是，大 O 时间复杂度表示的是代码执行时间随数据规模增长的变化趋势，而不是代码真正的执行时间，所以也叫它渐进时间复杂度，就是我们常说的时间复杂度。
通常，我们考虑时间复杂度是针对 n 很大的情况下，当 n 很大的时候，我们可以忽略掉 bigO 表达式中的常数项，低阶项以及系数，只考虑最高次项本身。就前面两段代码，他们的时间复杂度分别为 O(n) 和 O(n^2)。
时间复杂度分析：
对于时间复杂度分析，有以下几个比较实用的方法
1. 只关注循环执行次数最多（执行次数最多）的一段代码
那些常量级和低阶级的执行时间不考虑到总的时间复杂度中来。
2. 加法法则：总复杂度等于量级最大的那段代码的复杂度。
int cal(int n) {
//1
int sum_1 = 0;
int p = 1;
for (; p < 100; ++p) {
sum_1 = sum_1 + p;
}
//2
int sum_2 = 0;
int q = 1;
for (; q < n; ++q) {
sum_2 = sum_2 + q;
}
//3
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;
}
对于上面那段代码，分成三部分，第一部分的时间复杂度是常量级的（一段代码的执行次数只要它是一个已知的数它就是常量级的，不管这个数是 100,10000，10000000 亦或是更大），第二段代码的时间复杂度是 O(n)，第三段代码的时间复杂度是 O(n^2)，所以最后整段代码的最终时间复杂度就是 O(n^2)，因为当随着 n 增长越来越大的时候，对整个时间复杂度影响最大的是第三段代码而不是前面的。bigO 描述的也只是这种变化趋势而已。
时间复杂度分析的加法法则还可以用公式来描述：
T(n)=T1(n)+T2(n)=max(O(f(n)), O(g(n))) =O(max(f(n), g(n))).
3. 乘法法则：
嵌套代码的复杂度等于嵌套内外层代码复杂度的乘积。
T(n)=T1(n)T2(n)=O(f(n))O(g(n))=O(f(n)*g(n))
举个例子：
int cal(int n) {
int ret = 0;
int i = 1;
for (; i < n; ++i) {
ret = ret + f(i); //1
}
}
int f(int n) {
int sum = 0;
int i = 1;
for (; i < n; ++i) {
sum = sum + i; //2
}
return sum;
}
1 处代码的时间复杂度是 O(n)，调用到的 f(i) 函数的时间复杂度 2 也是 O(n)，整个代码就相当于嵌套循环一样，最终整个程序的时间复杂度就是 O(n^2)。
几种常见的时间复杂度分析：
多项式量级
非多项式量级
常量阶 O(1)
指数阶 O(2^n)
对数阶 O(logn)
阶乘阶 O(n!)
线性阶 O(n)
线性对数阶 O(nlogn)
平方阶 O(n^2)
立方阶 ……k 次方阶 ……
对于非多项式量级，当随着 n 的规模越来越大的时候，算法的执行时间会急剧增加，求解问题的时间会无限增长，对于这种低效的算法，直接跳过就行。
1.O(1)：
这表示常量级的时间复杂度，而不是说代码只执行了一次或者一行，只要某段代码的执行次数是一个已知数，那么它的时间复杂度就是 O(1)。
2.O(logn)，O(nlogn)
首先来看对数阶的例子
// 影响最大的代码执行时间 log2 N
i=1;
while (i <= n) {
i = i * 2;
}
// 影响最大的代码执行时间 log3 N
i=1;
while (i <= n) {
i = i * 3;
}
我们知道，对数之间是可以互相转换的，log3n 就等于 log3 2 log2n，所以 O(log3n) = O(C log2n)，其中 C =log3 2 是一个常量，在 bigO 表示法中可以忽视掉，故而所有存在这种成对数关系的时间复杂度中，均可以忽略掉底数，而最终记为 O(logn)。
而 O(nlogn) 则可以用乘法法则反推过来，它的情况就是，O(n) 嵌套 O(logn)。
3.O(m+n)，O(m*n)
这两种情况指的是，当代码的复杂度是由两个数据的规模来决定的时候，我们无法再像前面那样有一个明确的谁是量级最大的，所以我们需要将 m 和 n 都考虑进来。
例如下面的代码：
int cal(int m, int n) {
int sum_1 = 0;
int i = 1;
for (; i < m; ++i) {
sum_1 = sum_1 + i;
}
int sum_2 = 0;
int j = 1;
for (; j < n; ++j) {
sum_2 = sum_2 + j;
}
return sum_1 + sum_2;
}
上面的代码，时间复杂度是 O(m+n)，当确定了 m 和 n 谁是最高量级的时候，就可以归入到前面说到的情况了。而对于这种复杂度依赖于两个不确定的数据的规模情况，加法法则不再是取 max，而是要将他们统一纳入到 O 中，乘法法则可以继续有效。
空间复杂度分析：
看这段代码：
void print(int n) {
int i = 0; //O(1)
int[] a = new int[n]; //O(n)
for (i; i <n; ++i) {
a[i] = i * i;
}
for (i = n-1; i >= 0; –i) {
print out a[i]
}
}
上面的代码中，只有第 2,3 行申请了额外的内存空间，那么对于空间复杂度的分析也正是就这种申请了额外的存储空间的代码而言的。很明显，按照 bigO 表示法的意义，最终这段代码的空间复杂度是 O(n)。
对空间复杂度的分析基本上就上面的方法。
最好，最坏，平均，均摊时间复杂度：
为了引出这几个概念，先看下面的一段无须查找的代码：
// n 表示数组 array 的长度
int find(int[] array, int n, int x) {
int i = 0;
int pos = -1;
for (; i < n; ++i) {
if (array[i] == x) {
pos = i;
break; // 注意
}
}
return pos;
}
上面这段代码，去掉 break 和加上 break，对代码复杂度分析是完全不一样的，当没有 break 的时候，这段代码的时间复杂度就是 bigOn，但是当优化加上 break 之后，它不再是如此了。
可能说一次就找到了，可能说 10 次就找到，可能说 n 次就找打了，可能 n 次也找不到。
为了表示代码在不同情况下的不同时间复杂度，引入了最好，最坏，平均情况时间复杂度。而他们的含义也是见名知意的。拿上面的代码举例，最好情况就是一次找到，最坏就是需要对整个数据都进行遍历才行。
平均时间复杂度
那么对于平均时间复杂度而言，拿上面的查找代码为例，分析过程就是：对于 search key x 而言，它能出现的位置一共有 n + 1 种可能（前面的 n 种表示在这个数组中，而第 n + 1 种则是指 x 不在数组中），如果把需要每一种情况下需要遍历的元素累加，然后再除以 n +1，就可以得到求得结果（找到或者未找到）所需要遍历元素的平均值。
于是我们得到了这个公式：
公式中，累加了两次 n，一次是找到了，一次是未找到，最后得到的平均复杂度就是 O(n)。
上面虽然得到了正确的时间复杂度，但是过程却不一定正确，不妨这样想，1 次就找到和 100 次才找到，这两个时间的概率并不相等，后者的概率显然大于前者（因为随着查找次数增加，后面继续查找下去找打的概率就越大），所以上面的 n + 1 种情况并不等概率发生，如果把经过 m 次查找看做一个随机事件，我们还需要给它加上一个权值，这个权值就是经过 m 次查找找到的概率。
x 在不在数组中的概率都是 1 /2，而要查找的数据出现在 0 -（n-1）这 n 个位置上的概率也是相等的 1 /n，所以在 0 -（n-1）这 n 个位置上找到 x 的概率就是 1 /2n，那么经过 m 次查找可能得到结果的概率就是 m *1/2n。
所以我们得到了下面这个公式：
需要解释的一点是最后一个 n *1/2，这是 x 不在数组中的情况，概率是 1 /2，需要总共要遍历 n 个元素。最后把加权平均值相加，得到加权平均时间复杂度 O(n)。
而平均时间复杂度，就是用代码在所有情况下执行次数的加权平均值表示。
均摊时间复杂度
这实际上是一种特殊情况下的复杂度，举个例子，假设存在 n - 1 次常量级的操作，在第 n - 1 次之后又加上一次 O(n) 的操作，均摊分析的思路大致思路就是，像这种情况，我们可以把耗时多的操作均摊到耗时少的 n - 1 次操作上，均摊下来的时间复杂度就是均摊时间复杂度。
对于均摊时间复杂度，使用的情况比较少，总结下它的应用场景就是：
对一个数据结构进行连续的操作，其中大部分的操作时间复杂度都比较的低，之后个别情况下的复杂度较高，而且这一系列操作在时序上是前后连贯的，这个时候我们就可以将复杂度高的操作耗时平摊到复杂度低的操作上，而如果能够应用到均摊时间复杂度的场合，一般而言，均摊时间复杂度往往就是最好情况时间复杂度。
可以认为均摊时间复杂度是一种特殊的平均时间复杂度，对此我们不必花太大经历去区分他们，重点在于怎么去分析平均时间复杂度和均摊时间复杂度。
