時間複雜度分析

當我們在評估一個一段 code 的品質，時間與使用空間是一個很好的評估標準。好的 code 可以在較短的時間內達成任務，而比較差的則會花比較多時間。
然而，在不同時間、不同電腦環境下，程式執行起來的時間一定會有所差別。假設今天在兩組不同的 code 分別在不同的電腦執行相同任務，那們我們測出來的時間勢必會受到環境的影響。就算是在同一台電腦，也會因為時間點不同而產生差異。因此無法準確以時間去估計 code 的品質。
因此我們只能回歸到程式碼本身的執行步驟來評估其品質

步驟數量分析

考慮以下程式碼片段

int a; // 宣告整數變數 a
a = 5; // a 被賦值為 5
printf("%d", a); // 輸出 a

可以發現程式碼有

$3$ 個步驟，而且不管在什麼情況下，一定只會有三個步驟

---

如果加上一個迴圈使輸出執行

$10$ 次:

int a; // 宣告整數變數 a
int i; // 宣告整數變數 i
a = 5; // a 被賦值為 5
for (i = 0; i < 10; i++) // 迴圈 10 次
    printf("%d", a);

在這個 for 迴圈中:
一開始賦值

$i=0$，接下來反復判斷

$i$ 是否小於

$10$，並加上

$1$，然後輸出

$a$
因此程式碼總共

$3\times 10+1+3=34$ 個步驟

---

迴圈次數會隨著輸入數字大小不同而變化:

int a; // 宣告整數變數 a
int i; // 宣告整數變數 i
scanf("%d", &a); // 輸入 a
for (i = 0; i < a; i++) // 迴圈 a 次
    printf("%d", a);

在這個 for 迴圈中:
一開始賦值

$i=0$，接下來反復判斷

$i$ 是否小於

$a$，並加上

$1$，然後輸出

$a$
因此程式碼總共

$3a+4$ 個步驟

---

巢狀迴圈:

int a; // 宣告整數變數 a
int i; // 宣告整數變數 i
int j; // 宣告整數變數 j
scanf("%d", &a); // 輸入 a
for (i = 0; i < a; i++) // 迴圈 a 次
    for(j = 0; j < a; j++) // 迴圈 a 次
        printf("%d", a);

因此程式碼總共

$((3a+1)+2)\times a+5=3a^2+3a+5$ 個步驟

---

由上述幾個例子可以發現，步驟數量有可能因迴圈數而變成一個多項式函數

Big-O Notation

假設今天有兩個 code，其步驟數量分別為:

$n^2+4n+2$、

$7n^3$

可以發現一個問題: 在

$n=1$、兩者的步驟數量剛好皆為

$7$
在此之前綠線的步驟數皆小於紅線，在此之後綠線的步驟數皆大於紅線
那麼該如何描述兩著的大小關係呢?

---

定義

$f(n)=O(g(n))$ 若且為若存在正的常數

$c$ 與

$n_0$ 使

$f(n)\le c\cdot g(n),\mathrm{\forall }n\ge n_0$

舉例像是

$f(n)=n^2+4n+2$ ，絕對可以找到一個函數

$c\cdot g(n)=2\cdot n^2$ 使

$f(n)\le c\cdot g(n),\mathrm{\forall }n\ge 5$

如此一來，我們就可以說

$f(n)$ 為

$O(n^2)$，就是

$f(n)$ 的時間複雜度為

$n^2$

基本上，如果

$f(n)$ 的最大冪次是

$m$，則可稱

$f(n)$ 為

$O(n^m)$
口頭上可以說時間複雜度為

$n^m$

---

舉例說明

回到剛才的問題，由於

$n^2+4n+2$、

$7n^3$ 的的時間複雜度分別為

$O(n^2)$、

$O(n^3)$
因此紅的程式碼時間複雜度比綠的程式碼小，原因是因為在圖中某個點以後，紅必定小於綠

---

估算方法

根據微積分的觀念，在

$n$ 非常大的時候

$f(n)$ 只會受到最大的一項影響
因此在多數時候，可以直接找在

$f(n)$ 中最大的那一項去判斷

例

$1$:

$f(n)=n^3+2n^2+2$，則

$f(n)=O(n^3)$，因為當

$n$ 非常大時，

$n^3$ 最大

例

$2$:

$f(n)=n!+4n^{50}+8$，則

$f(n)=O(n!)$，因為當

$n$ 非常大時，

$n!$ 最大

常見時間複雜度

$O(1)$: 常數時間，通常沒有迴圈，或是迴圈數固定，要注意常數有時可能非常大

$O(n)$: 線性時間，通常就是遍歷資料一次

$O(n^2)$: 平方時間，通常就是開兩個迴圈，或是將一維資料拓展成二維

$O(n^3)$: 立方時間，不常見，但通常是在走訪三維空間

$O(logn)$: 對數時間，二分搜尋或是在某些資料結構 (heap、DSU 等) 都有可能出現

$O(n\cdot logn)$: 在很多排序法或是資料結構上會出現

$O(n!)$: 階乘時間，別用他

$O(n^n)$: 別用他

$O(\sqrt{n})$: 根號時間，在某些數論問題或是區間分塊 (莫隊演算法) 會出現

其他的時間複雜度估算方式

由於在 Big-O 所估計的是上限的概念，所以當然也有估算下限的方式(方法差不多)

• Big-Omega: 估算下限
• Big-Theta: 同時估算上限與下限

由於上述的三個方法都有一個問題，假設常數

$n_0$ 很大，大到其資料量遠所不及，根本不可能達到，那麼自然會失準。因此有 Amortized analysis 來更準確地去估計他們的量，其中就包含三種方法:

• Aggregate analysis: 總量估算
• Accounting method: 把每個步驟都當作存錢到存錢筒(?
• Potential method: 把每個步驟都當作存錢到銀行(這方法很玄)

小結

時間複雜度可以想像成是資料量與步驟數量之間的關係

其實如果說一段程式很輕易的就可以看出來哪個地方迴圈數最多，那幾乎就可以由此判斷時間複雜度。假如說有一個三層的巢狀迴圈，那麼就可以猜他是不是

$O(n^3)$雖然有時候不一定是

有時候 Big-O 裡面不一定是

$n$，在圖論問題中有可能是

$V$(節點) 或

$E$(邊)；在數論問題中，

$n$ 可能只是一個整數

總之，在估算之前，要先看清楚要估算哪些資料

---

參考資料

• Introduction to Algorithms, Fourth Edition

---

ShanC 程式競賽筆記
作者: ShanC
更新: 2024/9/27