Как вычислить сложность алгоритмического пространства - PullRequest
Новая
       44

Как вычислить сложность алгоритмического пространства

4 голосов
/ 02 октября 2010

Я рассматриваю свой урок по структурам данных и анализу алгоритмов, и у меня возникает вопрос, как определить по сложности пространства сортировку слиянием и алгоритмы быстрой сортировки ?

Глубина рекурсии составляет только O (lgn) для сортировки слиянием связанного списка

Объем дополнительного пространства для хранения, необходимого для непрерывной быстрой сортировки, составляет O (n).

Мои мысли:

Оба используют стратегию «разделяй и властвуй», поэтому я предполагаю, что сложность пространства сортировки слиянием связанного списка должна быть такой же, как и у непрерывной быстрой сортировки.На самом деле я выбираю O (lgn), потому что перед каждым вызовом итерации или рекурсии список делится пополам.

Спасибо за любые указатели.

Ответы [ 2 ]

2 голосов
/ 02 октября 2010

Наихудшая глубина рекурсии для быстрой сортировки не является (обязательно) O (log n), потому что быстрая сортировка не делит данные «пополам», а разделяет их вокруг оси, которая может быть или не быть медианной. Можно реализовать быструю сортировку для решения этой проблемы [*], но, предположительно, анализ O (n) был базовой рекурсивной реализацией быстрой сортировки, а не улучшенной версией. Это объясняет расхождение между тем, что вы говорите в цитате, и тем, что вы говорите в «моих мыслях».

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

Другой возможный способ объяснить расхождение, я полагаю, заключается в том, что анализ O (n) является просто неправильным. Или, «смежная быстрая сортировка» - это не термин, который я слышал раньше, поэтому, если это не означает, что я думаю («быстрая сортировка массива»), это может означать, что быстрая сортировка в некотором смысле неизбежно неэффективна , например, возвращая выделенный массив вместо сортировки на месте. Но было бы глупо сравнивать быструю сортировку и сортировку на основе глубины рекурсии слияния и размера копии входных данных для быстрой сортировки.

[*] В частности, вместо рекурсивного вызова функции в обеих частях вы помещаете ее в цикл. Сделайте рекурсивный вызов для меньшей части и выполните цикл, чтобы выполнить большую часть, или эквивалентно поместите (указатели) большую часть в стек работы, чтобы выполнить ее позже, и выполните цикл вокруг, чтобы выполнить меньшую часть. В любом случае, вы гарантируете, что глубина стека никогда не превышает log n, потому что каждый кусок работы , а не , помещенный в стек, составляет не более половины размера фрагмента до него, вплоть до фиксированного минимума ( 1 или 2, если вы сортируете только с помощью быстрой сортировки).

1 голос
/ 08 июня 2012

Я не очень знаком с термином "непрерывная быстрая сортировка". Но быстрая сортировка может иметь сложность пространства O (n) или O (log n) в зависимости от того, как она реализована.

Если это реализовано следующим образом: 

quicksort(start,stop) {
    m=partition(start,stop);
    quicksort(start,m-1);
    quicksort(m+1,stop);
}

Тогда сложность пространства равна O (n) , а не O (log n), как принято считать. Это связано с тем, что вы дважды помещаете в стек на каждом уровне, поэтому сложность пространства определяется по повторению: 

T(n) = 2*T(n/2)

Предполагая, что разбиение делит массив на 2 равные части (в лучшем случае). Решение этой проблемы согласно Основной теореме - это T (n) = O (n).

Если мы заменим второй вызов быстрой сортировки на хвостовую рекурсию в приведенном выше фрагменте кода, то вы получите T (n) = T (n / 2) и, следовательно, T (n) = O (log n) (для случая 2 основная теорема).

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

...