Быстрая сортировка и сложность пространства?

scott miles спросил: 12 мая 2018 в 04:57 в: algorithm

Quick - это алгоритм, который не использует вспомогательный массив. Итак, почему сложность памяти этого O (nlog (n))?

Точно так же я понимаю, что худшей временной сложностью является O (n ^ 2), но не получается, почему средняя сложность времени случая равна O (nlog (n )). В принципе, я не уверен, что мы имеем в виду, когда говорим о сложности среднего случая?


1 ответ

Alexander Kaschta ответил: 12 мая 2018 в 05:14

К вашему второму пункту выдержка из Википедии:

Самый неуравновешенный раздел возникает, когда подпрограмма секционирования возвращает один из подписок размером n - 1. Это может произойти, если точка опоры наименьший или самый большой элемент в списке или в некоторых реализациях (например, схема разделов Lomuto, как описано выше), когда все элементы равны.

Если это повторяется повторно в каждый раздел, то каждый рекурсивный вызов обрабатывает список размером один меньше, чем предыдущий список. Следовательно, мы можем сделать n - 1 вложенных вызовов до того, как получим список размером 1. Это означает, что дерево вызовов является линейной цепочкой из n - 1 вложенных вызовов. I-й вызов делает O (n-i) для работы с разделом и {\ displaystyle \ textstyle \ sum _ {i = 0} ^ {n} (ni) = O (n ^ {2})}, поэтому в этот случай Quicksort занимает время O (n²).

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