複雜度分析淺析
一、為什麼需要複雜度分析#
可能平常，都会通过统计、监控，来得到相关的性能数据，来评估性能。有人将这种平时使用的性能分析方式，称为：事后分析法。
但是事后分析法，虽然普遍存在，但其有一些缺陷：
- 测试结果非常依赖测试环境。
- 某种意义上这也很方便，但是面对不同的机器、不同的编译环境，同段代码可能会有不同的结果。
- 测试结果受测试规模的影响很大。
- 同段代码，在大规模和小规模下会有不一样的结果。
所以，能不能有一种方法，能让我们无视测试环境，在任意规模下都能较精确地分析出代码的性能呢？
自然是有的，那就是使用大 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)$。
