合并排序的空间要求

Question

我正在尝试理解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，当我们到达递归堆栈底部并开始向上移动时，我们不保留先前分支使用的内存，因此最多使用2n的内存，O(n)。

- Arkaitz Jimenez

Answer 1

有一些归并排序的版本可以原地操作。

然而，在大多数实现中，所需的空间与数组大小成线性关系。这意味着第一层需要n个元素的空间，第二层需要n/2个元素的空间，第三层需要n/4个元素的空间，以此类推。当你递归到底部时，这个级数会加起来约为2n，即线性。

- Uri

---

@Arkaitz：“大多数实现”包括您发布的实现。 - Brian

我现在已经发布了我所理解的内容，请纠正我如果有错误。 - Arkaitz Jimenez

你理解得很正确。问题出在伪代码上，它更容易可视化控制（因此时间复杂度），而不是调用堆栈的内容。 - Uri

@Uri 当您解释 (n、n/2、n/4 等) 的和负责 N 运行时间时，是否是通过合并排序的实现来实现的，该实现在当前帧每次对 较小 组件数组调用 sort 时都会创建一个数组？ - Muno

如果不是真的，意味着每次都传递相同的数组给sort，我的理解是你将会在堆栈顶部拥有最大的开销，当合并原始数组的两个半部分时。 - Muno

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)。

- Frank Q.

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]

- Gaganpreet