merge sort, heapsort, ... 以及我們之前所看過的許多 sorting algorithm，都有一個共同的特色：the sorted order they determine is based on comparisons between the input elements。這些 sorting algorithm 因此被稱為 comparison sorts。往下我們將會證明任何的 comparison sort 的 worst case 一定得花費 $\Omega(n \lg n)$ 這麼多的時間。
在這個 section，我們將會假設 input elements 都是相異的，沒有任兩個 elements 是相同的。根據這個假設，我們也假設所有 comparison 的方法都是這樣的形式： $a_i \leq a_j$。這也是唯一可以獲得兩個 elements 他們之間的資訊的唯一 operation。
The decision-tree model
A decision tree is a full binary tree that represents the comparisons between elements that are performed by a particular sorting algorithm operating on an input of a given size.
decision tree model 是所有 comparison sort 的 abstraction。一旦給定了某個 sorting algorithm 以及某個 input 的長度，那這棵 decision tree 也就跟著確定了。
上面那張圖是個 insertion sort 排序 3 個 elements 的 input array 的 decision tree，每個 non-leaf node 以 $i:j$ 表示 $a_i$ 跟 $a_j$ 在做 comparison，其中的 $i:j$ 是指他們的 original position，我們忽略 data movement 的影響。每個 leaf 都會標示 $\langle \pi(1), \pi(2), \ldots , \pi(n) \rangle$，以代表 $a_{\pi(1)} \leq a_{\pi(2)} \leq \ldots \leq a_{\pi(n)}$ 的排序結果。對一個長度為 n 的 array 執行 sorting algorithm 就對應到一條從 root 往下 trace 到某個 leaf 的 path，不同的 input 就對應到不同的 path。
因為長度為 n 的 input array，總共有 $n!$ 種的排列組合，而且每一個排列組合都必須對應到一個 leaf，所以我們知道這棵 decision tree 的 leaves 必須大於 $n !$ 個
A lower bound for the worst case
首先，我們知道任何 height 為 h 的 binary tree 的 leaves 最多就是 $2^h$ 個。然後我們必須瞭解到最長的 path 對應到這個 sorting algorithm 的 worst-case，接下來我們引進一個定理：
Theorem 8.1
Any comparison sort algorithm requires $\Omega(n \lg n)$ comparisons in the worst case.
Proof: 假設有一棵 height 為 h 的 decision tree 有 l 個 reachable leaves，因為我們知道$n!$ 種的排列組合都必須對應到一個 leaf，所以我們可以得到 $n! \leq l$，再來因為任何 height 為 h 的 binary tree 的 leaves 最多就是 $2^h$ 個，所以我們又可以得到 $n! \leq l \leq 2^h$，因此我們知道 $h \geq \lg(n!) = \Omega(n \lg n)$。$\blacksquare$
Corollary 8.2
Heapsort and merge sort are asymptotically optimal comparison sorts.
Proof: 前面我們已經知道 heapsort 以及 merge sort 有 $O(n \lg n)$ 的 upper bound，根據 Theorem 8.1，我們知道他們都有 $\Omega(n \lg n)$ 的 lower bound，故得證。$\blacksquare$
沒有留言:
張貼留言