基于比较的排序是WC最小时间nlogn，那么最佳/平均情况呢

Question

科尔曼有一个定理说...（第8.1节）“对于基于比较的排序技术，您不能有一个算法来排序给定的列表，在最坏的情况下，它所花费的时间少于nlogn时间（比较）”，即。基于比较的排序技术的最差情况时间复杂度为Omega（nlogn）.

现在，我在寻找的是，在最佳情况下，或者甚至在平均情况下，是否存在这样的语句：

在最好的情况下，排序算法对给定的元素列表进行排序所需的时间不能少于X

Answer 1

好问题！定义“平均情况”复杂性的挑战是，你必须问“平均情况是什么？”

例如，如果我们假设数组的元素在n！n个元素的可能排列，那么比较排序上的？（n log n）界限仍然成立，尽管我似乎记得这一点的证明相当复杂。

另一方面，如果我们假设数据中存在趋势（例如，你在测量一天中的温度，你知道它们通常是上升然后下降的趋势）。很多真实世界的数据集看起来都是这样的，有像Timsort这样的算法可以利用那些模式来加快性能。所以这里的“平均”可能是指“在所有可能的曲线上的平均，这些曲线是由一个上升，然后下降的序列加上噪声项形成的。”我没有遇到过任何人在这些情况下分析算法，但我肯定已经做了一些工作，甚至可能有一些很好的平均情况度量，但不太为人所知。