在某些情況下Timsort如何擊敗O（n log n）排序界限？

Question

我聽說Timsort利用數據模式打破了某些情況下的O（n log n）界限。怎麼可能？任何人都可以詳細解釋我嗎？如果這是真的，那麼Timsort總是比快速排序少比較，因爲在真實生活數據中有一些模式，除了數據是真正隨機的嗎？

我們能使用某種技巧的突破爲O（n log n）的結合在平均情況下比較排序？

Answer 1

這取決於你的意思是平均這裏。在CS領域，平均有一個非常精確的含義：在所有可能的輸入集的平均，假設每個可能的輸入集具有相同的概率。這個定義很方便，因爲它是精確的，並且很容易處理，但在某些情況下不是最有用的，因爲現實世界的數據一般是隨機數不同，所以平均一個可以說是更好的定義是：的意味着所有真實世界的輸入集合。但這不是很精確，不會在科學環境下工作，所以你不會在學術界找到這個。這兩個定義的差異是巨大的：在現實世界的數據中，你可以合理地假設輸入集合有一個固定的百分比，可以通過類似timsort的線性時間進行排序。對於隨機數據，可以在線性時間排序的百分比K2(n)去非常迅速歸零，就像K2=Exp(-n)，與n是輸入集的大小。所以，對你的問題的確切的，學術的答案是沒有，你不能改善平均情況。從現實世界的工程師的答案將是也許，這取決於，我們可以嘗試。他們這樣做。