Пространственные требования слияния-сортировки

Question

Я пытаюсь понять требования к пространству для Mergesort, O (n).
Я вижу, что время требования в основном, количество уровней (logn) * merge (n), так что делает (n log n).
Теперь мы по-прежнему выделяем n для каждого уровня в двух разных массивах: левый и правый.
Я понимаю, что ключевой момент здесь в том, что когда рекурсивные функции возвращают пространство, оно освобождается, но я не вижу этого слишком очевидным.
Кроме того, вся информация, которую я нахожу, просто требует, чтобы пространство состояний было O (n), но не объясняйте это.
Любой намек?

function merge_sort(m)
    if length(m) ≤ 1
        return m
    var list left, right, result
    var integer middle = length(m) / 2
    for each x in m up to middle
         add x to left
    for each x in m after middle
         add x to right
    left = merge_sort(left)
    right = merge_sort(right)
    result = merge(left, right)
    return result

EDIT Хорошо, спасибо @Uri, это трюк
В самом начале я не смог увидеть, что время только добавляет, а память добавляет и вычитает, поэтому максимальное количество времени находится в конце выполнения, но максимальное количество памяти находится на дне рекурсивного стека.

Итак, если мы продолжим добавлять n + n / 2 + n / 4 + n / 8 .... не имеет значения, сколько раз мы добавим, оно никогда не будет больше 2n, и когда мы достигнем дно рекурсивного стека и начало роста, мы не сохраняем память, использованную для предыдущей ветви, поэтому при максимальном значении 2n будет использоваться объем памяти, O (n).

Answer 1

Существуют версии сортировки слиянием, которые могут работать на месте.

Однако в большинстве реализаций пространство является линейным по размеру массива. Это означает, что n для первого уровня, n / 2 для второго, n / 4 для третьего и т.д.

Answer 2

Это мое объяснение сложности пространства для вашего кода. Как правило, когда алгоритм достигает результатов, как мы работаем с памятью.

1) Каждый рекурсивный вызов, который вы делаете, имеет постоянный размер выделенного фрейма стека, а также любые переменные, которые не являются функцией «n». Давайте назовем эту константу "с". Поскольку вы углубляетесь на уровень lg (n), результатом будет c * lg (n), который равен O (lg (n)).

2) Теперь, когда мы вычисляем результат, мы выделяем пространство для n / (2 ^ k) элементов, где k - уровень, на котором вы находитесь.

left = merge_sort(left)
right = merge_sort(right)

Для людей, которым может быть интересно, как мы пришли к n / (2 ^ k), обратите внимание, что сначала мы идем о выделении памяти при решении первой половины массива, т.е. left = merge_sort (left). Как только это дерево рекурсии закончено, мы в конечном итоге освобождаем всю память и возвращаемся к исходной точке, прежде чем решить для правой стороны. Следовательно, его п / (2 ^ к). Это будет O (n).

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

Окончательный ответ = O (lg (n)) + O (n) + O (n), то есть O (n).