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

Question

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

我们可以使用某种技巧来打破 O(n log n) 对比较排序的平均情况的限制吗？

Answer 1

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