# 演算法 - 時間複雜度
###### tags: `Algorithm`

## 前言
1. 時間複雜度 : 用於描述，過某個定量之後，程式的時間和輸入量的相互成長。
2. 時間複雜度只關心『有幾行程式碼』，不太在意程式碼的執行時間，如下，if再cpu的執行可能大於cout，但，再時間複雜度的評估上，我們都認為一樣。

if(bool_test) // 一次
{
   cout<<"test";// 一次
}

3. 我們會用『漸進符號』成見時間複雜度，當然可以也會有濫用的時候，必須注意這些濫用。
4. 下面討論的時候，我們都用$f(n)$表示為演算法的時間函數，而$g(n)$為簡單函式，用於逼近演算法的時間函式。
## 一 . 大$Θ$符號
### (一) . 概念
1. 定義 : 用兩個相似的函數，去夾時間函數。
- 存在著**正數** $n_0, c_1, c_2$。
- 使的對所有 $n≧n_0$。
- 都滿足 $0≦c_1×g(n)≦f(n)≦c_2×g(n)$。
- 可以稱 $f(n)$的$Θ$為$g(n)$。
- 記成 $f(n)=Θ(g(n))$，即 $f(n)$的$Θ$為$g(n)$。

2. 例子 : 給定一個$f(n)=\dfrac{1}{2}n^2 +3n$求$Θ$。
- 目標 - 求出 : $0≦c_1×g(n)≦f(n)≦c_2×g(n)$。
- 先假設$g(n)$ : 經驗法則，取最高項，設$g(n)=n^2$。
- 帶入假設 : $0≦c_1×n^2≦\dfrac{1}{2}n^2 +3n≦c_2×n^2$。
- 同除$n^2(即g(n))$ : 得$0≦c_1≦\dfrac{1}{2}+3/n≦c_2$
- 找出是否存在正數$c_1,c_2$滿足上式。
- 若假設的$g(n)$下可以找出$c1,c2$使$f(n)$滿足$Θ$定義的話，表示假設成功。

3. 特性 :
- $Θ(g(n))$是一個函數集，非單一的一個$f(n)$的函數而已。
- 對多項式的時間函數$f(n)=\sum_{i=0}^{d} an×n^i$時間複雜度為$Θ(n^d)$。

### (二) . 使用注意
1. 難以放大或縮小 : $Θ(n^k)$不一定符合$Θ(n^(k-1))$或$Θ(n^(k+1))$。
- 取上例 : $f(n)=\dfrac{1}{2}n^2 +3n=Θ(n^2)$
- 先假設$g(n)$時設為$g(n)=n^3$
- 會得 : $0≦(c1×n)≦\dfrac{1}{2}+3/n≦(c_2×n)$。
- 找不出$n0$，使$n$大於$n0$時可以滿足上式。
- 假設過大 : 使的條件式必須夾在兩個會成長到無限的函式。
- 先假設$g(n)$時設為$g(n)=n$
- 同理可得 : $0≦c1≦(\dfrac{1}{2}n+3)≦c_2$。
- 假設過大 : 使的條件式會成長到無限的函式，又要符合定值的限制。

## 二 . 大O符號
### (一) . 概念
1. 定義 : 用一個相似的函數，去夾時間函數的上限。
- 存在著**正數** $n_0, c$。
- 使的對所有 $n≧n_0$。
- 都滿足 $0≦f(n)≦c×g(n)$。
- 可以稱 $f(n)$的$O$為 $g(n)$。
- 記成 $f(n)=Θ(g(n))$，即 $f(n)$的$O$為$g(n)$。
2. 特性 :
- 大$O$也是一個函數的集合，非單一的一個$f(n)$的函數而已。
- 對$f(n)=Θ(g(n))$下，可以得 : $f(n)=O(g(n))$。

### (二) . 使用的注意:
1. 大$O$ 通常用於描述一個演算法的最糟情形。
- 最糟情況 : 一個演算法可能出現使時間最大的情形。
2. 大$O$ **並沒有**特別定義要如何逼近原函式的時間函式。
- 因此我們通常可以說，對於**非負漸進**的時間函式，我們可以知道 : $O(n^k)$定符合$O(n^(k+1))$。
- 注意，對負漸進的函式則不一定。
## 三 . 大Ω符號
### (一) . 概念
1. 定義 : 用一個相似的函數，去夾時間函數的下限。
- 存在著**正數** $n_0, c$。
- 使的對所有 $n≧n_0$。
- 都滿足 $0≦c×g(n)≦f(n)$。
- 可以稱 $f(n)$的$Ω$為$g(n)$。
- 記成 $f(n)=Ω(g(n))$，即 $f(n)$的$Ω$為$g(n)$。
2. 特性 :
- 大$Ω$也是一個函數的集合，非單一的一個$f(n)$的函數而已。
- 定理 : $[f(n)=O(g(n))]∩[f(n)=Ω(g(n))]↔︎f(n)=Θ(g(n))$

### (二) . 使用的注意
1. 大$Ω$ 通常用於描述一個演算法的最佳情形。
- 最佳情況 : 一個演算法可能出現使時間最小的情形。
2. 其實用 大$Ω$描述一個演算法的最差時間也可以 :
- 排序演算法 : 最糟形況是為整個array為一個大到小的陣列。
- 我們可以用排序演算法的最糟形況為 $Ω(n^2)$意思為 : 最糟的形況不會低於一個 $c×n^2$。
## 四 . 漸進符號的運算
1. **匿名函式** : 若漸進符號存在不等式或等式，那他的腳色就是匿名函式。
- 例 : $n^2+n=n+Θ(n^2)$。
- 此時的意思就是說，有一個函式 $f(n)=Θ(n^2)$使的等式相等。
- 依此例可能是 $n^2$。
2. 當等式或不等式左右都有漸漸符號時
- 定理 : **若**等式左方有漸進符號，**則**右方必也要有。
- 通論 : **右方的漸進符號比左方的粗糙**。
- 例子 :若 $2n+Θ(n)$為等號左式下。
- 為了滿足 $Θ(n)$可能是任何函數。
- 右方必須為 $Θ(n^2)$。

3. 方程式的漸進符號的鏈結 :
- 例 : $2n^2+3n+1 ⊆ ?$。
- 可以推出 : $2n^2+3n+1=2n^2+Θ(n)$。
- 可以推出 : $2n^2+Θ(n)=Θ(n^2)$
- 可以用鏈結間接的求出時間函式的時間複雜度。

4. $\sum$ 的濫用
- 問 : $\sum_{i=0}^{n}O(i)$ 有幾個匿名函式?
- 答 : 其實只有一個，因展開得$O(1)+O(2)..+O(n)$。
- 大部分是常數，只有最終項$O(n)$是匿名函式。
## 五 . 其他漸進符號
### (一) . 小$o$符號
1. 定義 : 類似大$O$但嚴格了不少。
- 對所有正數 $c$，都存在至少一個正數$n0$。
- 使的 $n0≦n$ 下滿足 $0≦c×g(n)≦f(n)$。
- 可以稱 $f(n)$的$o$為$g(n)$。
- 記成 $f(n)=Ω(g(n))$，即 $f(n)$的$o$為$g(n)$
2. 例子 : $2n=o(n^2)$ , 但 $2n^2≠o(n^2)$ , 且$2n^2≠o(2n^2)$ 。
3. 特性 :
- 少了大 $O$ 符號沒定義如何逼近時間函式的缺點。
- 數學式定義 : $\lim_{n\to\infty}\dfrac{f(n)}{g(n)}=0$
- $f(n)為時間函數，g(n)為逼近函數$
### (二) . 小$w$符號
1. 定義 : 類似大$Ω$但嚴格了不少。
- 對所有正數 $c$，都存在至少一個正數$n0$。
- 使的 $n0≦n$ 下滿足 $0≦f(n)≦c×g(n)$。
- 可以稱 $f(n)$的$w$為$g(n)$。
- 記成 $f(n)=w(g(n))$，即 $f(n)$的$w$為$g(n)$
2. 例子 :
3. 特性 :
- 少了大 $Ω$ 符號沒定義如何逼近時間函式的缺點。
- 數學式定義 : $\lim_{n\to\infty}\dfrac{f(n)}{g(n)}=∞$
- $f(n)為時間函數，g(n)為逼近函數$