合并排序算法的最佳运行时间和平均运行时间

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