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

18

Рандомизированная быстрая сортировка - это расширение быстрой сортировки, в котором элемент поворота выбирается случайным образом. Что может быть наихудшим случаем временной сложности этого алгоритма. По моему мнению, это должно быть , так как наихудший случай случается, когда случайно выбранный круг выбирается в отсортированном или в обратном порядке. Но в некоторых текстах [1] [2] его наихудшая временная сложность записывается какO(n2)O(nlogn)

Что правильно?

Atinesh
источник
3
Вы должны этот "некоторый текст", о котором вы говорите. Там что-то спрятано. Вы найдете его, если снова прочитаете этот «текст»
AJed
Примечание. Ссылка [1] не работает. Линк [2] четко заявляет, что алгоритм рандомизирован, поэтому для любого ввода у вас есть не «время выполнения», а «ожидаемое время выполнения». И ожидаемое время выполнения для наихудшего возможного ввода - O (n log n).
gnasher729

Ответы:

18

Оба ваших источника ссылаются на «ожидаемое время выполнения в наихудшем случае» Я предполагаю, что это относится к ожидаемому требованию ко времени, которое отличается от абсолютного наихудшего случая.O(nlogn),

Быстрая сортировка обычно имеет абсолютное наихудшее время . Худший случай возникает, когда на каждом этапе процедура разбиения разбивает массив n- длины на массивы размером 1 и n - 1 . Этот «неудачный» выбор элементов разворота требует O ( n ) рекурсивных вызовов, что приводит к O ( n 2 ) наихудшему случаю.O(n2)N1N-1О(N)О(N2)

Выбор шарнирной случайной или случайной перестановки массива перед сортировкой приводит к тому, что наихудший случай становится крайне маловероятным, особенно для больших массивов. Посмотрите Википедию для доказательства того, что ожидаемое время - . Согласно другому источнику , "вероятность того, что быстрая сортировка будет использовать квадратичное число сравнений при сортировке большого массива на вашем компьютере, намного меньше, чем вероятность того, что ваш компьютер будет поражен молнией".О(NжурналN)

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

Согласно комментарию Банье, вы можете исключить последовательность выбора наихудшего случая, всегда выбирая медианный элемент в качестве основного. Поскольку нахождение медианы занимает времени, это дает Θ ( n log n ) производительности в худшем случае. Однако, поскольку маловероятно, что рандомизированная быстрая сортировка наткнется на худший случай, детерминистический вариант быстрой сортировки по медиане редко используется.О(N)Θ(NжурналN)

Джеймс Эванс
источник
Так что в целом можно сказать, что в худшем случае он ведет себя как квадратичный
Атинеш
@ Atinesh Нет, по крайней мере, если ты имеешь в виду под этим. Θ
Рафаэль
Я думаю, что правильно сказать, что производительность рандомизированной быстрой сортировки в наихудшем случае равна О(N2),
Джеймс Эванс
4
Quicksort может принимать только время , в худшем случае , если один использует алгоритм линейного времени , чтобы найти медиану в качестве опоры. Конечно, рандомизированная быстрая сортировка обычно имеет лучшую практическую производительность. Θ(NжурналN)
Bangye
6

Вам не хватало того, что в этих текстах говорится о «наихудшем ожидаемом времени выполнения», а не «наихудшем времени выполнения».

Они обсуждают реализацию Quicksort, которая включает случайный элемент. Обычно у вас есть детерминированный алгоритм, то есть алгоритм, который для данного входа всегда будет производить одинаковые шаги. Чтобы определить «время выполнения в худшем случае», вы изучаете все возможные входные данные и выбираете тот, который дает худшее время выполнения.

Но здесь у нас есть случайный фактор. Учитывая некоторые входные данные, алгоритм не всегда будет делать одни и те же шаги, потому что это связано с некоторой случайностью. Вместо того, чтобы иметь время выполнения для каждого фиксированного ввода, у нас есть «ожидаемое время выполнения» - мы проверяем каждое возможное значение случайных решений и их вероятность, а «ожидаемое время выполнения» является средневзвешенным значением времени выполнения для каждой комбинации случайных решений , но все же для фиксированного ввода.

Таким образом, мы рассчитываем «ожидаемое время выполнения» для каждого возможного ввода, и чтобы получить «ожидаемое время выполнения в худшем случае», мы находим один возможный вход, где ожидаемое время выполнения является наихудшим. И, по-видимому, они показали, что наихудший случай для «ожидаемого времени выполнения» - это просто O (n log n). Я не удивлюсь, если простой случайный выбор первого стержня изменит наихудшее ожидаемое время выполнения на o (n ^ 2) (маленький o вместо большого O), потому что только несколько из n пивотов приведут к худшему случаю поведение.

gnasher729
источник
2

Обратите внимание, что есть две вещи, которые нужно принять за ожидание / среднее значение: входная перестановка и опорные точки (по одной на разбиение).

NΘ(NжурналN)

Θ(NжурналN)

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

Рафаэль
источник
Рассмотрим этот вопрос postimg.org/image/fiurc4z87, который я задал на экзамене. Какие уместные ответы вы бы мне посоветовали (с)
Атинеш
1
@ Atinesh Я думаю, что мой ответ дает вам достаточно информации по этому вопросу.
Рафаэль
-1

О(N2)

В худшем случае для рандомизированной быстрой сортировки используются те же элементы, что и для ввода. Пример: 2,2,2,2,2,2

T(N)знак равноT(N-1)+NО(N2)

pratyay
источник
Это если у вас очень глупая реализация быстрой сортировки. Любая достойная реализация будет в первом разделе обмениваться # 1 и # 6, # 2 и # 5, # 3 и # 4, а затем отсортирует два подмассива длины 3.
gnasher729
Я думаю, у вас есть <=, а также> = на обоих указателях, которые сканируют из LHS и RHS. Вот почему ты так говоришь. '=' ассоциируется с любым из указателей, а не с обоими. В этом случае дерево рекурсии растет до n.
Пратай
И это то, что я называю чрезвычайно глупой реализацией. Любая реализация, которая принимает квадратичное время выполнения для случая «все элементы равны», преступно глупа. На самом деле существуют реализации, которые в этом случае занимают линейное время (O (n), а не O (n log n)).
gnasher729