---
# System prepended metadata

title: <font size="6">演算法 </font><br />

---

# <font size="6">演算法 </font><br />

<br>

---

<br>

## <font size="6">[基本定義](https://zh.wikipedia.org/wiki/%E7%AE%97%E6%B3%95)</font><br />
<font size="5"> 定義: 高德納(Donald Ervin Knuth) 在他的曠世巨作－《電腦程式設計藝術》裡已經幫我們整裡、歸納出一個==演算法需要俱備的五個特性==：[參考資料](https://jason-chen-1992.weebly.com/home/-whats-algorithm) </font><br />
<br>
><font color="#000066" size="5"> **1. 輸入：** 一個演算法必須有零個或以上的輸入。==$(input: \ \ge\ 0)$==</font><br />

><font color="#000066" size="5">**2. 輸出：** 一個演算法應有一個或以上輸出，輸出是演算法計算的結果。==$(output: \ \ge\ 1)$==</font><br /> 


><font color="#000066" size="5">**3. 明確性：** ==演算法的描述必須明確無歧義==，以保證演算法的實際執行結果是精確地符合要求或期望，通常要求實際執行結果是確定的。</font><br />

><font color="#000066" size="5">**4. 有限性:** 依據圖靈的定義，一個演算法是能夠被任何圖靈完備系統類比的一串運算，而圖靈機只有有限個狀態、有限個輸入符號和有限個轉移函式(指令)。而一些定義更規定==演算法必須在有限個步驟內完成任務。==</font><br />
 
><font color="#000066" size="5">**5. 有效性：** 又稱可行性。==演算法中描述的操作都是可以通過已經實現，且容易的基本運算執行有限次來實現。==
</font><br /> 


---

<br>

## <font size="6">[時間複雜度 (Time Complexity)](https://zh.wikipedia.org/wiki/%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6)</font><br /> 

<br>

<font size="5"> 定義: 演算法的時間複雜度 $(Time\ \ complexity）$是一個函式，它定性描述某個==演算法的執行時間==。這是一個==代表演算法輸入值的字串的長度的函式==。分析時可以不用直接運行程式，只要用肉眼觀察程式碼，用紙筆計算後大致可以計算出程式會耗費的時間資源的分析方式。</font><br />

<br>

---
<br>

## <font size="6">[範例(1): 插入排序 (Insertion sort)](https://zh.wikipedia.org/wiki/%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F) </font><br />
<br>

![](https://i.imgur.com/FwrB0J3.png)
## 
<br>

<font size="5"> 設 $c(cost)$ 為執行的步驟，$n$ 為 $[A]$ 的長度；即為執行次數。所以上圖的插入排序演算法，會執行 $c_{i}$ 個步驟；每個步驟執行 $n$ 次，==設 $t_{j}$ 為上圖第 $5$ 行 $whlie\ \ loop$ 在 $index=j$ 時的執行次數==</font><br />
<br>
##

><font size="5" color="#000066"> 第 $1$ 行:  設 $j$ 為下一個要比較 $data$ 的 $index\ \ \therefore\ j$ 從 $2$ 開始。==在執行到第 $n$ 次時會再進行一次比較 $j=[A]?$ 所以是執行 $n$ 次。== </font><br />
## 
><font size="5" color="#000066"> 第 $2$ 行: 宣告下個要插入比較的 $data\ \ A[j]$ 給 $key$ ，所以共執行 $n-1$ 次。 </font><br />
## 
><font size="5" color="#000066"> 第 $4$ 行: 宣告原本要比較的 $index$ 給 $i$ ，所以共執行 $n-1$ 次。</font><br />
## 
><font size="5" color="#000066"> 第 $5$ 行: 用 $while\ \ loop$ ，設定向前檢查的中斷點 $index>0$ 後比較 $data\ \ A[i]>key?$ </font><br />
## 
><font size="5" color="#000066"> 第 $6$ 行: 若第 $5$ 行成立，把 $A[i]$ 內的 $data$ 寫入 $A[i+1]$ $\ ($也就是把 $A[i]$ 向右移動$)$。</font><br />
## 
><font size="5" color="#000066"> 第 $7$ 行: 繼續向前檢查，直到新插入的 $data$ 比較大為止 $($$key>A[i]$$)$。</font><br />
## 
><font size="5" color="#000066"> 第 $8$ 行: $($此行在$\ while\ \ loop\ 外$$)$ 當 $A[i]$ 向右移到 $key>A[i]$ 時 $while\ \ loop$ 中斷，把 $key$ 的 $data$ 寫入 $A[i+1]$。 </font><br />
## 
<br>
<br>

![](https://i.imgur.com/nnIHqle.png)
## 
<br>

<font size="5"> $eg:$ 在上圖 $j=6\ ，key=3$ 時: </font><br />
<br>

<font size="5"> $\because\ \underline{3<6\ ......\ 3<2\ ?\ (比較了4次)，\therefore t_{6}\ =\ 4}$ ，每次比較後都執行 $data$ 右移: $6\ 寫入\ A[5+1]\ ，\ ......\ 4\ 寫入\ A[3+1]\ \because \ 3\nless2，\therefore while\ \ loop$ 中斷 ，把 $key$ 的 $data\ \ 3$ 寫入 $A[2+1]$。</font><br />
<br>

## 

<br>

### <font size="6" color=#4682B4>時間複雜度分析:</font><br /> 
## 
<font size="5">用時間函式 $T(n)$，來計算運作時間，也就是每個步驟 $c_{i}\ \ (level\ \ cost)$ 和 $input\ \ size:n$ 的總和。</font><br />
<br>
<br>

<font size="6">$\begin{split}T(n)&=c_{1}n\ +\ c_{2}(n-1)\ +\ c_{4}(n-1)\ +\ c_{5}\sum_{j=2}^{n}t_{j}\ +\\&c_{6}\sum_{j=2}^{n}(t_{j}-1)\ +\ c_{7}\sum_{j=2}^{n}(t_{j}-1)\ +\ c_{8}(n-1)\end{split}$</font><br />
# 
<br>

### <font size="6" color=#4682B4> Best Case &  時間複雜度分析: </font><br />
<br>

## 
><font size="5" color="#000066"> $\underline{\bf{c_{5}，c_{6}，c_{7}，c_{8}}}$ 在 $Best\ \ Case$ 下，$\ \because$ 皆已排序完畢，$\therefore\ \underline{\bf{c_{6}，c_{7}}}$ 不會運行， $\underline{\bf{c_{5}}}$ 每兩個 $data$ 只需比較 $1$ 次，共執行 $(n-1)$ 次。$\underline{\bf{c_{8}}}$ 也只會寫入 $key$ 原本的位置，共執行 $(n-1)$ 次。</font><br />
![](https://i.imgur.com/MlAr4GW.png)
## 
<br>

<font size="6"> $\large if\ \ t_{j}=1\ \ \ for\ \ \ j=2，3，...，n$</font><br />
<br>
<font size="6"> $\begin{split}T(n)&=c_{1}n\ +\ c_{2}(n-1)\ +\ c_{4}(n-1)\ +\ c_{5}(n-1)\ +\ c_{8}(n-1)\\&=(c_{1}+c_{2}+c_{4}+c_{5}+c_{8})n\ - \ (c_{2}\ +\ c_{4}\ +\ c_{5}\ +\ c_{8})\end{split}$</font><br />
<br>

# 
### <font size="6" color=#4682B4> Worst Case &  時間複雜度分析: </font><br />
## 
<br>

><font size="5" color="#000066"> $\underline{\bf{c_{5}}}$ 在 $Worst\ \ Case$ 下會比較 $\ \dfrac{n(n+1)}{2}-1$ 次，==$\dfrac{n(n+1)}{2}$ 為等差級數公式，== $\because\  j$ 從 $2$ 開始， $\therefore -1$。</font><br />
<br>

>><font size="5" color="#660066"> 等差級數公式原理: 高斯作法 $eg:1\ +\ 2\ +\ 3\ + ⋯ +\ 99\ +\ 100 =\ ?$ </font><br />
<br>
>><font size="5" color="#660066"> $(1)\ \ 1+2+3+⋯+98+99+100=S\\(2)\ \ 100 + 99 +98 + ⋯ + 3 + 2 + 1 = S$</font><br />
>><font size="5" color="#660066"> $(1)+(2)=101 +101+101 + ⋯ +101+101 +101 = 2S$</font><br />
>><font size="5" color="#660066"> $\therefore\ \dfrac{100\times 101}{2}=5050$ </font><br />
<br>
## 
<br>

><font size="5" color="#000066"> $\underline{\bf{c_{6}，c_{7}}}$ 由下圖知在 $Worst\ \ Case$下:</font><br /> 
><font size="5" color="#000066"> $\underline{\bf{c_{6}:}}$ 在 $index=6$ 時會讓 $data$ 右移 $5$ 次 $......$ 當 $index=2$ 則 $\underline{\bf{c_{6}}}$ 會讓 $data$ 右移 $1$ 次。</font><br /> 
<font size="5" color="#000066"> $\underline{\bf{c_{7}}}:$ 會讓 $index$ 往左檢查 $5$ 次 $......$ $1$ 次。</font><br />
<br>
<font size="5" color="#000066"> $\ \therefore$ $\ \underline{\bf{c_{6}，c_{7}}}$ 各別運行</font><br /> 
<br>
<font size="5" color="#000066"> $\underbrace{(2-1）+（ 3-1）+\ ......\ +\ (n-1)}_{n}= 1\ +\ 2\ +\ ......\ +\ (n-1)=\dfrac{n(n-1)}{2}$ 次。正好為三角形面積公式 $($底: $n\times$高: $(n-1)$ $\times \dfrac{1}{2}$ $)$</font><br />
<br>
![](https://i.imgur.com/TkuryG7.png) 
<br>
<font size="5" color="#000066"> $\underline{\bf{c_{8}}}:$ 會把 $key$ 的 $data$ 寫入 $A[i+1]$ 最多執行 $(n-1)$ 次。</font><br />
## 
<br>

<font size="6"> $\large if\ \ t_{j}=1\ \ \ for\ \ \ j=2，3，...，n$</font><br />
<br>

<font size="6">$\begin{split}T(n)&=c_{1}n\ +\ c_{2}(n-1)\ +\ c_{4}(n-1)\ +\ c_{5}(\dfrac{n(n+1)}{2}-1)\\&+\ c_{6}(\dfrac{n(n-1)}{2})\ +\ c_{7}(\dfrac{n(n-1)}{2})\ +\ c_{8}(n-1)\\&=(\dfrac{c_{5}+c_{6}+c_{7}}{2})n^2\ -\ (c_{1}+c_{2}+c_{4}+\dfrac{c_{5}-c_{6}-c_{7}}{2}+c_{8})n\\&-(c_{2}+c_{4}+c_{5}+c_{8})\end{split}$</font><br />


<br>

---
<br>

## <font size="6">[漸進符號 (又稱大O符號) (Asymptotic Notation or Big O notation)](https://zh.wikipedia.org/wiki/%E5%A4%A7O%E7%AC%A6%E5%8F%B7)</font><br />
<br>

<font size="5"> 定義: 在某個時間複雜度函式 $f(n)$ 的首項$（leading\ \  term）$，也就是帶有最高指數的那一項，在隨著輸入大小 $(input\ \ size)\ n$ 改變時，執行時間變化的幅度較大。因此，可捨去複雜度函數中其他較不重要的次項與常數，留下最大次項，==「透過簡單的函數來表述函數接近極限的行為」，讓時間複雜度函數更易理解==，這就是「漸進符號」的概念。參考資料: [(1)](https://rust-algo.club/concepts/asymptotic-notation/)，[(2)](https://wangwilly.github.io/willywangkaa/2018/08/28/Algorithm-Time-Complexity/)</font><br />
<br>
<br>
![](https://i.imgur.com/lwtZoq2.png)
<br> 
<br>
![](https://i.imgur.com/nsDu3fp.png)
<br>
<br>
![](https://i.imgur.com/o82oj2b.png)
<br>
<br>
#  
# <font size="6" color=#4682B4> (1) O - notation </font><br />
<br>
<br>
<br>

<font size="6">$\large f(n)=O(g(n))\iff \Omega(f(n))=g(n)\\∃C\ ,\ n_{0}\ >\ 0,\ \ such\ \ that\ \ \ f(n)\ ≤\ C\ ×\ g(n)\ ,\ n\ ≥\ n_{0}$</font><br />
# 
<br>
<br>

<font size="6">$稱\ g(n)\ 為\ f(n)\ 的\ Asymptotic\ \ upper\ \ bound\ \ f(n)\\的\ \ Order\ \ 會小於等於\ \ g(n)\ \ 的\ \ Order\ 。$</font><br />
<br>

# 
# <font size="6" color=#4682B4>(2) Θ - notation </font><br />
<br>
<br>

<font size="6">某些書定義成: </font><br />
<font size="6"> $\lim\limits_{n \to \infty}\dfrac{f(n)}{g(n)}=\underbrace L_{>0的常數}>0\iff f(n)=\Theta(g(n))$</font><br />
<br>

# 
<br>
<br>
<br>

<font size="6">$\large f(n)=\Theta(g(n))\iff f(n)=O(g(n))=\Omega (g(n))\\∃C_{1}\ ,\ C_{2}\ ,\ n_{0}\ >\ 0\ ,\ \ such\ \ that\\C_{1}\ ×\ g(n)\ ≤\ f(n)\ ≤\ C_{2}\ ×\ g(n)\ ,\ n\ ≥\ n_{0}$</font><br />
<br>
# 
<br>
<br>

<font size="6">$稱\ g(n)\ 為\ f(n)\ 的\ Asymptotic\ \ tight\ \ bound\ \ f(n)\\的\ \ Order\ \ 會等於\ \ g(n)\ \ 的\ \ Order\ 。$</font><br />
<br>
#  
# <font size="6" color=#4682B4>(3) Ω - notation</font><br />
<br>
<br>
<br>

<font size="6">$\large f(n)=\Omega(g(n))\iff O(f(n))=g(n)\\∃C\ ,n_{0}\ >\ 0,\ \ such\ \ that\ \ \ f(n)\ ≥\ C\ ×\ g(n)\ ,\ n\ ≥\ n_{0}$</font><br />
# 
<br>
<br>

<font size="6">$稱\ g(n)\ 為\ f(n)\ 的\ Asymptotic\ \ lower\ \ bound\ \ f(n)\\的\ \ Order\ \ 會大於等於\ \ g(n)\ \ 的\ \ Order\ 。$</font><br />
<br>
# 
# <font size="6" color=#4682B4>(4) o - notation</font><br />
<br>
<br>

<font size="6">某些書定義成: </font><br />
<font size="6"> $\lim\limits_{n \to \infty}\dfrac{f(n)}{g(n)}=0\iff f(n)=o(g(n))$</font><br />
<br>

# 
<br>
<br>
<br>

<font size="6">$\large f(n)=o(g(n))\iff f(n)=O(g(n))\ne\Theta(g(n))\\∃C\ ,\ n_{0}\ >\ 0,\ \ such\ \ that\ \ \ C\ ×\ g(n)\ >\ \ f(n),\ n\ ≥\ n_{0}$</font><br />
<br>
# 
<br>
<br>

<font size="6">$稱\ g(n)\ 為\ f(n)\ 的\ Asymptotic\ \ upper\ \ bound\ \ f(n)\\的\ \ Order\ \ 會絕對小於\ \ g(n)\ \ 的\ \ Order\ 。$</font><br />
<br>
# 
# <font size="6" color=#4682B4>(5) ω - notation</font><br />
<br>
<br>

<font size="6">某些書定義成: </font><br />
<font size="6"> $\lim\limits_{n \to \infty}\dfrac{f(n)}{g(n)}=\infty\iff f(n)=\omega(g(n))$</font><br />
<br>

# 
<br>
<br>
<br>

<font size="6">$\large f(n)=\omega(g(n))\iff f(n)=\Omega(g(n))\ne\Theta(g(n))\\∃C\ ,n_{0}\ >\ 0,\ \ such\ \ that\ \ \ f(n)\ >\ C\ ×\ g(n)\ ,\ n\ ≥\ n_{0}$</font><br />
# 
<br>
<br>

<font size="6">$稱\ g(n)\ 為\ f(n)\ 的\ Asymptotic\ \ lower\ \ bound\ \ f(n)\\的\ \ Order\ \ 會絕對大於\ \ g(n)\ \ 的\ \ Order\ 。$</font><br />
<br>
# 
# <font size="6" color=#4682B4>漸進符號的其他性質</font><br />
<br>
<br>

><font size="5" color="#000066">$(1)\ \ O\ ,\ \Omega\ ,\ \Theta\ ,\ o\ ,\ \omega\ 皆具有遞移性(transitive)\ 。$</font><br />
<br>
<font size="5" color="#000066">$\ \ \ \ \ \ \ eg:以\ O\ 為例，若\ f(n)=O(g(n))\ 且\ g(n)=O(g(n))\ 則\ f(n)=O(g(n))$</font><br />
<br>

><font size="5" color="#000066">$(2)\ \Theta，具有對稱性(symmetric)\ 。$</font><br />
<br>
><font size="5" color="#000066">$\ \ \ \ \ \ \ eg:a=b，b=a$</font><br />
<br>

><font size="5" color="#000066">$(3)\ \ O\ ,\ \Omega\ ,\ \Theta\ 具有反身性(reflexive)，即每個函式自己和自己一定有關係\ 。$</font><br />
<br>
><font size="5" color="#000066">$\ \ \ \ \ \ \ eg:f(n)=O(f(n))$</font><br />
<br>

><font size="5" color="#000066">$(4)\ \ Asymptotic\ \  Notation\ 未必滿足三一律(trichotomy)，\\ \ \ \ \ \ \ \ 也就是大於，小於，等於三種關係至少成立一個，即有可能發生\\ \ \ \ \ \ \ \ f(n)=O(g(n))\ 與\ f(n)=\Omega(g(n))\ 皆不成立的情形。$</font><br />
<br>

><font size="5" color="#000066">$\ \ \ \ \ \ \ eg:f(n)=n，g(n)=n^{1+sin\ n}，\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ 則\ f(n)=O(g(n))\ 與\ f(n)=\Omega(g(n))\ 皆不成立。\\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \because sin\ n\ 在-1\sim1\ 震盪\ but\ 時間函數一定\ >0\ ，\therefore\ +1$</font><br />
<br>

# 
# <font size="6" color=#4682B4>推導常用數學公式</font><br />
><font size="6" color="#000066">$(1)第1\sim n項等差級數公式:\dfrac{項數\times(首項+末項)}{2}\\ \ \ \ \ =\dfrac{n(n+1)}{2}$</font><br />
<br>

><font size="6" color="#000066">$\ \ \ \ \ \ eg:3+6+9+12+15=\dfrac{5\cdot(3+15)}{2}$</font><br />
<br>

><font size="6" color="#000066">$(2)第1\sim n項等比級數公式:\dfrac{(最高項^{項數次方+1}-最低項)}{公比-1}\\ \ \ \ \ =\dfrac{r^{n+1}-r^{1}}{r-1}$</font><br />
<br>

><font size="6" color="#000066">$\ \ \ \ \ \ eg:2^{0}+2^{1}+......+2^{n}=\dfrac{2^{n+1}-2^{0}}{2-1}$</font><br />
<br>

><font size="6" color="#000066">$(3)$</font><br />