歡迎來到演算法的世界！
你好！今天我們要深入探討計算機科學中最令人興奮的部分之一：演算法 (Algorithms)。你可能會覺得演算法是複雜的數學謎題，但其實它們就只是一組指令，就像烘焙蛋糕的食譜，或者是你繫鞋帶時遵循的步驟一樣。在本章中，我們將學習如何有效地設計這些指令，如何衡量它們有多「快」，並探索每一位優秀的計算機科學家都必須了解的「經典」演算法。別擔心一開始會覺得負擔太重——我們會一步一步把它拆解開來！
1. 設計與分析演算法
在我們編寫任何程式碼之前，必須先構思計劃。分析與設計 (Analysis and design) 涉及觀察一個問題並決定解決它的最佳途徑。當我們分析一個演算法時，通常會關心兩件事：
1. 時間 (Time)： 執行需要多久？
2. 空間 (Space)： 它佔用了多少記憶體？
類比： 想像你在清理房間。其中一個「演算法」是把所有東西都丟進衣櫥。這非常快速（時間短），但佔用了大量的衣櫥空間。另一個「演算法」是把每件物品都完美地摺疊好。這會花費很多時間，但節省了空間。在計算機科學中，我們總是在尋求這兩者之間的最佳平衡點！
重點總結
演算法是一組解決問題的步驟。我們根據其執行時間和佔用的記憶體空間來評估它們。
2. 大 O 符號：衡量效率
我們如何告訴朋友一個演算法比另一個「更好」？我們使用大 O 符號 (Big O Notation)。這是一種描述演算法效能隨著數據量（我們稱之為 \(n\)）增加而如何變化的方法。
大 O 類型快速回顧：
- \(O(1)\) - 常數複雜度 (Constant Complexity)： 無論你有多少數據，時間都保持不變。例如：查看列表中的第一項。
- \(O(\log n)\) - 對數複雜度 (Logarithmic Complexity)： 時間增長得非常緩慢。這是搜尋演算法的「黃金標準」。例如：二分搜尋法 (Binary Search)。
- \(O(n)\) - 線性複雜度 (Linear Complexity)： 如果數據量加倍，所需時間也會加倍。例如：讀取列表一次。
- \(O(n^2)\) - 多項式複雜度 (Polynomial Complexity)： 通常涉及嵌套迴圈 (Nested loops)。如果數據量加倍，所需時間會變成原來的四倍！例如：氣泡排序法 (Bubble Sort)。
- \(O(2^n)\) - 指數複雜度 (Exponential Complexity)： 每增加一個數據，時間就會加倍。這些演算法非常「昂貴」且緩慢。例如：解決某些複雜的謎題。
你知道嗎？ 即使電腦的速度快上一億倍，\(O(2^n)\) 的演算法最終還是會變得慢到無法使用，因為它的增長速度實在太驚人了！
重點總結
大 O 衡量的是效率。從最快到最慢，順序是：\(O(1)\)、\(O(\log n)\)、\(O(n)\)、\(O(n^2)\)、\(O(2^n)\)。
3. 資料結構的演算法
儲存數據的不同方式（資料結構）需要不同的演算法來管理。以下是你必須知道的重要概念：
堆疊 (Stacks) 與佇列 (Queues)： 我們使用演算法來對堆疊進行 Push（加入）或 Pop（移除，類似疊盤子），並對佇列進行 Enqueue（加入）或 Dequeue（移除，類似排隊購物）。
鏈結串列 (Linked Lists)： 若要尋找項目，我們從 Head（開頭）開始，沿著指標從一個節點走到下一個，直到到達 Tail（結尾）。
樹狀結構遍歷 (Tree Traversals)： 為了存取樹中的每個節點，我們使用兩種主要方法：
1. 廣度優先搜尋 (Breadth-First)： 在移到下一層之前，先存取同一層的所有節點（向「寬度」發展）。
2. 深度優先搜尋 (後序遍歷，Depth-First, Post-order)： 在回溯並嘗試另一分支之前，先儘可能深入某一分支（向「深度」發展）。
重點總結
演算法是我們用來操作資料結構的「工具」。遍歷 (Traversing) 指的是存取結構中的每一個部分一次。
4. 標準排序演算法
排序只是將事物按順序排列（如字母或數字順序）。你需要知道這四種：
氣泡排序法 (Bubble Sort)： 比較兩個相鄰元素。如果順序錯誤就交換它們。重複此過程直到末尾。然後重新開始，直到整個列表排序完成。效率：\(O(n^2)\)。
插入排序法 (Insertion Sort)： 每次拿取一個項目，並將其「插入」到已排序子列表的正確位置。想像一下你如何排列手中的撲克牌。效率：\(O(n^2)\)。
合併排序法 (Merge Sort)： 一種「分治法 (Divide and Conquer)」演算法。重複將列表對半分割，直到你有許多只有 1 個元素的微型列表。然後，以正確的順序將它們「合併」回來。效率：\(O(n \log n)\)。
快速排序法 (Quick Sort)： 選取一個「基準值 (Pivot)」。將所有小於基準值的項目放在左邊，大於的放在右邊。對左側和右側重複此過程。效率：平均為 \(O(n \log n)\)。
常見錯誤： 許多學生認為氣泡排序法很好，因為它很容易編寫。然而，面對大量數據時，它非常緩慢！
重點總結
對於大型列表，合併排序法和快速排序法通常比氣泡排序法和插入排序法快得多。
5. 搜尋與路徑搜尋演算法
我們該如何在乾草堆中尋找特定的一根針，或是找出到朋友家最快的路線？
線性搜尋 (Linear Search)： 從開頭開始，逐一檢查每個項目。效率：\(O(n)\)。
二分搜尋法 (Binary Search)： 列表必須先經過排序。查看中間的元素。你的目標項目是更大還是更小？捨棄不需要的那一半，然後重複步驟。效率：\(O(\log n)\)。
戴克斯特拉演算法 (Dijkstra’s Shortest Path)： 這可以在加權圖（如帶有距離的地圖）中找到兩點之間的最短路徑。它會持續記錄到達每個點的「成本」，並總是選擇下一個成本最低的路徑。
A* 演算法： 這是戴克斯特拉演算法的改進版本。它使用一個啟發式函數 (Heuristic)（一種基於經驗的估計）來將搜尋重點導向目標，使其速度快得多。類比：戴克斯特拉演算法就像池塘中的漣漪，向四面八方擴散；而 A* 演算法則更像是一支指向出口的手電筒。
重點總結
二分搜尋法速度很快，但要求數據必須已排序。戴克斯特拉演算法能找到絕對最短路徑，而 A* 演算法則利用額外的「猜測」（啟發式函數）來更快地找到路徑。
快速複習測驗（腦力檢查！）
1. \(O(n)\) 和 \(O(n^2)\) 哪一個比較快？
2. **二分搜尋法**的主要要求是什麼？
3. 哪種排序演算法會使用「基準值 (Pivot)」？
4. **A*** 演算法中使用的「猜測」名稱是什麼？
答案：1. \(O(n)\) 比較快。 2. 列表必須已排序。 3. 快速排序法。 4. 啟發式函數 (Heuristic)。
做得好！演算法可能會很棘手，但只要你記住基本的步驟以及它們如何隨數據規模變化（大 O），你就已經在掌握 H446 課程的道路上邁出了一大步！