【舌尖上的演算法】Day1 -- 初嚐演算法

前言

從生物科技產業轉行到資訊科技產業不知不覺來到第五個年頭，這五年裡當個無憂無慮的小小碼農渾渾噩噩地來到了今天，雖然內心一直覺得既然踏入了這個行業，不會一點演算法好像不太行，但畢竟我一直都沒有點數學這個技能項目，也不覺得自己邏輯好，因此這五年始終沒有勇氣去面對這駭人的項目；如今，有個朋友找我一起組隊參加第12屆ＩＴ邦幫忙鐵人賽，一個小小碼農也沒什麼特長可以分享，於是我決定藉由這個機會來摸一摸演算法，同時也透過寫成文章的方式來試著將自己理解的內容用最簡單的方式表達出來，希望能夠幫助到其他想了解演算法卻又無從開始的人。

30天後的目標

連續30天介紹一個主題是個看似時間不長但卻很考驗毅力的一件事，既然下定決心要挑戰，就要設定一個衝線標準🏆，因此我在這30天裡，希望可以透過下列四點來讓大家初步了解演算法到底都在幹嘛：

• 了解8個資料型別及其特性
• 了解5種資料結構及其特性
• 了解Ｎ種演算法及其目的
• 了解如何估計演算法的執行效能
• 數獨背後的演算法及資料結構

為什麼要學演算法？

演算法學可以視為資訊科技、電腦科學的發展基礎，廣義來說，如果沒有演算法就不會有所謂的『程式』，程式的運行基礎就是建立在各式各樣不同的演算法上。身為一個ＩＴ領域的有為青年，學習演算法可以幫助了解到在不同的情境下，有一些基礎且標準的演算法可以用來解決難題，甚至可以自己設計出新的演算法並分析這個新演算法的執行效率來進行調整與優化。此外，在David Harel的書中-Algorithmics: the Spirit of Computing-就有提到：「演算法學不只是電腦科學其中的一個分支，更是電腦科學的核心觀念，甚至可應用到其他科學、科技與商業行為上」，因此演算法除了應用在電腦科學領域之外，還可以在其他領域中實現演算法的一些概念，進而解決問題與困境，所以演算法一直都存在於我們的生活中，只是平常不會意識到罷了。

而演算法的重要性在於運算的速度，在目標資料的數量不龐大的情況下，演算法看似可有可無，可是只要數量來到上萬筆，那這運算速度的問題就會凸顯出來了；如同一開始只是拿一把斧頭去砍樹枝，還算應付的來，速度可能也還能接受，但如果還是只拿一把斧頭去砍樹🌴，樹還是可以被砍斷，只是所花費的時間會大幅增加。或許在開發小系統或小專案中不太會去思考運算速度的問題，可是對於一些大型系統而言，其運算速度可能攸關公司的運作，例如電商的搜尋引擎，假設你輸入關鍵字要找某一類的產品，結果網頁一直在轉圈圈，估計你下一個動作就是把網頁關掉，然後去用其他的電商平台了😡。

因此，學演算法的目的是在有限的步驟內精準地解決問題，而透過了解演算法的步驟，試著進一步對演算法或程式進行優化，來達到最佳的執行效率。

什麼是演算法？

既然生活中就圍繞著演算法，那到底演算法是什麼東西？🤨

雖然針對「演算法」這個名詞並沒有一個所謂標準的定義，卻有一個一致認可的解釋：演算法是用來解決問題的一系列清楚明白的步驟或指示，換言之，演算法就是針對問題精確地列出解決步驟進而得到解答。

如上圖所示，演算法的概念就是：透過演算法(Algorithm)的步驟(Computer)將問題(Problem)的Input（用來解決問題的素材）轉換成Output（解答），下面我舉兩個例子來初步解釋這個概念：

問題一(Problem)-生活中的演算法：如何製作奶酪吐司？

食材(Input）：

• 六片厚切冷凍白吐司
• 200克軟化的奶油（非冷凍）
• 100克帕瑪森起司
• 沙拉油

製作步驟(Algorithm-Computer):

1. 在碗中將奶油與帕瑪森起司混合均勻
2. 在厚切冷凍白土司上塗抹一層奶油起司
3. 放回冷凍庫待其凝固
4. 預熱平底鍋（中溫）後，加入適量沙拉油，奶酪吐司置於平底鍋中（有奶油起司的面朝下）烹飪，直到吐司上面解凍且奶油起司面呈現金黃色，即可起鍋。

結果(Output)：六片熱奶酪吐司

上面的例子中，製作步驟即可視為『演算法的步驟』，這樣是不是稍微比較有一點感覺了。👍

問題二(Problem)-兩種演算法v.s.同一個問題：求最大公因數（Greatest Common Divisor）

兩個要求最大公因數的數值(Input）：

• m, n

計算步驟與方法(Algorithm-Computer):

下面提供兩種計算的方法：

1. Euclid’s Algorithm

   Euclid’s algorithm是反覆地去計算GCD(m, n) = GCD(n, m mod n)，直到第二個數值（n)為零時，第一個數值（m）即為最大公因數。

   (公式中的mod表示取餘數)

   例如：GCD(60, 24) = GCD(24, 12) = GCD(12, 0) = 12

   步驟分解：

   1. m = 60, n = 24 ➡︎ GCD(60, 24) ➡︎ 60 ÷ 24 = 2 … 12
   2. m = 24, n = 12 ➡︎ GCD(24, 12) ➡︎ 24 ÷ 12 = 2 … 0
   3. m = 12, n = 0 ➡︎ GCD(12, 0) ➡︎ 第二個數值為零，故第一個數值（12）即為60和24的最大公因數

2. Common Primes

   Common primes就是將兩個數值分別進行質因數分解，再將兩者分解後的結果進行比較，取出相同的部分相乘，即可得到兩數值的最大公因數。

   例如：

   • 60 = 2 × 2 × 3 × 5
   • 24 = 2 × 2 × 2 × 3
   • GCD(60, 24) = 2 × 2 × 3 = 12

結果(Output)：m, n的最大公因數

雖然這兩種方法都可以求出最大公因數，但是實際上在透過程式執行時，若要進行Common Primes的話，需要先準備一個質因數的清單，有了清單之後還需要針對各別數值去一一計算出分解後的公式，這一個步驟也是會很花時間的關鍵，因此Common Primes的實作複雜度會比Euclid’s Algorithm大得多，且前者的執行效率也比後者慢許多（因為步驟多）。從這裡我們也可以知道，針對同一個問題，雖然可以透過不同的演算法來得到結果，但在演算法的設計上，仍然會有執行效率上的差異，而這些微的差異卻有可能演變成影響整個系統效能的關鍵。

小結

1. 學演算法的目的是在有限的步驟內精準地解決問題。
2. 演算法是個✨用來解決問題的一系列精準不模糊的步驟或指示✨。
3. 不是只有Computer Science領域的人才需要學習演算法，演算法的應用一直存在我們生活中，食譜就是一個很好的例子。
4. 透過好的演算法可以提升程式運行的效率，進而穩定公司的運作。

預告

下一篇將會介紹如何估計、衡量一個演算法的效率⏱。

References

1. Introduction to the Design and Analysis of Algorithms, 3rd Edition, by Anany Levitin
2. Make a Sizzler Cheese Sandwich

• ← A Brief Introduction of Using Java Logger
• → 【舌尖上的演算法】Day2 -- 解析演算法的優劣（上）