---
# System prepended metadata

title: 時間複雜度 (Time Complexity)

---

# 時間複雜度 (Time Complexity)
### Big-O
#### 定義:某演算法時間函數的上限，最糟也不會超過的意思！
#### $f(n)=O(g(n))$ iff存在兩正數$C, n_0$使得$f(n)\le C \times g(n)$, for all $n>=n_0$
只要n大到某個程度(no)，就保證時間函數f(n)最多就長到g(n)
(n是執行次數)
![](https://i.imgur.com/EHvE6vH.png)

#### 例題1: $f(n)=3n+2$, 證明$f(n)=O(n)$
1. 先把$f(n)$最高次項的係數值+1設為C
    --> C=3+1=4
2. $3n+2\le 4n$
    --> $n\ge2$
    $n_0=2$
3. 結論: $f(n)=O(n)$ iff $C=4, n_0=2$, 使得$f(n)\le 4\times g(n)$, for all $n>=2$
#### 例題2: $f(n)=5n^2+3n+2$, 證明$f(n)=O(n^2)$
1. 先把$f(n)$最高次項的係數值+1設為C
    --> C=5+1=6
2. $5n^2+3n+2\le 6n^2$
    --> $n^2\ge3n+2$
    $n_0=4$ (代數字試)
3. 結論: $f(n)=O(n^2)$ iff $C=6, n_0=4$, 使得$f(n)\le 6\times g(n)$, for all $n>=4$

以例題1的$f(n)=3n+2$來說，它的Big-O是$O(n)$，但這只是一個最爛值，所以$O(n^2), O(n^3)$..etc都可以是它的Big-O。
因此為了使Big-O有意義，$f(n)=O(g(n))$的$g(n)$要越小越好。

### Omega
#### 定義:某演算法時間函數的下限，最好也不會低於此下限！
#### $f(n)=\Omega(g(n))$ iff存在兩正數$C, n_0$使得$f(n)\ge C \times g(n)$, for all $n>=n_0$
只要n大到某個程度(no)，就保證時間函數f(n)最好就長到g(n)，不會再低於g(n)
(n是執行次數)
![](https://i.imgur.com/mLnZGOG.png)

#### 例題1: $f(n)=3n+2$, 證明$f(n)=\Omega(n)$
1. 先把$f(n)$最高次項的係數值設為C
    --> C=3
2. $3n+2\ge 3n$
    --> $2\ge0$, 恆真所以$n_0$可以任選
    $n_0=1$
3. 結論: $f(n)=\Omega(n)$ iff $C=3, n_0=1$, 使得$f(n)\ge 3\times g(n)$, for all $n>=1$
#### 例題2: $f(n)=5n^2+3n-6$, 證明$f(n)=\Omega(n^2)$
1. 先把$f(n)$最高次項的係數值設為C
    --> C=5
2. $5n^2+3n-6\ge 5n^2$
    --> $3n-6\ge0$
    $n_0=2$
3. 結論: $f(n)=\Omega(n^2)$ iff $C=5, n_0=2$, 使得$f(n)\ge 5\times g(n)$, for all $n>=2$

再次以$f(n)=3n+2$來說，它的Omega是$\Omega(n)$，但$\Omega (1)$也可以是它的Omega。
因此為了使Omega有意義，$f(n)=\Omega(g(n))$的$g(n)$要越大越好。

## Theta
#### 定義:就是Big-O跟Omega的夾擊~
#### $f(n)=\theta(g(n))$ iff存在三正數$C_1, C_2$和$n_0$,
#### 使得$C_1\times g(n) \le f(n)\le C_2 \times g(n)$, for all $n>=n_0$
![](https://i.imgur.com/xhlQKNH.png)
#### 例題1: $f(n)=3n+2$, 證明$f(n)=\theta(n)$
$C_1\times g(n) \le \underline{f(n)\le C_2 \times g(n)}$
1. 先處理右半邊，把$f(n)$最高次項的係數值+1設為C2
    --> C=3+1=4
2. $3n+2\le 4n$
    --> $n\ge2$, $n_0$=2
    
$\underline{C_1\times g(n) \le f(n)}\le C_2 \times g(n)$

3. 再處理左半邊，把$f(n)$最高次項的係數值設為C1
   --> C=3
4. $3n+2\ge 3n$,
    --> $2\ge0$恆真, 所以$n_0任取$
5. 結論: $f(n)=\theta(n)$ iff $C_1=3, C_2=4, n_0=2$, 使得$3\times g(n) \le f(n)\le 4\times g(n)$, for all $n>=2$
![](https://i.imgur.com/s6t7snC.png)