2014-10-28 83 views

回答

5

如果只能比較(檢查兩個項目是否爲<,>,==),那麼排序的值就不會比O(n log(n))做得更好。它是那裏算法的幾個經證實的下界之一。證明不是太複雜(查看維基百科上的比較排序以瞭解詳細信息),但足夠長時間不在這裏重複。

如果您可以做比較之外的事情,那麼您可以擁有更多的靈活性。如果你有數字,你可以檢查桶排序(一種基數排序),它可以使O(n)排序成爲可能。

+0

+1用於引用存儲區排序。 O(n log n)的下界僅適用於基於比較的排序算法。 – 2014-10-28 22:44:10

1

簡短的回答是否定的。

如果輸入數組的每個元素都屬於一個有限集合,那麼O(N)算法是可能的。假設輸入總是在有限集[0..9]內。然後你可以創建一個大小爲10的數組,掃描數組並增加相應的索引。

所以,在所有情況下,O(N)排序算法只有在內存無限時纔可能。

+0

如果記憶是無限的,那會是什麼時間?不是O(N) – smac89 2014-10-28 23:08:16

相關問題