基于比较的排序是 WC min time nlogn，那么 best/average 的情况呢
Comparison based sorting is WC min time nlogn, so what about best/average case
Cormen 中有一个定理说...
（第 8.1 节）
"For comparison based sorting techniques you cannot have an algorithm to sort a given list, which takes time less than nlogn time (comparisons) in the worst case"
IE。
最坏情况 时间复杂度是 Omega (nlogn) 基于比较的排序技术...
现在我正在搜索的是，是否存在关于最佳情况的陈述......或者甚至是平均情况
其中声明如下：
You cannot have a sorting Algorithm which takes time less than some X to sort a given list of elements...in the best case
基本上我们有最佳案例算法的任何下限。或者甚至是平均情况下的事实。 （我尽力找到这个，但找不到任何地方）。也请告诉我我提出的观点是否值得。
好问题！定义“平均情况”复杂性的挑战在于你必须问“平均超过什么？”
例如，如果我们假设数组的元素有相同的概率出现在n！ n 个元素的可能排列，那么比较排序上的 Ω(n log n) 仍然成立，尽管我似乎记得这个证明相当复杂。
另一方面，如果我们假设数据存在趋势（例如，您正在测量一天中的温度，您知道它们通常呈先上升后下降的趋势）。许多现实世界的数据集看起来像这样，并且有像 Timsort 这样的算法可以利用这些模式来提高性能。因此，这里的“平均”可能意味着“对所有可能的图进行平均，这些图由先上升后下降的序列形成，并添加了噪声项。”我没有遇到任何人在这些案例中分析算法，但我确信那里已经做了一些工作，甚至可能有一些不太为人所知的不错的平均案例度量。
Cormen 中有一个定理说... （第 8.1 节） "For comparison based sorting techniques you cannot have an algorithm to sort a given list, which takes time less than nlogn time (comparisons) in the worst case" IE。 最坏情况 时间复杂度是 Omega (nlogn) 基于比较的排序技术...
现在我正在搜索的是，是否存在关于最佳情况的陈述......或者甚至是平均情况 其中声明如下：
You cannot have a sorting Algorithm which takes time less than some X to sort a given list of elements...in the best case
基本上我们有最佳案例算法的任何下限。或者甚至是平均情况下的事实。 （我尽力找到这个，但找不到任何地方）。也请告诉我我提出的观点是否值得。
好问题！定义“平均情况”复杂性的挑战在于你必须问“平均超过什么？”
例如，如果我们假设数组的元素有相同的概率出现在n！ n 个元素的可能排列，那么比较排序上的 Ω(n log n) 仍然成立，尽管我似乎记得这个证明相当复杂。
另一方面，如果我们假设数据存在趋势（例如，您正在测量一天中的温度，您知道它们通常呈先上升后下降的趋势）。许多现实世界的数据集看起来像这样，并且有像 Timsort 这样的算法可以利用这些模式来提高性能。因此，这里的“平均”可能意味着“对所有可能的图进行平均，这些图由先上升后下降的序列形成，并添加了噪声项。”我没有遇到任何人在这些案例中分析算法，但我确信那里已经做了一些工作，甚至可能有一些不太为人所知的不错的平均案例度量。