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

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

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

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

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

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

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

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

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

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

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

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

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

$n$$\Theta(n \log n)$

$\Theta(n \log n)$

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

$O(n^2)$

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

$T(n) = T(n-1) + n$$O(n^2)$