Относительно Quick Sort Killer

Question

Некоторые из вас, возможно, наткнулись на эту симпатичную статью - http://igoro.com/archive/quicksort-killer/ \

Что действительно интересно, так это то, как он исправляет быструю сортировку для выполнения в O (N log N) против определенного противника..

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

Мой вопрос заключается в том, не будет ли алгоритм поиска медианы по линейному временив конечном итоге использовать ту же функцию сравнения и выполнить в O (N ^ 2) вместо O (N)?

Редактировать:

Чтобы быть точным: я ставлю под сомнение сложность раздела-Алгоритм based-median-selection, который использует стратегию, подобную стратегии быстрой сортировки, и использует ту же функцию сравнения, что и функция быстрой сортировки.Как это может работать в O (N) с этим противником?

Answer 1

не найдет медиану линейного времени алгоритм в конечном итоге использует тот же сравнить функцию и выполнить в O (N ^ 2) вместо O (N)?

Нет, если добавить функцию O (N) для нахождения медианы, сложность становится равной

O((N+N) log N) == O(2N log N) == O(N log N)

Но, как говорится в этой статье, увеличение константы делает ее непривлекательной.

Стандартная методика называется медиана-3, и полный медианный поиск не улучшится.

Если наихудший случай критичен, просто не используйте быструю сортировку. У скорлупы лучше верхняя граница.