合併排序算法的最佳運行時間和平均運行時間

Question

如何解釋爲什麼合併排序算法的最佳運行時間爲Big Omega（n log n），平均運行時間爲Big theta（n log n）？

Answer 1

Big Omega忽略低階項和/或常數因子，通常使用Big Omega來描述上限或最差情況。 Big Theta應該是一個較低和較高的範圍，並且/或者可以作爲最佳情況，平均情況，最壞情況，特定情況。

對於純合併排序（不是在較小組上使用某種排序類型的混合），移動次數相同，n⌈log2（n）⌉（其中⌈⌉是整數上限），而比較的數量可以變化，最壞的情況比n⌈log2（n）bit少一點，最好的情況大約是1/2，所以只是常數因子的差異。如果數據集元素適合寄存器（如對整數數組進行排序），則比較時間可能會被存儲器訪問時間隱藏（比較對總體時間影響很小或沒有影響）。如果執行外部合併排序（例如對大文件進行排序），比較時間可能會被設備讀取/寫入時間隱藏。

維基文章：

http://en.wikipedia.org/wiki/Big_O_notation

http://en.wikipedia.org/wiki/Time_complexity

http://en.wikipedia.org/wiki/Computational_complexity_theory

http://en.wikipedia.org/wiki/Analysis_of_algorithms