Быстрая сортировка с медианой в O (n log n)

Question

Я не очень понимаю, почему мы не всегда выбираем медианный элемент в качестве оси.Это может быть сделано в O (n) и, следовательно, приводит к общему времени выполнения O (n log n).

Я просто предполагаю, что, вероятно, в O (n) скрыта большая константа длясредний поиск.

Answer 1

Со страницы Wikipedia Quicksort :

И наоборот, как только мы узнаем, что алгоритм выбора наихудшего случая доступен, мы можем использовать его для нахождения идеального центра (медианы) на каждом шаге быстрой сортировки, получая вариант с запущенным O (n log n) в худшем случае. время. Однако в практических реализациях этот вариант в среднем значительно медленнее.

Другими словами, стоимость принудительной гарантии O (n log n) обычно не стоит оплачивать. На этой странице есть больше информации, а также алгоритмы выбора страница.

Answer 2

Очевидно, что время нахождения медианы составляет O (n) с использованием рандомизированной версии раздела, но на самом деле, когда раздел снова не сбалансирован до крайности, тогда время выполнения переходит к O (n ^{2 *).1002 *).Таким образом, вы не можете сделать улучшения прямо отсюда.Но все же есть надежда.Если вы пройдете через «CORMEN», то обнаружите, что нахождение статистики i-го порядка может быть выполнено за линейное время даже в худшем случае.Техника, которая используется, состоит в том, чтобы использовать медиану медианы в качестве элемента поворота, а затем найти недиан, который гарантирует линейное время бега в любом случае.Таким образом, мы можем использовать эту технику в быстрой сортировке, чтобы получить время выполнения O (nlgn)}

Answer 3

используйте рандомизированную быструю сортировку, и у вас будет наихудшее время выполнения O (n log n) с очень высокой вероятностью.