複雜度、排序與搜尋：從輸入形狀推導成本
本頁為依教材與考古題整理的原創摘要；考古題答案經技術覆核，但不是官方答案。
考古題證據邊界： 複雜度分析在現有 canonical metadata 中沒有 direct primary 考古題；本課的考古題直接支撐排序與搜尋，複雜度部分由 reviewed MIT 6.006 課程內容補足，不把相鄰題冒充直接出題證據。
第一次接觸也沒關係
這堂先懂這些詞
先記住白話意思，不必急著背英文。看到正文時，再把正式名稱接回來。
大 O 複雜度
也會看到：Big O、time complexity、O(n)、時間複雜度描述輸入變大時，演算法所需時間或空間的成長速度。
- 生活例子：
- 排 10 人與排 1 萬人時，工作量增加多快比小規模快幾秒更重要。
- 別搞混：
- Big O 不是精確秒數，也不能忽略資料規模與常數成本。
二分搜尋
也會看到：binary search、二元搜尋在已排序資料中反覆排除一半範圍來找目標。
- 生活例子：
- 猜 1 到 100 的數字，每次猜中間並問較大或較小。
- 別搞混：
- 資料若未排序，不能直接套二分搜尋得到正確結果。
快速排序的分割
也會看到：QuickSort、partition、pivot選一個基準值，把較小與較大的元素分到兩側，再遞迴處理。
- 生活例子：
- 像選一位身高作基準，矮的站左邊、高的站右邊，再各自重排。
- 別搞混：
- 若每次分割極不平均，QuickSort 最壞可能退化為 O(n²)。
排序穩定性
也會看到：stable sort、sorting stability排序鍵相同的資料，排序後仍保持原本先後次序，就稱為穩定。
- 生活例子：
- 先按報名時間排好，再依組別做穩定排序，同組內仍保留報名先後。
- 別搞混：
- 穩定性描述相同鍵的相對順序，不等於排序結果一定正確或速度較快。
以輸入規模與基本操作次數建立 Big-O、Omega、Theta，再用 Bubble Sort 與 QuickSort 分析 best/worst case、提前停止與穩定性，最後整理搜尋演算法成立所需的資料前提。對應考古題答案均為非官方技術覆核。
先抓住這幾件事
- 區分 Big-O、Omega、Theta，以及 best/average/worst case 的不同問題。
- 由迴圈與比較次數推導 Bubble Sort 的 O(n) best case 與 O(n²) worst case。
- 說明 QuickSort 的 partition 結構，以及不平衡切分為何造成 O(n²)。
- 判斷排序穩定性，並說明 binary search 等搜尋方法的前置條件。
先想像這個場景
圖書館閉館前的還書大整理
閉館前，館員要把 n 本還書依索書號排回推車。有人逐本比較相鄰書，有人挑一本當分界把書分到兩側；整理完後，讀者還想快速找到指定索書號。真正決定成本的，不只是『哪個方法聽起來快』，而是輸入原本的形狀、分界怎麼選，以及書是否已按同一規則排好。
先別急著往下看，花十秒想一想：
推車上的書早已依索書號排好。相鄰比較法若每一趟都記錄是否交換，第一趟完全沒交換後應怎麼做？
把故事換成電腦語言
| 生活中的角色 | 對應到 | 技術概念 |
|---|---|---|
| 還書數量是 n，館員把一次索書號比較或交換當成要計數的工作 | Input size、基本操作與漸近界 | |
| 館員反覆比較相鄰兩本，順序相反就交換；一整趟沒交換便停止 | Optimized Bubble Sort | |
| 館員挑一本分界書，把較小與較大的書分到兩車後繼續處理 | QuickSort partition 與 pivot quality | |
| 兩本索書號相同的預約書貼有『先到 A』『後到 B』，整理後仍保留 A 在 B 前 | Stable sort | |
| 書確實按索書號排列後，館員每次查看中間一本並排除一半範圍 | Binary search 的前置條件 |
題目出現這些字，先想到
- 題目只寫 O(n²) 或問 best/worst case：先確認 n、基本操作、輸入形狀與實作版本；case 與 O/Omega/Theta 不是同義詞。
- Bubble Sort 題目出現『已排序』『沒有交換就停止』：有 swapped flag 才能推出 best-case Theta(n)；固定輪數版本不能。
- QuickSort 遇到已排序輸入：檢查 pivot selection；每次選極端值才會一路切成 0 與 n-1。
- 題目問 stable 或 binary search：Stable 只管 equal keys 的相對順序；binary search 先驗證排序與 random/indexed access 前提。
1.先定義 n、操作與 case
演算法的時間複雜度（time complexity）衡量的是「隨著輸入規模 n 增長，演算法需要的基本操作次數如何增長」。用 Big-O 記號表示上界（worst case 的增長速度）。 【定義 n】n 是輸入的規模，具體定義取決於問題。排序問題中 n 是元素數量；圖演算法中 n 可能是節點數 V 或邊數 E；字串演算法中 n 是字串長度。 【常見複雜度等級（由快到慢）】 • O(1)：常數時間，和輸入規模無關。例如存取陣列中的第 i 個元素。 • O(log n)：對數時間，每次操作把問題規模減半。例如 binary search。 • O(n)：線性時間，需要看過每個元素一次。例如線性搜尋。 • O(n log n)：最佳比較排序的下界。例如 merge sort、heap sort。 • O(n²)：二次方時間。例如 bubble sort、selection sort、insertion sort 的 worst case。 • O(2ⁿ)：指數時間，通常只適用於很小的 n。例如暴力枚舉子集。 【Best / Average / Worst case】同一個演算法在不同輸入下可能有不同的表現。例如 insertion sort 在已排序的陣列上是 O(n)（best case），但在反向排序的陣列上是 O(n²)（worst case）。Big-O 通常描述 worst case。Big-Ω 描述 lower bound（best case），Big-Θ 描述 tight bound（當 O 和 Ω 相同時）。 【空間複雜度】除了時間，也要考慮演算法需要的額外記憶體。In-place 演算法只需要 O(1) 額外空間（如 quicksort 的 partition），而 merge sort 需要 O(n) 額外空間。 【考試連結】最常考的題型：(1) 給定程式碼（通常是巢狀迴圈），判斷時間複雜度。(2) 比較不同排序演算法的複雜度。(3) 從給定的 Big-O 判斷能否在時限內處理特定規模的輸入。
- 忽略常數與低階項是為了比較成長率，不代表實際執行時間完全相同。
- O(n²) 是上界敘述；若同時可證明 Omega(n²)，才能寫成 Theta(n²)。
- Best/worst case 必須說明輸入形狀，例如已排序、逆序或 pivot 每次極端不平衡。
- 比較兩個演算法時，除了時間也要看額外空間、穩定性與輸入前提。
2.Bubble Sort：相鄰交換與提前停止
Bubble Sort 是最直覺的排序演算法：反覆掃描陣列，比較相鄰的兩個元素，如果順序錯誤就交換。每一輪掃描（pass），最大的未排序元素會像氣泡一樣「浮」到正確位置。 【運作機制】以升序排列 [5, 3, 8, 1, 2] 為例： Pass 1：比較 (5,3)→交換→[3,5,8,1,2]；(5,8)→不換；(8,1)→交換→[3,5,1,8,2]；(8,2)→交換→[3,5,1,2,8]。最大值 8 到位。 Pass 2：比較 (3,5)→不換；(5,1)→交換→[3,1,5,2,8]；(5,2)→交換→[3,1,2,5,8]。第二大值 5 到位。 如此重複，直到整個陣列排序完成。 【提前停止優化】如果某一輪 pass 中沒有發生任何交換，表示陣列已經完全排序，可以提前結束。這使得 best case（已排序的陣列）的複雜度降為 O(n) — 只需要掃一遍確認沒有交換。 【複雜度分析】 • Worst case：O(n²) — 反向排序的陣列，每一輪都需要交換。 • Best case：O(n) — 已排序的陣列（加入提前停止優化）。 • Average case：O(n²)。 • 空間複雜度：O(1)（in-place）。 • 穩定性：穩定（stable）— 相等元素的相對順序不會改變，因為只有嚴格大於時才交換。 【考試連結】Bubble sort 是考古題最常出現的排序演算法，通常要你(1) 手動執行幾個 pass 寫出中間結果，或 (2) 判斷最壞情況下需要幾次比較。n 個元素最壞需要 n(n-1)/2 次比較。
- 沒有 swapped flag 的固定輪數版本，即使已排序也可能執行 Theta(n²)。
- 只在 left > right 時交換，可保留相等元素的相對順序，因此標準 Bubble Sort 是 stable。
- 每一趟結束後，至少一個極值進入最終位置。
- 題目若說『若尚未排序才繼續』，通常暗示存在提前停止檢查。
Bubble Sort 對已排序陣列 [1,2,3,4,5] 執行：有 swapped flag 時需要幾輪？沒有時呢？
3.QuickSort：切分品質決定遞迴深度
QuickSort 使用 divide-and-conquer 策略：選一個 pivot（基準值），把陣列分成「小於 pivot」和「大於 pivot」兩部分（partition），然後對兩部分遞迴排序。 【Partition 機制】選定 pivot 後（常用最後一個元素、隨機元素或 median-of-three），掃描陣列把元素分成兩組：≤ pivot 的放左邊，> pivot 的放右邊。Partition 結束後，pivot 就在它最終的正確位置。 【具體範例】排序 [7, 2, 1, 6, 8, 5, 3, 4]，選 pivot = 4： Partition 後：[2, 1, 3, 4, 8, 5, 7, 6]。4 在正確位置（index 3）。 遞迴排序左半 [2, 1, 3] 和右半 [8, 5, 7, 6]。 【複雜度取決於 pivot 選擇品質】 • Best case：每次 pivot 恰好是中位數，把陣列等分。遞迴深度 O(log n)，每層 O(n) 比較。總計 O(n log n)。 • Worst case：每次 pivot 是最大或最小值（例如已排序的陣列用最後元素做 pivot），一邊 0 個元素、另一邊 n-1 個。遞迴深度 O(n)，總計 O(n²)。 • Average case：O(n log n)。隨機化 pivot 選擇可以讓 worst case 出現的機率極低。 【空間複雜度】In-place partition 不需要額外陣列，但遞迴呼叫需要 call stack 空間：best case O(log n)、worst case O(n)。 【穩定性】QuickSort 不是穩定排序 — partition 過程中可能改變相等元素的相對順序。 【考試連結】(1) 手動執行 partition 過程是常見題型。(2) 常考 QuickSort worst case 出現的條件。(3) 比較 QuickSort 和 MergeSort — QuickSort 通常更快（cache 友善，常數因子小），但 worst case 更差且不穩定。
- 已排序資料不必然讓所有 QuickSort 變慢；是否退化取決於 pivot/partition 策略。
- Randomized pivot 或較穩健的 pivot selection 可降低反覆極端切分的機率，但不消除理論 worst case。
- 常見 in-place partition 會讓相等元素跨位置交換，因此 QuickSort 通常不 stable。
- QuickSort 是 divide-and-conquer；partition 正確性與遞迴邊界同樣重要。
QuickSort 對已排序陣列一定會退化到 O(n²) 嗎？
4.穩定性與搜尋前提
【排序的穩定性】穩定排序（stable sort）保證：當兩個元素的排序鍵相同時，它們在排序後的相對順序和排序前一致。例如按成績排序學生名單，兩個都是 90 分的學生在排序後的前後順序和原來一樣。 穩定排序：Bubble Sort、Insertion Sort、Merge Sort、Counting Sort、Radix Sort。 不穩定排序：Selection Sort、Quick Sort、Heap Sort。 穩定性在「多鍵排序」時特別重要：先按姓名排序，再按成績排序。如果第二次排序是穩定的，那麼成績相同的學生仍按姓名排序。如果不穩定，姓名順序可能被打亂。 【各排序演算法比較表】 | 演算法 | Best | Average | Worst | 空間 | 穩定？ | | Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | ✓ | | Insertion Sort | O(n) | O(n²) | O(n²) | O(1) | ✓ | | Selection Sort | O(n²) | O(n²) | O(n²) | O(1) | ✗ | | Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | ✓ | | Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) | ✗ | | Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | ✗ | 【Binary Search 前提】Binary Search 要求陣列已排序。步驟：比較中間元素和目標值，如果目標值較小就搜尋左半，較大就搜尋右半。每次把搜尋範圍減半，所以時間複雜度是 O(log n)。如果陣列未排序，只能用線性搜尋 O(n)。 【考試連結】(1) 排序穩定性是常考選擇題。(2) 常考「以下哪個排序最壞情況仍是 O(n log n)」→ Merge Sort 和 Heap Sort。(3) Binary Search 的前提條件（已排序）和每次比較後搜尋範圍如何縮小。
- 穩定性只約束 equal keys，不表示排序結果唯一或演算法一定較快。
- Merge Sort 是否 stable 取決於 merge 遇到相等值時是否先取左側元素。
- Binary search 每步排除約一半範圍，時間為 O(log n)，但前提不成立時答案不可靠。
- 字串搜尋的 input size 可能同時包含 text length 與 pattern length，分析前要先定義符號。
一起拆題目
範例 1：用 Bubble Sort 將逆序陣列 [5,4,3,2,1] 由小到大排序。若每輪縮短已定位尾端，總共做多少次相鄰比較？這支持什麼量級？
- 第一輪比較 4 次，將 5 推到最右端。
- 後續三輪分別比較 3、2、1 次。
- 總比較數為 4+3+2+1=10，也就是 n(n-1)/2 在 n=5 的值。
- 一般 n 的主導項是 n²/2，因此 worst case 為 Theta(n²)。
所以答案是：共 10 次比較；一般化為 n(n-1)/2，所以是 Theta(n²)。
範例 2：最佳化 Bubble Sort 以 swapped flag 記錄一輪中是否交換。輸入 [1,2,3,4,5] 時會執行幾輪、幾次比較？
- 第一輪依序比較四組相鄰元素。
- 因陣列已排序，不會發生任何交換，swapped 保持 false。
- 演算法在第一輪後立即停止，不再執行剩餘輪次。
所以答案是：執行 1 輪、4 次比較；一般 n 是 n-1 次比較，因此 best case 為 Theta(n)。
範例 3：QuickSort 每次選子陣列第一個元素為 pivot，輸入 [1,2,3,4,5]。請說明子問題大小與 worst-case 成本。
- 第一個 pivot=1 是最小值，切成大小 0 與 4。
- 下一層 pivot=2，再切成大小 0 與 3，之後依序為 2、1。
- 每層 partition 仍掃描當前子陣列，工作量近似 4+3+2+1。
- 一般化 recurrence 為 T(n)=T(n-1)+Theta(n)，解為 Theta(n²)。
所以答案是：切分一路為 0 與 n-1，遞迴深度線性，總成本 Theta(n²)。這是指定 pivot 策略下的結果，不代表所有已排序輸入都必然退化。
範例 4：Records 為 [(2,A),(1,X),(2,B)]，只依第一欄由小到大排序。Stable sort 與可能的 unstable sort 結果有何差異？
- 兩筆 key=2 的原始順序是 A 在 B 前。
- Stable sort 必須保留 equal-key records 的相對順序。
- 因此 stable 結果是 [(1,X),(2,A),(2,B)]。
- Unstable sort 可能產生 [(1,X),(2,B),(2,A)]，雖然 key 仍已排序。
所以答案是：Stable 結果必須維持 A 在 B 前；unstable 演算法不保證這個次序。
這裡最容易選錯
- 把 Big-O 當成精確等號，或把 worst case 直接當成 Big-O 的定義。
- 未確認 Bubble Sort 是否有提前停止，就一律宣稱 best case O(n)。
- 認為排序輸入一定讓 QuickSort O(n²)，忽略 pivot selection。
- 把 stable 誤解為不會改動資料；它只保證 equal-key records 的相對順序。
- 在未排序資料上直接使用 binary search。
- 只寫複雜度結論，沒有定義 n、基本操作與輸入 case。
換你快速判斷
先在心中作答，再展開答案。答不出來時，回頭找本課的對照關係。
1Big-O 與 worst case 是同一件事嗎？
不是。Big-O 描述漸近上界；worst case 是固定 input size 下成本最大的輸入情況。可以對 best、average 或 worst-case function 分別給 Big-O。
分析前要先定義 case，再對該成本函數給 O、Omega 或 Theta bound。
2Bubble Sort 的 worst-case 比較次數與複雜度為何？
逆序等 worst-case 輸入約比較 (n-1)+(n-2)+…+1=n(n-1)/2 次，因此是 Theta(n²)。
每輪把一個極值推到最終位置，未定位區間逐輪縮短。
3何時 Bubble Sort 的 best case 是 Theta(n)？
實作有 swapped flag／提前停止，而且輸入已排序時；第一輪 n-1 次比較沒有交換即可結束。
若固定執行所有輪次、沒有 early termination，已排序輸入仍可能是 Theta(n²)。
4QuickSort 何時會退化為 Theta(n²)？
每次 partition 都極端不平衡，只切出大小 0 與 n-1 的子問題時。
此時 T(n)=T(n-1)+Theta(n)。已排序輸入是否觸發退化，取決於 pivot strategy。
5Stable sort 保證什麼？
排序 key 相等的 records 在輸出中維持原本的相對順序。
穩定性不表示演算法不移動資料，也不直接代表時間複雜度較好。
6Insertion、Merge、Bubble、QuickSort 中，哪一個典型實作不保證 stable？
QuickSort。典型 in-place partition 可能交換跨越 pivot 的 equal-key records。
Insertion、stable merge 與只交換嚴格逆序相鄰元素的 Bubble Sort 可保留 equal-key 次序。
7何時可以把 T(n) 寫成 Θ(f(n))，而不只寫 O(f(n))？
當 T(n) 同時具有漸近上界 O(f(n)) 與漸近下界 Ω(f(n)) 時，才能寫成緊確界 Θ(f(n))。
O 只保證成長不會漸近超過某個上界，可能並不緊；Θ 則要求同一個 f(n) 同時夾住上界與下界，因此更精確描述成長階。
8做複雜度分析前，為什麼要先定義 input size n 與基本操作？
因為複雜度描述的是特定成本隨輸入規模成長的函數；n 的定義或被計數的操作不同，得到的成本函數也可能不同。
例如圖演算法常同時使用 |V| 與 |E|，字串搜尋則可能分別使用文字與樣式長度。若未先說明 n 和成本單位，單寫 O(n) 無法形成可比較、可檢驗的分析。
最後用考古題驗證
本課連結的題目都已通過可重現的技術覆核，可逐題練習與判分。
開始本課考古題練習參考來源
- Introduction to Algorithms (6.006) — Erik Demaine and Srini Devadas