数据结构和算法本身就是解决"快"和"省"的问题，即如何让代码运行的更快，让代码更省存储空间。复杂度分析，是整个算法学习的精髓，只要掌握了它，数据结构和算法的内容基本上就掌握了一半。
为什么需要复杂度分析？
- 测试结果非常依赖环境
- 测试结果受数据规模的影响很大
所以，我们需要一个不用具体的测试数据来测试，就可以粗略地估计算法的执行效率的方法。
大O复杂度表示法
算法的执行效率，简单来说，就是算法的执行时间。那么如何在没有执行代码的情况下，用“肉眼”来判断一段代码的的执行时间呢？我们来看看这段代码：
int cal(int n) {
int sum = 0;
int i = 1;
for (; i <= n; ++i) {
sum = sum + i;
}
return sum;
}
假设每行代码对应的执行时间相同，为1个unit_time。第2，3行代码运行了一次，各用1个unit_time的执行时间，第4，5行运行了n次，则用了n个unit_time，所以这段代码的总执行时间为（2n + 2）个unit_time。可以看出来，所有代码的执行时间T(n)与每行代码的执行次数成正比。
同理，我们看下面一段代码：
int 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;
}
}
}
第2，3，4行执行一遍，每行需要1个unit_time，第5，6行执行了n遍，需要2nunit_time个执行时间，第7，8行执行了n² 遍，需要2n² unit_time个执行时间。所有代码的执行时间为(2n² +2n+3 )个unit_time执行时间。
由此我们可以看出，所有代码的执行时间T(n)与每行代码的执行次数n成正比。**我们总结为一个公式：
T(n)为所有代码的执行时间，n为数据规模大小，f(n)表示所有代码执行的总次数，O表示执行时间T(n)与f(n)成正比。所以第一个例子和第二个例子，我们分别用T(n) = O(2n + 2), T(n) = O(2n² +2n+3)来表示。
我们想象一下如果n很大的时候，2n² +2n+3 中，2n和3相对2n² 可以忽略不计，所以一般来说直接记为T(n)=O(n)，T(n)=O(n²)。
时间复杂度分析
我们只关注循环次数最多的一段代码
加法法则：
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;
}
代码分为3部分，分别求sum_1，sum_2,sum_3。第1,2,3部分的时间复杂度分别为，O(1), O(n), O(n²)。综合这三段代码的时间复杂度，我们取其中最大的量级。所以，整段代码的时间复杂度就是O(n²)。也就是说：总的时间复杂度就等于量级最大的那段代码的时间复杂度。
我们抽象成公式：如果T1(n) = O(f(n)), T2(n) = O(g(n)), 那么T(n) = T1(n) + T2(n) = O(f(n)) + O(g(n)) = O(max( f(n), g(n) ))。
- 乘法法则
以「加法法则」为基础，我们抽象成公式：如果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) )。
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;
}
f()函数部分的时间复杂度为O(n), 在第4，5行中，调用了n次f()，所以整个call()函数的时间复杂度为T(n) = O(n * n) = O(n²)。
常见的时间复杂度
一般分为：「多项式量级」和「非多项式量级」。
「多项式量级」：常量阶O(1)， 对数阶O(logn), 线性阶O(n)， 线性对数阶O(nlogn)， 平方阶O(n²)，立方阶O(n³)...
「非多项式量级」：指数阶O(2*n), 阶乘阶O(n!)。
空间复杂度
前面说，时间复杂度表示，算法的执行时间和数据规模之间的增长关系。空间复杂度表示，算法的存储空间和数据规模之间的增长关系。
void print(int n) {
int i = 0;
int[] a = new int[n];
for (i; i <n; ++i) {
a[i] = i * i;
}
for (i = n-1; i >= 0; --i) {
print out a[i]
}
}
第2行申请了一个空间存储变量i，但是它是常量阶，跟数据规模n没有关系。第3行，申请了1个长度为n的int型数组，除此之外，其他代码没有占用存储空间。故这段代码的空间复杂度为O(n)。
