Sorting Lower Bound比較排序下界

01為什麼需要它

看到這些關鍵字就想到它：還能不能更快、O(n log n) 是不是極限、決策樹、log₂(n!)、題目要求 O(n) 卻看起來需要排序、只能用比較、資訊量、下界論證。

02核心概念

比較排序指的是只能透過「比較兩個元素誰大」來了解輸入的排序演算法：泡沫、插入、合併、快速、堆積排序都是。這樣的演算法不論怎麼寫，對固定的 n 都可以畫成一棵決策樹：每個內部節點是一次比較「a < b？」，依答案走左或右；每片葉子是演算法最後輸出的一種排列順序。拿一組輸入去跑，就是從根走到某片葉子，比較次數等於那條路徑的長度，最壞情況的比較次數就是樹的高度。

證明只要數葉子。n 個相異元素有 n! 種排列，每一種需要不同的重排方式才能變成有序，所以一個正確的演算法至少要有 n! 片可以到達的葉子，否則兩種不同的輸入會走到同一片葉子、被做了同樣的重排，至少有一個排錯。高度 h 的二元樹最多只有 2ʰ 片葉子，因此 2ʰ ≥ n!，也就是 h ≥ log₂(n!)。任何比較排序在最壞情況下至少要比 ⌈log₂ n!⌉ 次。n = 3 時是 ⌈log₂ 6⌉ = 3、n = 4 時是 ⌈log₂ 24⌉ = 5。

這個量有多大：一方面 n! ≤ nⁿ，所以 log₂ n! ≤ n log₂ n；另一方面 n! 至少有 n/2 個因數不小於 n/2，所以 n! ≥ (n/2)^(n/2)，log₂ n! ≥ (n/2) log₂(n/2)。兩邊夾起來得到 log₂(n!) = Θ(n log n)，更精確的 Stirling 近似是 n log₂ n − 1.443n + O(log n)。所以比較排序的最壞情況是 Ω(n log n)，合併排序與堆積排序的最壞 O(n log n) 在漸近意義下已經最佳。平均情況也逃不掉：一棵有 n! 片葉子的二元樹，葉子的平均深度同樣至少是 log₂(n!)，因此快速排序的平均 O(n log n) 也是最佳的。

下界常被誤讀。第一，它只管比較模型：計數排序拿值當陣列索引、基數排序看數字的位數，一次操作得到的資訊遠多於一次「是或否」，所以 O(n + k)、O(d·n) 並不矛盾，只是它們要求鍵是小整數或固定寬度。第二，它說的是「所有 n! 種輸入裡最壞的那個」：如果已知輸入幾乎有序，可能的排列少得多，插入排序的 O(n + 逆序對數) 就不受這條下界限制。第三，⌈log₂ n!⌉ 不一定做得到：n = 5 時下界是 7，一般的合併與二分插入最壞要 8 次，精心設計的 merge insertion 才做得到 7，而 n = 12 已證明最少要 30 次、比下界多 1。同一套「數答案有幾種」的論證也適用其他問題：在有序陣列裡找一個數有 n + 1 種結果，所以二分搜尋的 ⌈log₂(n+1)⌉ 次也是最佳的。

03演算法步驟

1. 1確認計算模型：演算法是不是只能透過比較兩個元素來取得資訊。用了雜湊、索引或位元運算，就不在這條下界的範圍內。
2. 2數出可能的答案有幾種：排序 n 個相異元素有 n! 種，在有序陣列中搜尋有 n + 1 種。
3. 3把任一演算法畫成決策樹：每次比較有兩個分支，高度 h 的樹最多 2ʰ 片葉子，每種答案至少要佔一片。
4. 4由 2ʰ ≥ 答案數 得到 h ≥ ⌈log₂ 答案數⌉；排序就是 ⌈log₂ n!⌉ = Ω(n log n)。
5. 5需要更快時，只能改變前提：鍵是小整數就用計數或基數排序；輸入幾乎有序就用自適應的插入排序；只需要第 k 小或前 K 大，就不必完整排序。

04互動示範

選 n = 2、3、4。上方四個數字是 n!、log₂ n!、最壞情況至少要比較的次數，以及對照用的 n log₂ n；中間一排方塊是高度 h 的二元樹最多能裝幾片葉子，灰色裝不下，藍色是第一個裝得下 n! 片的高度。n = 3 時畫出一棵實際的決策樹，選一組輸入就能看它沿著黃色路徑比了幾次、落在哪片葉子：[5, 2, 9] 只比 2 次，[5, 9, 2] 要比 3 次，但沒有任何輸入超過 3 次。最下面的表把 n 放大到一百萬，log₂ n! 和 n log₂ n 的比值往 1 靠近。

05程式碼

程式碼把證明變成可以跑的數字：lower_bound 用整數精確算出 ⌈log₂ n!⌉；再寫兩個只能透過 less(x, y) 比較的排序，把 n 個元素的所有 n! 種排列都跑一遍，記下最多比了幾次。表格裡看得到兩件事：沒有任何演算法低於下界；n = 5 起，常見的演算法會比下界多一兩次，下界是「至少」而不是「剛好」。

import math
from itertools import permutations


def lower_bound(n):
    """任何比較排序在最壞情況至少要比 ⌈log₂ n!⌉ 次（用整數算，避免浮點誤差）"""
    return (math.factorial(n) - 1).bit_length()   # m ≥ 1 時 (m − 1).bit_length() = ⌈log₂ m⌉


# 兩個只能用 less(x, y) 比較的排序，用來實際數比較次數
def merge_sort(a, less):
    if len(a) <= 1:
        return a
    mid = len(a) // 2
    left, right = merge_sort(a[:mid], less), merge_sort(a[mid:], less)
    out, i, j = [], 0, 0
    while i < len(left) and j < len(right):
        if less(right[j], left[i]):
            out.append(right[j]); j += 1
        else:
            out.append(left[i]); i += 1
    return out + left[i:] + right[j:]


def binary_insertion_sort(a, less):
    out = []
    for x in a:
        lo, hi = 0, len(out)
        while lo < hi:                             # 在已排好的 out 裡二分找位置
            mid = (lo + hi) // 2
            if less(x, out[mid]):
                hi = mid
            else:
                lo = mid + 1
        out.insert(lo, x)
    return out


def worst_comparisons(sort, n):
    """把 n 個相異元素的 n! 種排列都跑一遍，回傳最多比了幾次"""
    worst = 0
    for perm in permutations(range(n)):
        count = 0

        def less(x, y):
            nonlocal count
            count += 1
            return x < y

        sort(list(perm), less)
        worst = max(worst, count)
    return worst


if __name__ == "__main__":
    for n in range(2, 9):
        print(n, lower_bound(n), worst_comparisons(merge_sort, n),
              worst_comparisons(binary_insertion_sort, n))
    # n  下界  合併  二分插入
    # 2   1    1     1
    # 3   3    3     3
    # 4   5    5     5
    # 5   7    8     8      ← 下界 7 做得到（merge insertion），這兩個演算法做不到
    # 6  10   11    11
    # 7  13   14    14
    # 8  16   17    17
    n = 10**6                                      # log₂ n! 用 lgamma 估，和 n log₂ n 比
    print(round(math.lgamma(n + 1) / math.log(2) / (n * math.log2(n)), 3))   # 0.928

06練習題

• LeetCode 217Contains Duplicate（排序 O(n log n) 對上雜湊 O(n)，後者不在比較模型裡）Easy
• LeetCode 278First Bad Version（n 種可能的答案，至少要 log₂ n 次詢問）Easy
• LeetCode 128Longest Consecutive Sequence（要求 O(n)，所以不能先排序）Medium
• LeetCode 164Maximum Gap（要求線性時間，用鴿籠原理分桶）Medium
• LeetCode 41First Missing Positive（把值當索引，跳出比較模型）Hard