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

Question

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

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

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

Мои мысли:

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

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

Answer 1

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

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

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

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

Answer 2

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

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

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

Тогда сложность пространства О (п), а не O (журнал N), как это принято считать. Это происходит потому, что вы толкая в стек дважды на каждом уровне, поэтому сложность пространства определяется из recurrance:

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

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

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

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