Quicksort, чтобы найти медиана?

Question

Почему худший сценарий $ mathcal {o} Left (n^2 right) $ при использовании QuickSort, чтобы найти медиана набора чисел?

• Если ваш алгоритм постоянно выбирает число больше или меньше, чем все Числа в списке разве ваш алгоритм не пройдет? Например, если список чисел:

  $ S = (12,75,82,34,55,15,51) $

  И вы продолжаете собирать цифры более 82 долл. США или менее 12 долларов, чтобы создать сублисты, разве ваш набор всегда останется таким же размером?

• Если ваш алгоритм постоянно выбирает число, которое создает сублисты $ 1 $. Почему худший сценарий $ mathcal {o} Left (n^2 right) $? Не будет ли линейной эффективности, учитывая, что в соответствии с Мастер теорема, $ d> log_b a $?* (и, следовательно, $ mathcal {o} left (n^d right) $ или конкретно в данном случае $ mathcal {o} left (n right) $)

*Где $ D $ - показатель эффективности (т.е. линейный, экспоненциальный и т. Д.), $ B $ - это фактор, который проблема снижается на каждую итерацию, $ A $ - это количество подзадачи, а $ K $ - это уровень Анкет Полное соотношение: $ t (n) = mathcal {o} left (n^d right) * ( frac {a} {b^d})^k $

Answer 1

QuickSort для сортировки, алгоритм, на который вы ссылаетесь, представляет собой алгоритм выбора, известный как Быстрый выбор.

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

Итак, первая итерация вы делаете операции $ n $, вторая итерация $ N-1 $ Operations, третий $ n-2 $ Operations, ... последняя итерация 1 операция.

Какая сумма первых натуральных чисел $ n $:

$ 1+2+3+...+(n-2)+(n-1)+n = n (n-1)/2 $ operations = $ o (n^2) $