Быстрый выбор объяснил сложность времени

Question

С https://en.wikipedia.org/wiki/Quickselect написано

"Однако вместо повторения в обе стороны, как в быстрой сортировке, быстрый выбор повторяется только в одну сторону - сторону с элементом, который он ищет. Этоуменьшает среднюю сложность с O (n log n) до O (n), с наихудшим случаем O (n ^ 2). "

Я не понимаю, как сокращение, если смотреть только на одну сторону, уменьшает среднюю сложностьк О (п)?Разве это не больше O (N / 2 log N), которое все еще равно O (N log N).А как наихудший случай O (n ^ 2)

Answer 1

n log(n) подразумевает, что алгоритм просматривает все N элементов log (n) раз.Но это не то, что происходит с Quickselect.

Допустим, вы используете Quickselect, чтобы выбрать 8 лучших элементов в списке из 128. И каким-то чудом случайного выбора, выбранные вами опорные точки всегда находятся на полпути.point.

На первой итерации алгоритм просматривает все 128 элементов и разбивает их на две группы по 64 элемента в каждой.Следующая итерация разбивается на две группы по 32 элемента в каждой.Затем 16, а затем 8. Количество проверенных элементов:

N + N/2 + N/4 + N/8 + N/16

Сумма этого ряда никогда не достигнет 2 * N.

В худшем случае разделение всегда приводит кочень перекошенные размеры перегородок.Подумайте, что произойдет, если первое разбиение удалит только один элемент.А второй удалил только один и т. Д. Результат будет:

N + (N-1) + (N-2) ...

Что означает (n^2 + n)/2) или O(п ^ 2).