我們在此之前討論的各種sort，都可以說是comparison sorting，因為我們判斷元素要在前面或後面都是透過compare這個動作來決定。這章節要探討comparison sorting的極限，並用數學來證明。

• prove log(N!) ∈ Θ(N logN), this means these two equations got the same growing rate

一開始先證明log(N!) ∈ Ω(N logN)，然後接著證明N log(N) ∈ Ω(log(N!))，所以這樣照邏輯來說就導向以下結果：

• is there a better sorting algorithm that can beat N log N?

首先來盤整一下目前所知的情況。假設有一個終極comparison sort方法，這邊稱它為TUCS(The Ultimate Comparison Sort)，我們可以定義它最爛最爛應該也要有O(N log(N))，因為我們已經確定有方法可以達到N log(N)了；那最好呢？不論一切可能性，Ω(1)就是最頂的了，但這是很弱的論述，也毫無根據：

能不能找個比Ω(1)更有說服力的論證？有的，就是Ω(N)，不論如何總得要遍歷所有元素吧？就算只遍歷一半，那也是Ω(N)。不過這也是很粗淺的論述，有沒有更強而有力的證明呢？有的，就在下一的段落的decision tree證明。

• puppy, cat, dog decision tree （動物箱遊戲）

  

  

  

在分析完三個元素的decision tree後，我們來想想若4個元素的話decision tree會有幾層呢：

接著我們把這個模式generalized：

• comparison logic:

我們看似解決了動物箱遊戲，但其實有一個最佳的辦法來解決，那就是sort！我們在不曉得每個箱子裡面是什麼動物時，直接根據箱子的大小來sort，只要sort完自然就知道答案了！

所以可以說動物箱遊戲其中一個解答是用sorting，反過來說動物箱遊戲的lower bound(Ω的感覺，有某個解，但可能更耗時)也會是sorting的lower bound！(有點難懂，但關鍵在於範圍跟Ω，因為動物箱遊戲是範圍更廣的問題，所以自然也可以成為另一個更狹窄問題的lower bound)：

所以我們把動物箱遊戲的lower bound Ω(log(N!))套到TUCS的lower bound：

又一開始已經證明log(N!) ∈ Ω(N logN)，所以我們得證comparison sorting除了是O(N log(N))，同樣也是Ω(N logN)！

但是sorting其實不一定只能用comparison，若用其他方式可能可以比O(N logN)更快～下一章節會介紹。

Slides are from Josh Hug CS61B

This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License