Пространственная сложность быстрой сортировки

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

На рисунке

при вычислении значения (1,1) мы сохраняем вызовы [(1,8), (1,4), (1,2)] ,

при вычислении значения (3,3) мы сохраняем вызовы [(1,8), (1,4), (3,4)] и т.д.

которые составляют только O (log n) пространства в муравьиный момент времени. Тогда становится ли сложность O(n) ?


sorting algorithm data-structures quicksort
person kaushalpranav    schedule 20.07.2016    source источник
comment
Стоит отметить, что можно настроить быструю сортировку так, чтобы рекурсивные биты неявно сохранялись в самих данных, используя только пространство стека O(1), хотя и за счет примерно в 2 раза большего количества сравнений. ideone.com/7dF7l1   -  person Mooing Duck    schedule 20.07.2016
comment
Метод, используемый для уменьшения накладных расходов на стек, состоит в том, чтобы использовать рекурсию только для меньшей части разделенного раздела, а когда эта вилка в конечном итоге возвращается, зациклиться и повторить (итерировать) процесс (начиная с другого разделения) на оставшейся большей части раздела. раздел. Это уменьшает максимальное используемое пространство стека, но не улучшает временную сложность в худшем случае.   -  person rcgldr    schedule 21.07.2016

Ответы (1)


arrow_upward
6
arrow_downward

В примере дерева, который вы привели выше, вы показали запуск быстрой сортировки, который всегда выбирает точный медианный элемент в качестве точки разделения на каждом шаге. Это делает глубину рекурсии O (log n), поэтому, как вы заметили, использование пространства будет O (log n) даже без оптимизации.

Но что произойдет, если у вас не получится выполнить быструю сортировку? То есть, что произойдет, если вы всегда выбираете абсолютный самый большой или абсолютный самый маленький элемент массива в качестве точки поворота в каждой точке? Тогда ваше дерево рекурсии будет выглядеть примерно так:

    size n
       \
       size n-1
         \
         size n-2
           \
            ...
             \
              1

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

person templatetypedef    schedule 20.07.2016