算法的复杂度分析
如果想要分析一个程序的性能，你可以尝试将程序运行，然后收集它的运行数据，就可以得到程序运行所需要的时间和内存。我们将这种分析方法称为事后统计法。
事后统计法是非常朴素的分析方法，但是也两点问题：
- 程序的运行需要依赖硬件环境，比如同一个程序在两台性能不一的电脑上的表现是不同的。
- 程序运行时间往往收到数据规模的影响，例如在排序算法中，快排是最优秀的算法，如果只使用几个数据进行排序，可能它的表现还不如冒泡排序，但是当使用上万个数据进行排序的时候，他们的性能差异就会显现。（这种差异可能不是十倍，而是百倍千倍）
由于这些问题，我们一般使用复杂度分析的方法分析一个算法的性能，这就是大O复杂度表示法
大O复杂度表示法：
大O时间复杂度表示法：
抛去计算机底层的影响，我们可以使用大O时间复杂度表示法来表示代码执行时间随数据规模增长的变化趋势，简称时间复杂度。
分析时间复杂度有三个比较使用的方法：
1.只关注循环执行次数最多的一段代码：
敲黑板：循环 和 最多
下面有一段代码：
int cal(int n) {
int sum = 0;
int i = 1;
for (; i <= n; ++i) {
sum = sum + i;
}
return sum;
}
上面的代码中，2、3行代码都是常量级的执行时间，和n无关，在复杂度分析中可以忽略。循环执行次数最多代码是 for 循环中的代码，它被执行了 n 次，所以总的时间复杂度是O（n）
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_2部分的代码的复杂度为O(n)，sum_3代码的复杂度为O(n2），根据加法法则，cal函数的复杂度为O(n2)
3.乘法法则：嵌套代码的复杂度等于嵌套内外代码的复杂度的乘积：
看下面的代码：
int cal(int n) {
int ret = 0;
int i = 1;
for (; i < n; ++i) {
ret = ret + f(i);
}
}
int f(int n) {
int sum = 0;
int i = 1;
for (; i < n; ++i) {
sum = sum + i;
}
return sum;
}
可以看到，在 cal 的 for 循环中嵌套了 f 函数。第一部分的 for 循环贡献了 n 的复杂度，而 f 函数也贡献了 n 的复杂度，根据乘法法则，cal的复杂度为 O(n2)。
大O空间复杂度表示法：
空间复杂度的定义和时间复杂度类似：表示算法需要的存储空间与数据规模之间的增长关系。
你只需要分析在算法中申请的存储空间即可，常见的空间复杂度有：O(1),O(n),O(n2)
最好、最坏、平均、均摊 时间复杂度
同一个算法在给定不同数据的情况下性能可能会出现很大的差异，例如：如果一个数组已经基本有序，那么使用快速排序则有O(n2)的时间复杂度，而最好的情况下复杂度为O(nlogn)。
基于上面的情况，我们引入了各种复杂度的度量：
- 最好情况时间复杂度：在最理想的情况下，执行这段代码的时间复杂度
- 最坏情况时间复杂度：在最糟糕的情况下，执行这段代码的时间复杂度
- 平均时间复杂度：根据概率论的理论，平均时间复杂度的值为代码执行的加权平均值，也就是它的期望值。所以你也可以将之称为加权平均时间复杂度。
- 均摊时间复杂度：你可以将其理解为一种特殊的平均时间复杂度：
先来看下面一段代码：
// array表示一个长度为n的数组
// 代码中的array.length就等于n
int[] array = new int[n];
int count = 0;
void insert(int val) {
if (count == array.length) {
int sum = 0;
for (int i = 0; i < array.length; ++i) {
sum = sum + array[i];
}
array[0] = sum;
count = 1;
}
array[count] = val;
++count;
}
你会发现，如果我们一直使用insert函数向数组array中添加数据，在没有到达n，只需要O(1)的时间复杂度，但是如果放入第n个数据，复杂度就会变为O(n)，这就出现了在执行过程中操作的复杂度不同的情况，针对这种情况，我摘取了下面一段话：
对一个数据结构进行一组连续操作中，大部分情况下时间复杂度都很低，只有个别情况下时间复杂度比较高，而且这些操作之间存在前后连贯的时序关系，这个时候，我们就可以将这一组操作放在一块儿分析，看是否能将较高时间复杂度那次操作的耗时，平摊到其他那些时间复杂度比较低的操作上。而且，在能够应用均摊时间复杂度分析的场合，一般均摊时间复杂度就等于最好情况时间复杂度。
注意：只有在最好、最坏、平均时间复杂度在量级上存在差异的时候，区分它们才有意义。
以上就是对算法的复杂度分析的全部内容。
