---
# System prepended metadata

title: 時間複雜度分析
tags: [內湖高中程式競賽]

---

# 時間複雜度分析
當我們在評估一個一段 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，其步驟數量分別為: <font color="red">$n^2+4n+2$</font>、<font color="green">$7n^3$</font>

<img src="https://hackmd.io/_uploads/S1DR-6m0R.png" style="margin: 0 auto; display: block; width: 400px">
<p><br></p>

可以發現一個問題: 在 $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">
<p><br></p>

**基本上，如果 $f(n)$ 的最大冪次是 $m$，則可稱 $f(n)$ 為 $O(n^m)$**
**口頭上可以說時間複雜度為 $n^m$**

---
### 舉例說明
回到剛才的問題，由於 <font color="red">$n^2+4n+2$</font>、<font color="green">$7n^3$</font> 的的時間複雜度分別為 <font color="red">$O(n^2)$</font>、<font color="green">$O(n^3)$</font>
因此<font color="red">紅</font>的程式碼時間複雜度比<font color="green">綠</font>的程式碼小，原因是因為在圖中某個點以後，<font color="red">紅</font>必定小於<font color="green">綠</font>

<img src="https://hackmd.io/_uploads/S1DR-6m0R.png" style="margin: 0 auto; display: block; width: 400px">
<p><br></p>

---
### 估算方法
根據微積分的觀念，在 $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