演算法

# 演算法 --- ## [基本定義](https://zh.wikipedia.org/wiki/%E7%AE%97%E6%B3%95) 定義: 高德納(Donald Ervin Knuth) 在他的曠世巨作－《電腦程式設計藝術》裡已經幫我們整裡、歸納出一個==演算法需要俱備的五個特性==：[參考資料](https://jason-chen-1992.weebly.com/home/-whats-algorithm) > **1. 輸入：** 一個演算法必須有零個或以上的輸入。==$(input: \ \ge\ 0)$== >**2. 輸出：** 一個演算法應有一個或以上輸出，輸出是演算法計算的結果。==$(output: \ \ge\ 1)$== >**3. 明確性：** ==演算法的描述必須明確無歧義==，以保證演算法的實際執行結果是精確地符合要求或期望，通常要求實際執行結果是確定的。 >**4. 有限性:** 依據圖靈的定義，一個演算法是能夠被任何圖靈完備系統類比的一串運算，而圖靈機只有有限個狀態、有限個輸入符號和有限個轉移函式(指令)。而一些定義更規定==演算法必須在有限個步驟內完成任務。== >**5. 有效性：** 又稱可行性。==演算法中描述的操作都是可以通過已經實現，且容易的基本運算執行有限次來實現。== --- ## [時間複雜度 (Time Complexity)](https://zh.wikipedia.org/wiki/%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6) 定義: 演算法的時間複雜度 $(Time\ \ complexity）$是一個函式，它定性描述某個==演算法的執行時間==。這是一個==代表演算法輸入值的字串的長度的函式==。分析時可以不用直接運行程式，只要用肉眼觀察程式碼，用紙筆計算後大致可以計算出程式會耗費的時間資源的分析方式。 --- ## [範例(1): 插入排序 (Insertion sort)](https://zh.wikipedia.org/wiki/%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F) ![](https://i.imgur.com/FwrB0J3.png) ## 設 $c(cost)$ 為執行的步驟，$n$ 為 $[A]$ 的長度；即為執行次數。所以上圖的插入排序演算法，會執行 $c_{i}$ 個步驟；每個步驟執行 $n$ 次，==設 $t_{j}$ 為上圖第 $5$ 行 $whlie\ \ loop$ 在 $index=j$ 時的執行次數== ## > 第 $1$ 行: 設 $j$ 為下一個要比較 $data$ 的 $index\ \ \therefore\ j$ 從 $2$ 開始。==在執行到第 $n$ 次時會再進行一次比較 $j=[A]?$ 所以是執行 $n$ 次。== ## > 第 $2$ 行: 宣告下個要插入比較的 $data\ \ A[j]$ 給 $key$ ，所以共執行 $n-1$ 次。 ## > 第 $4$ 行: 宣告原本要比較的 $index$ 給 $i$ ，所以共執行 $n-1$ 次。 ## > 第 $5$ 行: 用 $while\ \ loop$ ，設定向前檢查的中斷點 $index>0$ 後比較 $data\ \ A[i]>key?$ ## > 第 $6$ 行: 若第 $5$ 行成立，把 $A[i]$ 內的 $data$ 寫入 $A[i+1]$ $\ ($也就是把 $A[i]$ 向右移動$)$。 ## > 第 $7$ 行: 繼續向前檢查，直到新插入的 $data$ 比較大為止 $($$key>A[i]$$)$。 ## > 第 $8$ 行: $($此行在$\ while\ \ loop\ 外$$)$ 當 $A[i]$ 向右移到 $key>A[i]$ 時 $while\ \ loop$ 中斷，把 $key$ 的 $data$ 寫入 $A[i+1]$。 ## ![](https://i.imgur.com/nnIHqle.png) ## $eg:$ 在上圖 $j=6\ ，key=3$ 時: $\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]$。 ## ### 時間複雜度分析: ## 用時間函式 $T(n)$，來計算運作時間，也就是每個步驟 $c_{i}\ \ (level\ \ cost)$ 和 $input\ \ size:n$ 的總和。 $\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}$ # ### Best Case & 時間複雜度分析: ## > $\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)$ 次。 ![](https://i.imgur.com/MlAr4GW.png) ## $\large if\ \ t_{j}=1\ \ \ for\ \ \ j=2，3，...，n$ $\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}$ # ### Worst Case & 時間複雜度分析: ## > $\underline{\bf{c_{5}}}$ 在 $Worst\ \ Case$ 下會比較 $\ \dfrac{n(n+1)}{2}-1$ 次，==$\dfrac{n(n+1)}{2}$ 為等差級數公式，== $\because\ j$ 從 $2$ 開始， $\therefore -1$。 >> 等差級數公式原理: 高斯作法 $eg:1\ +\ 2\ +\ 3\ + ⋯ +\ 99\ +\ 100 =\ ?$ >> $(1)\ \ 1+2+3+⋯+98+99+100=S\\(2)\ \ 100 + 99 +98 + ⋯ + 3 + 2 + 1 = S$ >> $(1)+(2)=101 +101+101 + ⋯ +101+101 +101 = 2S$ >> $\therefore\ \dfrac{100\times 101}{2}=5050$ ## > $\underline{\bf{c_{6}，c_{7}}}$ 由下圖知在 $Worst\ \ Case$下: > $\underline{\bf{c_{6}:}}$ 在 $index=6$ 時會讓 $data$ 右移 $5$ 次 $......$ 當 $index=2$ 則 $\underline{\bf{c_{6}}}$ 會讓 $data$ 右移 $1$ 次。 $\underline{\bf{c_{7}}}:$ 會讓 $index$ 往左檢查 $5$ 次 $......$ $1$ 次。 $\ \therefore$ $\ \underline{\bf{c_{6}，c_{7}}}$ 各別運行 $\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}$ $)$ ![](https://i.imgur.com/TkuryG7.png) $\underline{\bf{c_{8}}}:$ 會把 $key$ 的 $data$ 寫入 $A[i+1]$ 最多執行 $(n-1)$ 次。 ## $\large if\ \ t_{j}=1\ \ \ for\ \ \ j=2，3，...，n$ $\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}$ --- ## [漸進符號 (又稱大O符號) (Asymptotic Notation or Big O notation)](https://zh.wikipedia.org/wiki/%E5%A4%A7O%E7%AC%A6%E5%8F%B7) 定義: 在某個時間複雜度函式 $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/) ![](https://i.imgur.com/lwtZoq2.png) ![](https://i.imgur.com/nsDu3fp.png) ![](https://i.imgur.com/o82oj2b.png) # # (1) O - notation $\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}$ # $稱\ g(n)\ 為\ f(n)\ 的\ Asymptotic\ \ upper\ \ bound\ \ f(n)\\的\ \ Order\ \ 會小於等於\ \ g(n)\ \ 的\ \ Order\ 。$ # # (2) Θ - notation 某些書定義成: $\lim\limits_{n \to \infty}\dfrac{f(n)}{g(n)}=\underbrace L_{>0的常數}>0\iff f(n)=\Theta(g(n))$ # $\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}$ # $稱\ g(n)\ 為\ f(n)\ 的\ Asymptotic\ \ tight\ \ bound\ \ f(n)\\的\ \ Order\ \ 會等於\ \ g(n)\ \ 的\ \ Order\ 。$ # # (3) Ω - notation $\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}$ # $稱\ g(n)\ 為\ f(n)\ 的\ Asymptotic\ \ lower\ \ bound\ \ f(n)\\的\ \ Order\ \ 會大於等於\ \ g(n)\ \ 的\ \ Order\ 。$ # # (4) o - notation 某些書定義成: $\lim\limits_{n \to \infty}\dfrac{f(n)}{g(n)}=0\iff f(n)=o(g(n))$ # $\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}$ # $稱\ g(n)\ 為\ f(n)\ 的\ Asymptotic\ \ upper\ \ bound\ \ f(n)\\的\ \ Order\ \ 會絕對小於\ \ g(n)\ \ 的\ \ Order\ 。$ # # (5) ω - notation 某些書定義成: $\lim\limits_{n \to \infty}\dfrac{f(n)}{g(n)}=\infty\iff f(n)=\omega(g(n))$ # $\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}$ # $稱\ g(n)\ 為\ f(n)\ 的\ Asymptotic\ \ lower\ \ bound\ \ f(n)\\的\ \ Order\ \ 會絕對大於\ \ g(n)\ \ 的\ \ Order\ 。$ # # 漸進符號的其他性質 >$(1)\ \ O\ ,\ \Omega\ ,\ \Theta\ ,\ o\ ,\ \omega\ 皆具有遞移性(transitive)\ 。$ $\ \ \ \ \ \ \ eg:以\ O\ 為例，若\ f(n)=O(g(n))\ 且\ g(n)=O(g(n))\ 則\ f(n)=O(g(n))$ >$(2)\ \Theta，具有對稱性(symmetric)\ 。$ >$\ \ \ \ \ \ \ eg:a=b，b=a$ >$(3)\ \ O\ ,\ \Omega\ ,\ \Theta\ 具有反身性(reflexive)，即每個函式自己和自己一定有關係\ 。$ >$\ \ \ \ \ \ \ eg:f(n)=O(f(n))$ >$(4)\ \ Asymptotic\ \ Notation\ 未必滿足三一律(trichotomy)，\\ \ \ \ \ \ \ \ 也就是大於，小於，等於三種關係至少成立一個，即有可能發生\\ \ \ \ \ \ \ \ f(n)=O(g(n))\ 與\ f(n)=\Omega(g(n))\ 皆不成立的情形。$ >$\ \ \ \ \ \ \ 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$ # # 推導常用數學公式 >$(1)第1\sim n項等差級數公式:\dfrac{項數\times(首項+末項)}{2}\\ \ \ \ \ =\dfrac{n(n+1)}{2}$ >$\ \ \ \ \ \ eg:3+6+9+12+15=\dfrac{5\cdot(3+15)}{2}$ >$(2)第1\sim n項等比級數公式:\dfrac{(最高項^{項數次方+1}-最低項)}{公比-1}\\ \ \ \ \ =\dfrac{r^{n+1}-r^{1}}{r-1}$ >$\ \ \ \ \ \ eg:2^{0}+2^{1}+......+2^{n}=\dfrac{2^{n+1}-2^{0}}{2-1}$ >$(3)$