## 演算法初論 (Algorithms) Author: 張佑丞 --- 什麼是演算法? ---- 顧名思義 演算的方法 --- 為什麼我需要學習演算法? ---- 舉個例子 ---- 今天我們在排隊  ---- 每個人發一個號碼牌 從1到1000號 ---- 你的朋友在750號 ---- 如何快速地找到他，然後插隊呢 --- 方法一： ---- 從頭開始問(Top-down) 1號、2號、3號...750號 ---- 總共要問幾個人呢 ---- 答：750人 --- 方法二： ---- 從最後一個人開始問(Bottom-up) 1000號、999號、998號...750號 ---- 總共要問幾個人呢 ---- 答：250人 --- 方法三： ---- 找每段最中間的人問(Binary-Search) ---- 什麼意思？！ ---- 我先問隊伍最中間的人 ---- 就是$[\frac{1+1000}{2}]=500$號 ---- 那麼我就知道750一定在500後面吧 ---- 那我在從500-1000的隊伍當中 再挑最中間的人問 ---- 那就是 $[\frac{500+1000}{2}]=750$號 ---- 那我就找到了wwww ---- 總共問了幾個人呢 ---- 答：2 --- 各種方法比較： ---- 方法一：從頭問(Top-down) -> 750次 方法二：從尾問(Bottom-up) -> 250次 方法三：問每段中間(Binary-Search) -> 2次 ---- 那速度大小你覺得誰最快、誰最慢呢 ---- 是 三>二>一 嗎 --- 不論你朋友幾號都是如此嗎? ---- 如果你朋友是250號呢？ ---- 各方法分別要問幾次呢？ ---- 方法一:(Top-down) 1號...250號 ---- 答：250次 ---- 方法二：(Buttom-up) 1000號...250號 ---- 答：750次 ---- 方法三：(Binary-Search) ---- $1^{st}$ 次：$[\frac{1+1000}{2}]=500號$ 250在1-500間 $2^{nd}$次：$[\frac{1+500}{2}]=250號$ ---- 答：2次 ---- 各方法分別要問幾次呢？ ---- 方法一：從頭問(Top-down) -> 250次 方法二：從尾問(Bottom-up) -> 750次 方法三：問每段中間(Binary-Search) -> 2次 ---- 速度快慢？ 三>一>二 ---- 疑？答案跟剛剛不一樣欸 ---- 沒有絕對的快慢嗎? --- 時間複雜度(Time Complexity) 又稱 $O$ (Big O) ---- 既然每次速度大小都不一定 ---- 不如我們都挑最慢的時候(The Worst Case) ---- 假設總共有n個號碼(1,2,3...,n) ---- 方法一(Top-down) 最糟的時候: ---- 剛好在最後一個 ---- 那就要問n個人 方法一的時間複雜度就是n ---- 方法二(Bottom-up) 最糟的時候: ---- 剛好在第一個 ---- 那就要問n個人 方法二的時間複雜度就是n ---- 方法三（Binary-Search) 最糟的時候： ---- 是什麼時候呢？ ---- 答：剛好在第一或最後一個 ---- 那要問幾個人呢 ---- 數學時間！！ ---- $1^{st}$次 $n \to \frac{n}{2}$ $2^{nd}$次 $\frac{n}{2} \to \frac{n}{4}$ . . $k^{th}$次 $\frac{n}{2^{k-1}} \to \frac{n}{2^k}$ ---- 最後一次的時候 $\frac{n}{2^k} = 1$ $k=\log_{2}{n}$ ---- 那就要問$\log_{2}{n}$次人 方法三的時間複雜度就是$\log_{2}{n}$ 但通常我們寫$\log{n}$ ---- 各種方法的時間複雜度比較： ---- 方法一：從頭問(Top-down) -> n次 -> $O(n)$ 方法二：從尾問(Bottom-up) -> n次 -> $O(n)$ 方法三：問每段中間(Binary-Search) -> $\log{n}$次 -> $O(\log{n})$ ---- 那這樣就可以比較了嗎 ---- 當n很大的時後 $\because \log{n}<n=n$ $\therefore$速度：三<二＝一 ---- 當然這只是一個例子 演算法的範疇還是非常廣的歐 今天就先到這裡吧