跳轉到

2.2 排序與搜尋的多項式演算法#

概念說明#

排序與搜尋是電腦科學最基礎的兩個問題，也是展示「多項式時間演算法」最典範的材料。排序問題的定義是：給定 n 個可比較的元素，將其由小到大重新排列。搜尋問題則是：在已排序（或未排序）的集合中，找出特定元素或其位置。

這兩個問題看似平凡，但它們是理解 P 類問題的最佳教材，原因有三：

  1. 它們有多個不同策略的演算法，複雜度從 O(n²) 到 O(n log n) 再到特殊情況下的 O(n)，讓我們能具體比較「多項式時間演算法之間也有優劣」。
  2. 排序的 O(n log n) 下界證明了「存在多項式時間演算法」不代表「可以無限加速」，這是複雜度理論的重要思維。
  3. 排序是許多進階演算法（包括後面的近似演算法、貪婪啟發式）的子程序。

值得注意的是：排序問題的輸入是排好序後立刻可以驗證的（檢查相鄰元素是否遞增需要 O(n)），而「找一個好的排法」的搜尋空間是 n! 種排列，但我們從不碰運氣——我們總有多項式時間的演算法直接構造答案。這正是 P 類問題的精神。

演算法步驟#

氣泡排序（O(n²)）#

  1. 重複掃描陣列，比較相鄰兩元素，若逆序則交換。
  2. 每一輪結束後，最大元素沉到最右端，下一輪可少掃一個位置。
  3. 直到某輪沒有交換發生或掃完 n−1 輪。

合併排序（O(n log n)）#

  1. 分解：將陣列切成兩半。
  2. 遞迴對兩半分別排序。
  3. 合併：用雙指標逐一比較兩個已排序子陣列的頭元素，較小者輸出，直到全部合併。

二分搜尋（O(log n)）#

  1. 在已排序陣列上，比較目標與中間元素。
  2. 若目標較大，丟棄左半；較小，丟棄右半；相等則找到。
  3. 重複至範圍為空。

Python 程式碼範例#

import random, time

def bubble_sort(a):
    a = a[:]
    n = len(a)
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
                swapped = True
        if not swapped:
            break
    return a

def merge_sort(a):
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    left, right = merge_sort(a[:mid]), merge_sort(a[mid:])
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            out.append(left[i]); i += 1
        else:
            out.append(right[j]); j += 1
    out += left[i:] or right[j:]
    return out

def binary_search(a, x):
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if a[mid] == x:
            return mid
        elif a[mid] < x:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

# 實測
for n in [1000, 4000, 16000]:
    data = [random.randint(0, n) for _ in range(n)]
    t0 = time.perf_counter(); bubble_sort(data); t1 = time.perf_counter()
    t2 = time.perf_counter(); result = merge_sort(data); t3 = time.perf_counter()
    print(f"n={n:>6}  bubble={t1-t0:8.4f}s  merge={t3-t2:8.4f}s")

s = merge_sort([3, 1, 4, 1, 5, 9, 2, 6])
print("排序後:", s, "  二分搜尋 5 的位置:", binary_search(s, 5))

執行結果會顯示：n 擴大 4 倍時，氣泡排序時間約成長 16 倍（平方特徵），而合併排序只成長約 4～5 倍（n log n 特徵）。

複雜度分析#

演算法 最壞時間 額外空間 備註
氣泡排序 O(n²) O(1) 簡單但慢，僅教學用
合併排序 O(n log n) O(n) 穩定、最壞情況保證好
快速排序 平均 O(n log n)，最壞 O(n²) O(log n) 實務上常最快
線性搜尋 O(n) O(1) 未排序資料只能如此
二分搜尋 O(log n) O(1) 需先排序

另外必須提一個漂亮定理：任何以比較為基礎的排序演算法，最壞情況都至少需要 Ω(n log n) 次比較。證明用決策樹：n 個元素有 n! 種排列，深度 d 的二元決策樹至多有 2^d 個葉子，故需 2^d ≥ n!，得 d ≥ log₂(n!) = Θ(n log n)。這說明合併排序已達到漸近最優，不是可以無限改進的——複雜度分析不只是求上界，也能證明下界。

練習#

  1. 修改 merge_sort，讓它在子陣列長度小於 32 時改用插入排序（實務上常見的混合策略），並用實驗比較它與純合併排序、Python 內建 sorted() 的速度。
  2. 「找出陣列中第 k 小的元素」可以用排序解決（O(n log n)），請實作。再查閱並實作快速選擇（quickselect）的期望 O(n) 演算法，比較兩者在 n = 100000、隨機輸入下的執行時間。
  3. 證明：若排序偏偏不需要「比較」（例如整數範圍在 [0, n²) 內），計數排序可以做到 O(n)。並思考：為什麼計數排序不違反 Ω(n log n) 下界？（提示：下界只對比較式演算法成立。）