归并排序的空间要求

Question

我试图了解合并排序的空间要求，O(n)。
我发现时间要求基本上是级别数量（logn）*合并（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，当我们到达递归堆栈时底部并开始向上，我们不保留前一个分支使用的内存，因此最大时，2n 将是使用的内存量，O(n)。

Answer 1

有一些可以就地工作的合并排序版本。

然而，在大多数实现中，空间与数组的大小成线性关系。这意味着 n 代表第一层，n/2 代表第二层，n/4 代表第三层，等等。当你到达递归底部时，这个级数加起来约为 2n，这是线性的。

Answer 2

这是我对代码空间复杂度的解释。基本上，当算法达到结果时，我们在内存上的表现如何。

1）您进行的每个递归调用都分配了恒定大小的堆栈帧以及不是“n”函数的任何变量。
我们称这个常数为“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) 的人，请注意，首先我们在求解数组的前半部分时分配内存，即 left=merge_sort(left)。一旦这个递归树结束，我们最终会释放所有内存并回到起点，然后再求解右侧。因此，它是 n/(2^k)。
这将是 O(n)。

3）最后，合并过程也可能会分配额外的空间（如果使用链表，则可能不需要该空间），即 O(n)

最终答案 = O(lg(n)) + O(n) + O(n) 其中是 O(n)。

Answer 3

如果运行下面的 Java 代码，您可以看到分配的空间。当然这不包括函数调用堆栈空间。

import java.util.Arrays;

public class MergeSort {
    public static int[] sort(int[] nums) {

        System.out.println("Input array = " + Arrays.toString(nums));

        if (nums == null) return null;
        
        int n = nums.length;
        if (n == 0) return new int[] {};

        int[] space = new int[1];
        int[] result = sort(nums, 0 , n-1, space);

        System.out.println("Output array = " + Arrays.toString(result));

        return result;
    }

    private static int[] sort(int[] nums, int left, int right, int[] space) {
        
        if (left == right) {
            space[0]++;
            System.out.println("Allocating a single entry. space = " + space[0]);
            return new int[] {nums[left]};
        }

        int mid = (left + right)/2;

        int[] sortedLeft = sort(nums, left, mid, space);
        int[] sortedRight = sort(nums, mid + 1, right, space);

        int[] merged = merge(sortedLeft, sortedRight, space);
        
        space[0] = space[0]-sortedLeft.length - sortedRight.length;
        System.out.println("Relinquishing left and right subarrays. Space = " + space[0]);
        return merged;
    }

    private static int[] merge(int[] arr1, int[] arr2, int[] space) {
        int n = arr1.length;
        int m = arr2.length;

        int[] arr = new int[m+n];
        space[0] = space[0]+m+n;
        System.out.println("Allocating merged array. Space = " + space[0]);
        int i = 0, j = 0, k = 0;

        for (; i < n && j < m; k++) {
            arr[k] = arr1[i] <= arr2[j] ? arr1[i++] : arr2[j++];
        }

        while (i < n) {
            arr[k++] = arr1[i++];
        }

        while (j < m) {
            arr[k++] = arr2[j++];
        }

        return arr;
    }
}

在 8 尺寸的输入上，

public class App {
    public static void main(String[] args) throws Exception {
        MergeSort.sort(new int[] {1, 6, 3, 8, 1, 8, -2, 4});
    }
}

您应该看到最大空间为 16。

Input array = [1, 6, 3, 8, 1, 8, -2, 4]
Allocating a single entry. space = 1
Allocating a single entry. space = 2
Allocating merged array. Space = 4
Relinquishing left and right subarrays. Space = 2
Allocating a single entry. space = 3
Allocating a single entry. space = 4
Allocating merged array. Space = 6
Relinquishing left and right subarrays. Space = 4
Allocating merged array. Space = 8
Relinquishing left and right subarrays. Space = 4
Allocating a single entry. space = 5
Allocating a single entry. space = 6
Allocating merged array. Space = 8
Relinquishing left and right subarrays. Space = 6
Allocating a single entry. space = 7
Allocating a single entry. space = 8
Allocating merged array. Space = 10
Relinquishing left and right subarrays. Space = 8
Allocating merged array. Space = 12
Relinquishing left and right subarrays. Space = 8
Allocating merged array. Space = 16
Relinquishing left and right subarrays. Space = 8
Output array = [-2, 1, 1, 3, 4, 6, 8, 8]