2010年9月17日 星期五

[Algo] 8.1 Lower bounds for sorting

Comparison sorts
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$

沒有留言:

張貼留言