Как 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 является размером набора входных данных. Итак, точный, академический ответ на ваш вопрос: No, вы не можете улучшить средний случай. Ответ от реального инженера будет Возможно,, все зависит, мы можем попробовать. И они это делают.