algorithm - 基于比较的排序是WC min time nlogn，那么最好/平均情况呢
问题描述
Cormen 中有一个定理说......（Th 8.1）“对于基于比较的排序技术，你不能有一个算法来对给定列表进行排序，在最坏的情况下，它花费的时间少于 nlogn 时间（比较）”即最坏案例时间复杂度是基于比较的排序技术的欧米茄（nlogn） ......
现在我正在搜索的是，在最好的情况下是否存在一个语句..或者甚至对于 avg case ，它声明如下：
你不能有一个排序算法，它花费的时间少于一些 X 来对给定的元素列表进行排序......在最好的情况下
基本上我们对最佳情况算法有任何下限。甚至事实上对于普通情况。（我尽力找到这个，但在任何地方都找不到）。还请告诉我我提出的观点是否值得。
解决方案
好问题！定义“平均案例”复杂性的挑战是您必须问“平均是什么？”</p>
例如，如果我们假设数组的元素有相同的概率出现在 n! n 个元素的可能排列，那么比较排序上的 Ω(n log n) 界限仍然成立，尽管我似乎记得这一点的证明相当复杂。
另一方面，如果我们假设数据中存在趋势（例如，您正在测量一天中的温度，您知道它们通常呈上升趋势然后下降）。许多现实世界的数据集看起来像这样，并且有像 Timsort 这样的算法可以利用这些模式来提高性能。因此，这里的“平均”可能意味着“对所有可能的图进行平均，这些图由一个上升然后下降的序列形成，并添加了噪声项。” 我没有遇到任何人在这些情况下分析算法，但我确信那里已经完成了一些工作，甚至可能有一些不太为人所知的很好的平均案例措施。