今天我正在閱讀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)。
+1。神奇的詞是「斯特林的近似」。 – Nemo