合并排序的空间要求

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

编辑 好了,多亏了@Uri,这就是诀窍
我一开始没看到的是时间只是添加,而内存增加和减少,所以最大时间是在执行结束时,但是最大量内存位于递归堆栈的底部.

所以,如果我们继续添加n + n/2 + n/4 + n/8 ....我们添加多少次并不重要,它永远不会大于2n,当我们到达递归堆栈时从底部开始上升,我们不保留用于前一个分支的内存,因此在最大值时,2n将是所使用的内存量O(n).

Answer 1

有一些版本的merge-sort可以在适当的位置使用.

但是,在大多数实现中,空间是数组大小的线性.这意味着第一级为n,第二级为n/2,第三级为n/4,等等.当你处于递归的底部时,此系列加起来约为2n,这是线性的.