時間複雜度分析

# 時間複雜度分析當我們在評估一個一段 code 的品質，時間與使用空間是一個很好的評估標準。好的 code 可以在較短的時間內達成任務，而比較差的則會花比較多時間。然而，在不同時間、不同電腦環境下，程式執行起來的時間一定會有所差別。假設今天在兩組不同的 code 分別在不同的電腦執行相同任務，那們我們測出來的時間勢必會受到環境的影響。就算是在同一台電腦，也會因為時間點不同而產生差異。因此無法準確以時間去估計 code 的品質。因此我們只能回歸到程式碼本身的執行步驟來評估其品質 ## 步驟數量分析考慮以下程式碼片段 ```cpp int a; // 宣告整數變數 a a = 5; // a 被賦值為 5 printf("%d", a); // 輸出 a ``` 可以發現程式碼有 $3$ 個步驟，而且不管在什麼情況下，一定只會有三個步驟 --- 如果加上一個迴圈使輸出執行 $10$ 次: ```cpp 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$ 個步驟 --- 迴圈次數會隨著輸入數字大小不同而變化: ```cpp 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$ 個步驟 --- 巢狀迴圈: ```cpp 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$ <img src="https://hackmd.io/_uploads/S1DR-6m0R.png" style="margin: 0 auto; display: block; width: 400px"> 可以發現一個問題: 在 $n=1$、兩者的步驟數量剛好皆為 $7$ 在此之前綠線的步驟數皆小於紅線，在此之後綠線的步驟數皆大於紅線那麼該如何描述兩著的大小關係呢? --- ### 定義 $f(n)=O(g(n))$ 若且為若存在正的常數 $c$ 與 $n_0$ 使 $f(n)\leq c\cdot g(n), \forall n\geq n_0$ 舉例像是 $f(n)=n^2+4n+2$ ，絕對可以找到一個函數 $c\cdot g(n)=2\cdot n^2$ 使 $f(n)\leq c\cdot g(n), \forall n\geq 5$ 如此一來，我們就可以說 $f(n)$ 為 $O(n^2)$，就是 $f(n)$ 的時間複雜度為 $n^2$ <img src="https://hackmd.io/_uploads/r1vf8pXCA.png" style="margin: 0 auto; display: block; width: 300px"> **基本上，如果 $f(n)$ 的最大冪次是 $m$，則可稱 $f(n)$ 為 $O(n^m)$** **口頭上可以說時間複雜度為 $n^m$** --- ### 舉例說明回到剛才的問題，由於 $n^2+4n+2$、$7n^3$ 的的時間複雜度分別為 $O(n^2)$、$O(n^3)$ 因此紅的程式碼時間複雜度比綠的程式碼小，原因是因為在圖中某個點以後，紅必定小於綠 <img src="https://hackmd.io/_uploads/S1DR-6m0R.png" style="margin: 0 auto; display: block; width: 400px"> --- ### 估算方法根據微積分的觀念，在 $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(log ~n)$: 對數時間，二分搜尋或是在某些資料結構 (heap、DSU 等) 都有可能出現 $O(n\cdot log ~n)$: 在很多排序法或是資料結構上會出現 $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 程式競賽筆記](https://hackmd.io/@ShanC/B1ouGxqcC) > 作者: ShanC > 更新: 2024/9/27