(Day 13) 選擇排序 (Selection Sort)
選擇排序 (Selection Sort) 是一種簡單直觀的排序演算法。核心概念: 每一輪從尚未排序的元素中挑出最小（或最大）者，放到目前應在的位置，一直重複直到完成。可以把它想成「選拔賽」: 第一輪選出最優放第一名，第二輪從剩下的人選次優放第二名，依此類推。
(Day 11) 演算法評估 (Algorithm Analysis)
目錄
到目前為止，我們已經介紹了各種資料結構 (Array、Linked List、Stack、Queue、Tree、Graph)，也練習了基本操作。但光有資料結構還不夠，要能設計演算法，就必須懂得如何評估一個演算法的效率。
這篇我們要正式進入演算法分析 (Algorithm Analysis)，也就是回答以下問題:
- 這個演算法在不同輸入規模下，執行需要多少時間?
- 這個演算法需要多少額外的記憶體?
- 在實務上，它和其他解法相比誰更好?
為什麼要分析演算法?
在軟體工程或面試中，我們常聽到: 「時間複雜度是多少?」、「能不能把 $O(n^2)$ 降到 $O(n \log n)$?」這些問題的本質就是演算法效率。
舉例:
- 排序一百萬筆資料，$O(n^2)$ 的冒泡排序會慢得無法接受，而 $O(n \log n)$ 的快速排序可以在合理時間內完成。
- 查詢資料時，用 Array 遍歷 ($O(n)$) 與用 Hash Table 查找 ($O(1)$ 平均) 的差異，會直接影響效能。
所以，演算法分析的目的不是「找最炫的解法」，而是在輸入規模變大時，哪個演算法更可擴展 (scalable)。
時間複雜度 (Time Complexity)
時間複雜度衡量的是: 隨著輸入規模 $n$ 增加，演算法所需步驟數量的增長率。 這裡不考慮硬體速度、編譯器優化，而是純粹從數學角度來看，常用的表示法是 Big-O 表示法:
- $O(1)$: 常數時間，輸入大小不影響效率。
- $O(\log n)$: 對數時間，每次將問題縮小一半，例如二分搜尋。
- $O(n)$: 線性時間，遍歷所有元素，例如尋找最大值。
- $O(n \log n)$: 接近線性的複雜度，例如快速排序、合併排序。
- $O(n^2)$: 平方時間，例如雙層迴圈。
- $O(2^n)$: 指數時間，例如遞迴解 NP 問題。
- $O(n!)$: 階乘時間，例如旅行推銷員的暴力解法。
常見範例
$O(1)$ – 常數時間
def get_first_element(arr):
return arr[0]
無論陣列多大，只取第一個元素，時間固定。
$O(n)$ – 線性時間
def find_max(arr):
max_val = arr[0]
for num in arr:
if num > max_val:
max_val = num
return max_val
需要遍歷所有元素，步驟數與 $n$ 成正比。
$O(n^2)$ – 平方時間
def bubble_sort(arr):
n = len(arr)
for i in range(n):
for j in range(0, n-i-1):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
return arr
雙層迴圈，每增加一倍輸入，執行時間大約變四倍。
$O(\log n)$ – 對數時間
def binary_search(arr, target):
left, right = 0, len(arr)-1
while left <= right:
mid = (left + right) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
每次將搜尋範圍縮小一半。
$O(n \log n)$ – 高效排序
例如 Merge Sort 與 Quick Sort，是大多數排序演算法的效率極限。
def merge_sort(arr):
if len(arr) <= 1:
return arr
mid = len(arr)//2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return merge(left, right)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
result.append(left[i]); i+=1
else:
result.append(right[j]); j+=1
result.extend(left[i:])
result.extend(right[j:])
return result
空間複雜度 (Space Complexity)
除了時間，演算法也需要額外的記憶體。
- $O(1)$ 空間: 不隨輸入增加，僅用固定變數 (例如最大值搜尋)。
- $O(n)$ 空間: 需要與輸入相同規模的額外空間 (例如複製陣列)。
- $O(n^2)$ 空間: 常見於動態規劃表格 (例如 Floyd-Warshall 最短路徑)。
範例:
- 遞迴函式: 需要額外的呼叫堆疊 (stack space)。
- Merge Sort: 需要額外 $O(n)$ 空間。
- Quick Sort: 平均 $O(\log n)$ stack space，最壞 $O(n)$。
演算法效率比較表
| 複雜度 | 範例 | 適用情境 |
|---|---|---|
| $O(1)$ | Hash 查詢 | 即時查找 |
| $O(\log n)$ | Binary Search | 有序資料快速查詢 |
| $O(n)$ | 遍歷陣列 | 單次掃描 |
| $O(n \log n)$ | Merge Sort, Quick Sort | 高效排序 |
| $O(n^2)$ | Bubble Sort, Floyd-Warshall | 小規模輸入 |
| $O(2^n)$ | Subset/Knapsack 遞迴解 | 小輸入 NP 問題 |
| $O(n!)$ | 全排列, TSP 暴力解 | 幾乎不可行 |
LeetCode
- LeetCode 1. Two Sum → $O(n)$ 解 vs $O(n^2)$ 解
- LeetCode 704. Binary Search → $O(\log n)$
- LeetCode 912. Sort an Array → $O(n \log n)$
結語
演算法分析是理解程式效率的核心能力。
- 時間複雜度: 幫助我們估計在不同輸入規模下演算法的表現。
- 空間複雜度: 幫助我們衡量記憶體需求。
- Big-O 表示法: 則提供一個標準化語言來比較演算法。
理解這些概念後，我們就能判斷什麼時候該用哪種資料結構或演算法，這不僅是面試必考，也是設計高效程式的基礎。