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

Question

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

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

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

Мои мысли:

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

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

Answer 1

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

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

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

*] В частности, вместо того, чтобы вызвать функцию рекурсивно на обе стороны, вы помещаете его в цикл. Сделайте рекурсивный вызов на меньшую часть и циклируйте, чтобы сделать более крупную часть или эквивалентно толкать (указатели на) большую часть на стопку работы, чтобы выполнить позже, и цикл, чтобы сделать меньшую часть. В любом случае, вы убедитесь, что глубина стека никогда не превышает журнал 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 (log n) как обычно считается. Это потому, что вы нажимаете на стек дважды на каждом уровне, поэтому пространство сложности определяется из рецидива:

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

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

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

Возможно, «смежность Quicksort» относится к первому осуществлению, потому что два вызовы Quicksort рядом друг с другом, в этом случае пространство сложности На).