算法的质量很大程度上取决于执行速度，也就是平时提到的性能，大O复杂度表示法可以在不运行算法情况下从代码分析的角度很准确的分析出算法的瓶颈。
- 下面有一段很简单的代码，我们用大O复杂度表示法，来分析下他的执行效率
1
2
3
4
5
6
7
8int cal(int n) {
int sum = 0;
int i = 1;
for (; i <= n; ++i) {
sum = sum + i;
}
return sum;
}
假设每一行的执行时间都一样，为：unit_time
观察上面的代码
第2、3行代码分别需要1个unit_time
第4、5行运行了n遍，所以需要2*n个unit_time
所以上面的代码总执行时间为T(n)=(2n+2)*unit_time
- 再看第二段代码：
1
2
3
4
5
6
7
8
9
10
11int cal(int n) {
int sum = 0;
int i = 1;
int j = 1;
for (; i <= n; ++i) {
j = 1;
for (; j <= n; ++j) {
sum = sum + i * j;
}
}
}
根据刚刚讲的逻辑，可以得出，此段代码的执行时间是
T(n) = (2n^2+2n+3)*unit_time
前人已经给我们总结了大O的公式
T(n)=O(f(n))
f(n) 表示每行代码执行的次数总和
所以可以得出
第一段代码的时间复杂度大O表示法为：O(2n+2)
第二段代码的时间复杂度大O表示法为：O(2n^2+2n+3)
在分析时间复杂度时我们只需要关注循环的那一段
所以可以简化为
第一段：O(n)，线性复杂度
第二段：O(n^2)，指数阶复杂度
不难看出，嵌套循环对性能的影响是巨大的，更别说3层和4层嵌套了。
我们在性能优化时，更多的应该去关注循环语句，将循环次数和层数降下来，性能自然就会变优
