演算法(Algorithm)是什麼?演算法應用的例子與場景

為什麼我們需要演算法

1. 解決問題與改善效率：演算法是我們處理資訊，解決問題和進行決策的關鍵工具。他們可以幫助我們更有效率地完成任務，減少時間和資源的浪費。
2. 應用範疇廣泛：從網路搜索、社交媒體的內容推薦，到機器學習和人工智慧，無處不在的演算法都在背後默默運作，大大擴展了我們處理資訊的能力。
3. 實現自動化與智慧化：在大數據時代，演算法不僅能自動化地處理大量資訊，還能從中學習並優化自己的運作，實現智慧化。
4. 支持決策制定：在商業、科學、醫療等領域，演算法可幫助我們對大量數據進行分析和挖掘，從而提供有價值的見解和支持決策。

演算法種類

演算法就和問題一樣有許多種類。以下是電腦科學領域常見的幾種演算法：

• 簡單遞迴演算法 (Simple recursive algorithms:)：這些演算法使用遞迴計算來找答案。這個方法用於解決古典問題，例如「計算到 n 次方」。
• 回溯法 (Backtracking)：為了找到解決方法，一個問題先劃分為多個計算用的路徑。如果路徑方向錯誤，便回到上一個位置，從另一個方向開始計算。常見的使用案例需要從大量數據中找到特定資訊。這個方法通常用來找出每一條路徑。如果一條路徑不包含目標資訊，則演算法會回到上一個連接點。
• 動態法 (Dynamic)： 這個演算法的獨特之處在於演算法會記憶之前解決過的問題，並藉由之前解決問題的經驗更快找到類似問題的解決方法。如果之前你計算過 n 的 1,000,000 次方，這個演算法不需從頭重新計算，而是能根據之前計算 n 的 1,000,001 次方的答案，更快找到解答。
• 分而治之法 (Divide and conquer)：排序是分而治之演算法常見的類型。這種演算法將一系列數字切分為多個部分，然後在每個部分進行比較排序。所有部分之後合併起來，整個組合會再次進行比較排序。這種方法的操作速度比只排序不分割的演算法還要快上好幾倍。
• 暴力法 (Brute force)：這是駭客最常使用的演算法。如果駭客想要駭入你的帳戶，大概會一次就嘗試所有可能的密碼組合。之所以稱為暴力演算法，是因為這個方法靠電腦速度暴力破解密碼。
• 貪婪法 (Greedy)：貪婪演算法和暴力演算法類似。這個解決方法會根據當前狀況，找出最佳解決方法，常用來尋找與決定行駛路線。演算法不會計算抵達目的地的所有可能路線，只選擇距離下一個檢查點最短的路線，而且不會考慮檢查點之後的其他路線。

演算法的應用

在這裡我們收集了幾個我們生活常碰到，而且有趣的演算法，請參考這幾個外部連結。

• 排列 (Sorting) – 如何把千多本書排列順序？
• 秘書問題 (Secretary Problem) – 如果你要聘請一名秘書，總共有 n 個申請者。每次只能面試一人，面試後要馬上決定是否聘他，如果當時決定不聘他，就再沒有機會。問：要面試幾個人，才最有機會選中最合適的人選？解決這個問題的方法，叫「最佳停止演算法」(Optimal Stopping Algorithm).
• PageRank – How Search Work by Google – Google 最早的是用 PageRank 這個演算法去判斷如何排列用戶搜尋的結果。
• EdgeRank – Facebook 動態消息 (Newsfeed) 早期以一個叫 EdgeRank 的演算法來判斷用戶看到什麼訊息。這篇文章可以幫助你了解更多有關 EdgeRank。

演算法的應用場景：以計算平均股價為例

計算平均股價－未使用演算法

說明：假設有過去 100 天的股價，但只需要最近 20 天的平均股價，這段程式的確能計算出最後 20 天的平均價格，卻導致浪費了 80 個空間去儲存不需要的股價資料。如果要計算的數字越多，就會浪費更多的空間。

計算平均股價－使用演算法‍

說明：這段程式碼跟前一段相比，多加了宣告，把 list 變成固定長度，length 設為 20，最新的數字會把舊的數字蓋掉。所以不管股價資料幾筆，所需的執行空間都固定。如果拿評估演算法效能的指標 Big-O 來看，這個作法就是達到了空間複雜度 Ｏ(1) 的理想狀況。

從上述舉例可得知，演算法能提高程式碼的執行效率。特別是當使用者規模或資料量達一定程度時，應用演算法提升程式的效能就變得非常重要。

如何評估演算法？

演算法除了能否正確解決問題之外，還有「好、壞」之分嗎？答案是有的。不同的演算法，雖然都能正確達成目標，但還是有效能 (efficiency) 之分。主要的考量點有兩個：

• 時間複雜度 (Time complexity) – 它代表一個演算法的執行時間。針對同一個問題，有些演算法會比別的用更短的時間(也是更快速)去解決問題。
• 空間複雜度 (Space complexity) – 它指的是要執行該演算法 (或是程式碼) 所需的記憶體量。

BigO Notation

可以理解，效能越好的演算法，它所需要的時間會越短、空間也越少。衡量時間、空間複雜度的方法我們叫 “Big O notation” ：是一種在數學和計算機科學中用來描述一個函數成長率的符號。在計算機科學中，我們通常用 Big O 表示法來評估和比較不同演算法的效率。

Big O 表示法主要聚焦在演算法的最壞情況性能，也就是輸入資料量最大時的情況。我們主要看的是當輸入大小 n 開始增大，演算法執行時間如何增長。

以下是一些常見的 Big O 時間複雜度：

• O(1)：常數時間複雜度。不論輸入大小如何，此類演算法的執行時間都保持不變。
• O(log n)：對數時間複雜度。隨著輸入資料的增加，演算法的執行時間會以對數的方式增加。著名的二分搜尋就是一個時間複雜度為 O(log n) 的例子。
• O(n)：線性時間複雜度。演算法的執行時間與輸入大小呈直線關係。舉例來說，一個簡單的 for 迴圈，從頭到尾掃過一個陣列的操作，就是 O(n)。
• O(n log n)：線性對數時間複雜度。這是一種介於線性和二次方之間的時間複雜度。著名的快速排序就是一個時間複雜度為 O(n log n) 的例子。
• O(n^2)：二次方時間複雜度。當輸入大小 n 倍增，演算法執行時間會變為原來的四倍。經典的泡沫排序就是一個時間複雜度為 O(n^2) 的例子。
• O(n!)：階乘時間複雜度。這類型的時間複雜度是所有最慢的，並且當 n 超過一定的大小後，這種算法幾乎不能在實際中使用。旅行銷售員問題的暴力求解就是一個時間複雜度為 O(n!) 的例子。

演算法面試準備與LeetCode 刷題重點心法

經典演算法例子

1. SVM演算法（Space vector modulation 支援向量機）

• 應用：主要用於分類問題，也可用於回歸。
• 原理：在特徵空間中尋找最佳超平面，以最大化不同類別之間的間隔。
• 特點：適合於高維數據集，對於非線性問題可以通過核技巧進行處理。

2. Minimax演算法

• 應用：主要用於零和遊戲，如象棋或圍棋。
• 原理：通過最小化對手可能獲得的最大收益來最大化自己的最小收益。
• 特點：常與Alpha-Beta剪枝一起使用，以提高效率。

3. ID3（Iterative Dichotomiser 3）

• 應用：用於創建決策樹，主要用於分類問題。
• 原理：使用信息增益作為分割數據的標準。
• 特點：易於理解和實現，但容易過擬合，且不支持連續屬性和缺失值處理。

4. C4.5

• 應用：是ID3的改進版，用於生成決策樹。
• 原理：使用增益比率來選擇特徵，克服了ID3對於特徵值數量偏多的屬性有偏好的問題。
• 特點：支持連續屬性的處理，對缺失值具有一定的容錯性。

5. Apriori演算法

• 應用：廣泛用於關聯規則學習，特別是在市場籃分析中。
• 原理：通過尋找頻繁項集來構建規則，基於這樣的假設：頻繁項集的子集也是頻繁的。
• 特點：簡單且直觀，但對大數據集效率較低。

6. EM（期望最大化）

• 應用：用於處理包含隱藏變量的統計問題，如聚類分析和最大似然估計。
• 原理：通過迭代地進行兩個步驟來最大化數據的似然函數：期望步驟（E步）和最大化步驟（M步）。
• 特點：適用於數據不完整或有隱藏變量的情況，但對初始值選擇敏感，可能陷入局部最優。

每種演算法都有其獨特的應用場景和特點，並在機器學習和數據分析的不同領域發揮著重要作用。理解這些演算法的原理和用途對於開發有效的數據驅動應用至關重要。

演算法書推薦

入門科普類

《寫程式前就該懂的演算法: 資料分析與程式設計人員必學的邏輯思考術》 ： 透過生動的插圖與實例，將演算法的複雜概念化為簡單易懂的知識。本書涵蓋基礎至進階演算法，適合程式設計新手與專業人員。透過詳解與練習題，讀者能夠深化對演算法的理解，提升解決問題的能力。

《改變世界的九大演算法》：淺顯介紹了塑造當代數位生活關鍵技術的九種演算法。從搜尋引擎、網頁排序到公鑰加密和數位簽章，這本書透過易懂的語言揭示了每日應用背後的科學原理。無需資訊科學背景，讀者可洞察這些技術如何定義我們的數位世界，感受到科學家與數學家的創新與探索。是理解現代技術不可或缺的閱讀。

專業書籍

演算法導論《Introduction to Algorithms》：這本書是演算法領域的經典之作。全面而深入地介紹了從基礎數據結構到複雜演算法設計與分析的各項知識。無論是學術研究還是實際應用，書中詳細的解釋和豐富的範例都讓它成為了程式設計師和電腦科學學生的必讀書籍。

《The Algorithm Design Manual》：由Steven S. Skiena撰寫，提供了一個實用的指南，專注於解決實際問題的演算法設計與應用。Skiena教授不僅詳細介紹了演算法的理論基礎，還著重於如何將這些理論應用於解決日常生活中的問題。這本書以其親切的語言和豐富的實例，幫助讀者深入理解演算法設計的藝術，是程式設計師和系統分析師的實用工具書。

演算法學習 Q&A

Q：學習演算法之前，需要有什麼樣的基礎嗎？

演算法算是獨立學問，不太需要基礎知識，但由於會使用 Big-O 來分析演算法效率，分析時會用到高中數學知識，如指數、對數等，所以還是要理解一些高中數學，假設真的忘了，碰到時再回頭補上即可。

Q：演算法會因程式語言不同而有差異嗎？

95% 邏輯是一樣的，但根據語言特性，實作細節寫法可能有點不同。如果要從零開始準備演算法面試，提供兩個面向供參考：

• 選擇自己最熟悉的語言練習演算法：絕大多數公司在面試演算法時，不會要求使用的程式語言，因此可以用自己最拿手的程式語言來準備
• 若無特別熟悉的程式語言，建議可以用 C 語言來學習演算法：由於 C 語言是很原始的程式語言，如果用 C 寫得出演算法，基本上其他語言也寫得出來

無論如何，程式語言只是工具，在準備演算法面試時，建議使用自己最拿手的武器去應戰。

Q：網路開發新手在做 side project 時，如何導入演算法思維？

其實蠻困難的，因為絕大多數前端應用軟體都用不到演算法，再者如果沒有演算法的概念，也無從應用起。只有當你具備演算法基礎知識時，做 project 才有機會用到演算法，因此在做 side project 時，可以反問自己：有沒有更棒的程式寫法。

Q：演算法學習路徑？

1. 選擇一個網站或平台：選擇一個網站或平台，例如 LeetCode、HackerRank、Codeforces 或 TopCoder 等，這些平台提供了各種演算法練習題目和解答，可以幫助你練習演算法和提高編程能力。

2. 選擇一個語言：選擇一個你熟悉且喜歡的程式語言，例如 C++、Java、Python 或 JavaScript 等，這些語言都可以用來編寫演算法。

3. 練習基本演算法：練習基本的演算法，例如排序、搜索、數據結構等，這些演算法是學習更複雜演算法的基礎。

4. 解決算法問題：解決算法問題，例如 LeetCode 或 HackerRank 上的題目，這些題目可以幫助你練習演算法和編程能力，並提高解決問題的能力。

5. 實現和優化演算法：實現和優化學習的演算法，例如實現一個搜索算法、優化一個排序算法或編寫一個機器學習模型等。

6. 參加競賽和挑戰：參加編程競賽、刷題、挑戰和解答問題等，可以幫助提高演算法和程式技能，並學習更多的演算法和數據結構。