Наихудший случай быстрой сортировки с помощью медианы из-3 метода

голоса
0

Можем ли мы всегда избежать худшего случая быстрой сортировки с помощью медианы из-3 метода?

Задан 20/10/2018 в 05:12
источник пользователем
На других языках...                            


1 ответов

голоса
-1

Быстрая сортировка Алгоритм работает следующим образом :

  1. Если число элементов в S равно 0 или 1, а затем возвращать (базовый вариант).
  2. Выберите любой элемент V в S (так называемый стержень).
  3. Partition элементов в S, за исключением V на два непересекающихся группы
  4. Возврат {QuickSort (S1) + V + QuickSort (S2)}

Худшем случае для быстрой сортировки с помощью метода медианы из-3, когда выбранный стержень уменьшает размер проблемы путем наименьшего возможного количества. Это означает, что выбранный шарнир обеспечивает, как далеко от раздела, как это возможно. И так как мы используем метод медианы из-3, выбранный раздел не может быть самым большим или наименьший элемент, так как наш выбранный метод гарантирует, что раздел имеет элемент больше и меньше, чем медиана.

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

Точка с использованием методы медианы из-3, чтобы приблизить нас к среднему времени выполнения быстрого вида : O (NlogN). Это происходит потому , что, избегая дальние элементы в списке , чтобы выбрать наш раздел, мы можем минимизировать наше отклонение от лучшего / усредненного времени выполнения в O (NlogN).

Используя метод медианы из-3 позволит нам никогда не придется искать весь список для правильного раздела, а начать где-то в середине. Таким образом, мы можем избежать худшего случая во время выполнения О (п ^ 2) и оседают на среднем времени выполнения в O (NlogN)

Ответил 03/12/2018 в 22:19
источник пользователем

Cookies help us deliver our services. By using our services, you agree to our use of cookies. Learn more