algorithm - 在某些情况下，Timsort 如何击败 O(n log n) 排序界限？

Question

我听说 Timsort 在某些情况下利用数据模式打破了 O(n log n) 界限。怎么可能？谁能详细解释我？如果这是真的，那么 Timsort 将总是比快速排序进行更少的比较，因为在现实生活中的数据中存在一些模式，除了数据是真正随机的？

我们可以使用某种技巧来打破 O(n log n) 限制在 avg 情况下进行比较排序吗？

Answer 1

这取决于你在这里平均的意思。在 CS 领域内，平均值具有非常精确的含义： 假设每个可能的输入集具有相同的概率，所有可能输入集的平均值。 这个定义很方便，因为它精确且很容易处理，但在某些情况下不是最有用的，因为真实的单词数据通常不同于随机数，所以可以说更好的平均值定义是：所有真实的平均值-世界输入集. 但这不是很精确，在科学背景下也行不通，所以你不会在学术界找到它。两种定义的区别是巨大的：在现实世界的数据中，你可以合理地假设有一个固定百分比K1的输入集可以通过 timsort 之类的东西在线性时间进行排序。对于随机数据，K2(n)可以在线性时间内排序的百分比非常快地变为零，例如K2=Exp(-n)，n作为输入集的大小。因此，对您的问题的准确学术回答是否定的，您无法改善平均情况。现实世界工程师的答案是可能，这取决于，我们可以尝试。他们做到了。