复杂度分析浅析
一、為什麼需要複雜度分析#
可能平常，都会通过统计、监控，来得到相关的性能数据，来评估性能。有人将这种平时使用的性能分析方式，称为：事后分析法。
但是事后分析法，虽然普遍存在，但其有一些缺陷：
- 测试结果非常依赖测试环境。
- 某种意义上这也很方便，但是面对不同的机器、不同的编译环境，同段代码可能会有不同的结果。
- 测试结果受测试规模的影响很大。
- 同段代码，在大规模和小规模下会有不一样的结果。
所以，能不能有一种方法，能让我们无视测试环境，在任意规模下都能较精确地分析出代码的性能呢？
自然是有的，那就是使用大 O 复杂度表示法运用时间复杂度和空间复杂度来分析代码
二、大 O 复杂度表示法#
大 O 表示法：算法的时间复杂度通常用大 $O$ 符号表述，定义为 $T (n) = O\big (f (n)\big)$。称函数 $T (n)$ 以 $f (n)$ 为界或者称 $T (n)$ 受限于 $f (n)$。 如果一个问题的规模是 n，解这一问题的某一算法所需要的时间为 $T (n)$。$T (n)$ 称为这一算法的 “时间复杂度”。当输入量 n 逐渐加大时，时间复杂度的极限情形称为算法的 “渐近时间复杂度”。—— 百度百科
时间复杂度#
时间复杂度：全称 “渐进时间复杂度”，表示算法的执行时间与数据规模之间的增长关系。
我们这里用一个公式来表示：
| $T(n)$ | $n$ | $f(n)$ | $O$ |
|---|---|---|---|
| 代码的执行时间 | 代码的规模 | 每行代码的执行次数 | $T (n)$ 与 $f (n)$ 成正比关系 |
为了更方便理解这个公式，我举一个例子：
#include <stdio.h>
int main(){
int c = 0;
for(int i=1; i<=n; ++i)
c += i;
return 0;
}
从 CPU 的角度来看，这段代码的每一行都执行着类似的操作：读数据 - 运算 - 写数据。尽管每行代码对应的 CPU 执行的个数、执行的时间都不一样，但是，我们这里只是粗略估计，所以可以假设每行代码执行的时间都一样，为 unit_time。在这个假设的基础之上，这段代码的总执行时间是多少呢？
第 3 行代码需要 1 个 unit_time 的执行时间，第 4、5 行都运行了 n 遍，所以需要 2n * unit_time 的执行时间，所以这段代码总的执行时间就是 (2n+1) * unit_time。可以看出来，所有代码的执行时间 T (n) 与每行代码的执行次数成正比。
时间复杂度的分析方法#
1、只关注循环次数最多的一段代码#
这里有一条目前我觉得很重要的推断：由于低阶、系数和常量均不影响规模大小，所以 $f (n)$ 取最高阶代表即可。
2、加法法则#
总复杂度等于量级最大的那段代码的复杂度
我们举一个例子：
#include <stdio.h>
int main(){
int x=0;
for(int i=1; i<=100; ++i)
x += i;
int y=0;
for(int i=1; i<=n; ++i)
x += i;
int z=0;
for(int i=1; i<=n; ++i){
for(int j=1; j<=n; ++j)
z += j;
}
printf("%d %d %d\n", x, y, z);
return 0;
}
在这个例子中，要求 x，y，z。我们分别求出每个部分的时间复杂度，然后取最高阶的作整段代码的复杂度。
求 x 的这段，它会循环 100 次。由于是常数，所以不作数。
求 y 的这段，它会循环 n 次。记 $O (n)$。
求 z 的这段，它会循环 $n^2$ 次。记 $O (n^2)$。
我们从中取最高阶 $O (n^2)$ 作为整段代码的复杂度。
所以将加法公式化作表达式就为：
3、乘法法则#
嵌套代码的复杂度等于嵌套内外代码复杂度的乘积
我们举个例子：
#include <stdio.h>
int f(int n);
int main(){
int x = 0;
for(int i=0;i<=n;++i)
x += f(i);
return 0;
}
int f(int n){
int y = 0;
for(int i=0;i<=n;++i)
y += i;
return y;
}
在这个例子中，如果我们把 $f ()$ 看作一个普通操作，那么第 6 行的时间复杂度就是 $T_1 (n)=O (n)$。但是 $f ()$ 是一个函数，它的时间复杂度为 $T_2 (n)=O (n)$，所以，这段代码的时间复杂度应该是，$T_总 = T_1 (n) * T_2 (n)=O (n*n)=O (n^2)$。
几种常见时间复杂度实例分析#
其中，我们可以将其分为两类：多项式量级和非多项式量级。非多项式量级只有两个：$O (2^n)$ 和 $O (n!)$。
我们把时间复杂度为非多项式量级的算法问题叫做 NP 问题。当数据规模 n 越来越大时，非多项式量级算法的执行时间会急剧增加，求解问题的执行时间会无限增长。所以，非多项式时间复杂度的算法其实是非常低效的算法。
1、$O (1)$—— 常量级时间复杂度#
- 这个‘1’只是一种表示方法。
只要代码的执行时间不随 n 的增大而增长，或者，一般情况下，只要算法中不存在循环语句、递归语句，即使有成千上万行的代码，其时间复杂度也是 $O (1)$
2、$O (\log n)$、$O (n\log n)$—— 对数阶时间复杂度#
- 可以把所有对数阶的时间复杂度都记作 $O (\log n)$，$O (n\log n)$ 同理。
根据换底公式, 对数之间是可以互相转换的，所以说，任意对数都可以转换成 $Cf (n)$，其中 $f (n)$ 为对数。而根据之间得到的结论，常数等不影响代码规模的可以忽略不计。所以在对数阶时间复杂度的表示方法里，我们忽略对数的 “底”，统一表示为 $O (\log n)$
3、$O (m+n)$、$O (m*n)$—— 两个数据规模的时间复杂度#
一般的，由两个数据的规模来决定的代码的复杂度，由于无法事先评估谁的量级大，所以我们在表示复杂度的时候，不能简单地利用加法法则，省略掉其中一个。所以，我们用 $O (m+n)$、$O (m*n)$ 来表示。
那么，在这种情况下，加法法则应该为：
而乘法法则不变。
空间复杂度分析#
空间复杂度，全称渐进空间复杂度，表示算法的存储空间与数据规模之间的增长关系
我们用一个例子来看一看。
#include <stdio.h>
int main(){
int a[n];
for(int i=0; i<=n; ++i)
a[i] = i * i;
for(int i=n-1; i>=0; --i)
pritntf("%d", a[i]);
return 0;
}
那么，分析这段代码，第三行申请了一个大小为 n 的 int 类型数组，除此之外，剩下的代码都没有占用更多的空间，所以整段代码的空间复杂度就是 $O (n)$。
三、內容小結#
複雜度也叫漸進複雜度，包括時間複雜度和空間複雜度，用來分析算法執行效率與數據規模之間的增長關係，可以粗略地表示，越高階複雜度的算法，執行效率越低。常見的複雜度並不多，從低階到高階有 $O (1)$、$O (\log n)$、$O (n)$、$O (n\log n)$、$O (n^2)$。
