按比較排序的低位限制

Question

今天我正在閱讀Julienne Walker關於排序的一篇很棒的文章 - Eternally Confuzzled - The Art of Sorting，有一件事引起了我的注意。我不太明白的部分在這裏筆者證明，通過比較排序，我們被限制Ω（ñ·登錄ñ）下界

下界並不明顯。大多數排序算法的最低限度是Ω（N·log N）。這是因爲大多數排序算法使用項目比較來確定項目的相對順序。任何通過比較排序的算法都將具有Ω的最小下界（N·log N），因爲使用比較樹來選擇排序的排列。對於三個數字1，2的比較樹，和圖3能夠容易地構成：

      1 < 2 

      1 < 3      1 < 3 

    2 < 3   3,1,2  2,1,3   2 < 3 

1,2,3 1,3,2       2,3,1  3,2,1 

通知每個項目是如何與每個其它項目相比較，並且每個路徑的結果的三個項的有效排列。樹的高度決定排序算法的下限。因爲有排列的算法是正確的，必須有儘可能多的葉子，比較樹的最小可能高度登錄ñ！，這相當於Ω（ñ·登錄ñ） 。

這似乎是一個非常合理的，直到最後一部分（粗體），我不太明白 - 怎麼登錄ñ！相當於Ω（N·log N）。我必須錯過我的CopmSci課程中的一些東西，無法獲得最後的轉換。如果我們使用排序方式進行比較，我期待這方面的幫助或與其他證據有關的其他證據的鏈接（N·log N）。

Answer 1

您沒有錯過CompSci課程的任何內容。你錯過的是數學課。斯特林近似的Wikipedia頁面顯示log n！是漸近的n log n +低階項。

Answer 2

• N！ < N^N
• ∴log N！ < log（N^N）
• ∴log N！ < N * log N

由此，可以證明θ（log N！）= O（N log N）。對於Ω來說證明是一樣的，這是對讀者的一個練習，或者對於mathematics stackexchange或theoretical computer science stackexchange的問題。

Answer 3

我最喜歡的證明是非常基本的。

N！ = 1 * 2 * .. * N - 1 * N

假設這些產品的前半部分不存在，我們可以很容易的下界，然後下半部分都是N/2 。

（N/2）^（N/2）< = N！（N/2）^（N/2）= N/2 * log（N/2）= N/2 *（log（N）-1）= O（n log n）

所以，即使你只表達下半部分，假設所有這些因素都不大於N/2，你仍然處於O（n log n）領域的下界，這是超級基本的。我可以說服一個普通的高中生，我甚至不能自己推導出斯特林的公式。