comparison decision tree和延伸想法

Algo裡提到由 sort 的 comparison decision tree 可得知，任一 decision tree 都存在worst case，其下界為Omega(N*lgN)。

證明的想法很簡單，一個sorting algorithm對 n 個elements來說，會形成一個decision tree，inner nodes是比較的過程，一個由 root 往 leaf 的過程，就是一個排序演算法經歷的步驟。於是，任一 decision tree 對 n 個不同的數來說，至少會有 n! 個 leaves （因為有 n! 種排法）。依tree的性質，有 n! 個 leaves的話，高度至少為 lg(n!)，而對於任意的input來說，這個 decision tree 的高度即為比較次數的 worst case。所以 worst case比較次數的下界是：

Omega(lg(n!)) = Omega(n*lg(n))

記得我第一次看到這證明時，對 decision tree 的想法相當感動，沒想到重讀 Algo 再看到這想法時，還是一樣感動，而且發現我並沒有懂得很透徹。做過習題 8-1 後，我才覺得自己似乎又多了解一些 decision tree 的想法。

若反向思考的話，decision tree 自然也存在最矮的 leaves，也就是當每次比較剛好都能利用到上回的結果時，只要比 n-1 次即可，例如：

第一次拿到最小和次小的數、第二次拿次小和第三小的數比、．．．

那麼，有沒有可能對於任意輸入，找到最佳的比較方式呢？也就是說，這顆 decision tree 並不是固定的形式，而會依輸入的過程改變比法。比方在讀入數字後，以O(n)的時間猜測數字可能的分佈方式，來調整 decision tree 的樣子（即 sorting algorithm 的流程）。在這個想法之下，是否有較高的機率走入較短的 sorting path，而加快排序速度呢？

若能想出借用 Evolutionary Computation 或其它做法在 comparison based 下找出新解法，應該很有趣，先暫記一下這極可能失敗的想法。

或是放鬆使用的限制，在得知資料分佈下，預測比較的方式，比方預測要拿那兩個數來比，就有較高的機率找到較好的比較方式，比方一開始就找到最小和次小的數，那麼，接下來就假定不用拿最小的數來比，於是問題就變成排 n-1 個數，用數學來描述的話，就是做到：

T(n) = T(n-1) + c

上面這式子成立的話，time complexity只有 O(n) 而已。當然，加號後面要猜中才會是常數，也許有可能配合機率分析，了解比成功的機會，我想這是不錯的練習 Randomized Algorihm 的機會，有空來想看看。

ps.

1. 雖然非 comparison based 在給定數值範圍的情況下可打破 worst case的下界，但卻多了 value range 的假設，純comparison based的使用範圍更廣，畢竟只要滿足能比較兩數大小的條件而已。
2. 剛讀大學時，我對 halting problem 或這類證極限的定理有些反感，因為它們證明了「對所有情況來說，不可能有萬能解」，那麼，若對「所有情況減一」呢？很多時候我們不需要考慮所有情況。而以前思考較不清析，讀到這類問題時會被搞混，而弄錯焦點。現在看來，自己似乎有那麼一點成長，可喜可賀。
3. 習題 8.1 告訴我們，透過 comparison decision tree 的分析，符合O(n)的輸入非常少，甚至不到 n!/(2^n) 種。