Я пытаюсь понять требования к пространству для Mergesort, O (n).
Я вижу, что временные требования в основном, количество уровней (logn) * merge (n), что делает (n log n).
Теперь мы все еще выделяем n за уровень, в 2 разных массивах, влево и вправо.
Я понимаю, что ключевым моментом здесь является то, что при возврате рекурсивных функций пространство становится освобожденным, но я не вижу его слишком очевидным.
Кроме того, вся информация, которую я нахожу, просто указывает, что требуется пространство, это 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
ИЗМЕНИТЬ
Хорошо, спасибо @Uri, это трюк
То, что я не видел в самом начале, это то, что время добавляет только время, в то время как память добавляет и вычитает, поэтому максимальное количество времени находится в конце выполнения, но максимальный объем памяти находится в нижней части рекурсивного стека.
Итак, если мы добавим n + n/2 + n/4 + n/8.... неважно, сколько раз мы добавляем, оно никогда не будет больше 2n, и когда мы достигнем рекурсивное нижнее дно стека и начать движение вверх, мы не сохраняем память, используемую для предыдущей ветки, поэтому при max 2n будет использоваться объем памяти O (n).
Существуют версии слияния-сортировки, которые могут работать на месте.
Однако в большинстве реализаций пространство является линейным по размеру массива. Это означает, что n для первого уровня, n/2 для второго, n/4 для третьего и т.д. К тому времени, когда вы находитесь в нижней части своей рекурсии, эта серия добавляет около 2n, что является линейным.
Это мое объяснение сложности пространства для вашего кода. В принципе, поскольку алгоритм достигает результатов, как мы это делаем в памяти.
1) Каждый вызов рекурсии, который вы делаете, имеет постоянный размер выделенного кадра стека, а также любые переменные, которые не являются функцией "n". Позвольте называть этот constanct "c". Так как вы идете на уровни lg (n), результат получается c * lg (n), который является O (lg (n)).
2) Теперь, когда мы вычисляем результат, выделяем пространство для элементов n/(2 ^ k), где k - уровень, на котором вы находитесь.
left = merge_sort(left)
right = merge_sort(right)
Для людей, которые могут задаться вопросом, как мы пришли с n/(2 ^ k), обратите внимание, что сначала мы собираемся выделить память при решении первой половины массива i.e left = merge_sort (слева). Однажды это дерево рекурсии завершено, мы в конечном итоге освобождаем всю память и возвращаемся к исходной точке, прежде чем решать для правой стороны. Следовательно, его n/(2 ^ k). Это будет O (n).
3) Наконец, процедура слияния может также выделять лишнее пространство (при использовании связанного списка это пространство может не понадобиться), которое равно O (n)
Окончательный ответ = O (lg (n)) + O (n) + O (n), который является O (n).