合并排序的空间需求 [英] Space requirements of a merge-sort

问题描述

我想了解的空间要求归并，为O（n）。
我看到时间要求基本上水平（LOGN）*合并（N），这样就使得（N log n）的量。
现在，我们仍然分配ñ每升一级，在2个不同的阵列，左，右。
我也明白，这里的关键是，当递归函数返回的空间被释放，但我没有看到它太明显了。
此外，所有的信息，我发现，只是规定所需的空间是O（n），但没有解释它。
任何提示？

I'm trying to understand the space requirements for a Mergesort, O(n).
I see that time requirements are basically, amount of levels(logn) * merge(n) so that makes (n log n).
Now, we are still allocating n per level, in 2 different arrays, left and right.
I do understand that the key here is that when the recursive functions return the space gets deallocated, but I'm not seeing it too obvious.
Besides, all the info I find, just states space required is O(n) but don't explain it.
Any hint?

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，这是招
我没有看到在一开始的那段时间只增加了，而内存加减法运算，所以时间的最高限额是执行结束，但最大内存量是递归堆栈的底部。

EDIT Ok, thanks to @Uri, this is the trick
What I failed to see at the very beginning is that time only adds, while memory adds and subtracts, so the maximum amount of time is at the end of execution, but the maximum amount of memory is at the bottom of the recursive stack.

所以，如果我们继续增加N + N / 2 + N / 4 + N / 8 ....不要紧多少次我们添加，它永远不会大于2N，当我们到达递归栈底，并开始往上走，我们不保留用于previous分支的内存，所以在最高，2N将内存使用量，为O（n）。

So, if we keep adding n + n/2 + n/4 + n/8.... it doesn't matter how many times we add, it'll never be bigger than 2n, and when we reach the recursive stack bottom and start going up, we don't keep the memory used for the previous branch, so at max, 2n would be the amount of memory used, O(n).

推荐答案

有对合并排序的版本，可以在地方工作。

There are versions of merge-sort that can work in place.

然而，在大多数实现中，空间是线性的阵列的大小。这意味着n，用于在第一级中，n / 2的第二中，n / 4为第三，等。通过你在你的递归底部的时间，这一系列加起来大约2n个，其是直链。

However, in most implementations the space is linear in the size of the array. That means n for the first level, n/2 for the second, n/4 for the third, etc. By the time you are at the bottom of your recursion, this series adds up to about 2n, which is linear.

这篇关于合并排序的空间需求的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！