在合并排序算法中，在合并数组后释放左右子数组是否会对 space 复杂度产生影响？

Question

在合并排序的一个教程视频中，提到一旦左右子数组必须合并到父数组，为了降低space复杂度，我们需要释放为左右子数组分配的内存。但是每当我们从函数调用中出来时，局部变量就会被销毁。如果我错了，请纠正我。那么释放内存的动作会有什么不同吗？

这是我写的代码：

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

void mergeArr(int *rarr, int *larr, int *arr, int rsize, int lsize) {
    int i = 0, r = 0, l = 0;

    while (r < rsize && l < lsize) {
        if (rarr[r] < larr[l]) {
            arr[i++] = rarr[r++];
        } else {
            arr[i++] = larr[l++];
        }
    }
    while (r < rsize) {
        arr[i++] = rarr[r++];
    }
    while (l < lsize) {
        arr[i++] = larr[l++];
    }
}

void mergeSort(int *arr, int length) {
    if (length > 1) {
        int l1 = length / 2;
        int l2 = length - l1;
        int rarr[l1], larr[l2];

        for (int i = 0; i < l1; i++) {
            rarr[i] = arr[i];
        }
        for (int i = l1; i < length; i++) {
            larr[i - l1] = arr[i];
        }

        mergeSort(rarr, l1);
        mergeSort(larr, l2);
        mergeArr(rarr, larr, arr, l1, l2);
        // will free(rarr); free(larr); make any difference in space complexity
    }
}

int main() {
    int arr[5] = { 1, 10, 2, 7, 5 };
    mergeSort(arr, 5);
    for (int i = 0; i < 5; i++)
        cout << arr[i] << " ";
}

Answer 1

释放临时数组不会影响 space 复杂度，因为我们必须考虑最大内存消耗 - 它大约是初始数组的大小。

从性能的角度来看，在排序开始时分配一次临时存储似乎是合理的，在每个阶段重用它，并在所有工作完成后释放它。

Answer 2

对此我有很多话要说。来自 C++ pov 的更多内容：

int rarr[l1],larr[l2]; - 这是非法的 c++。这只是 g++ 提供的扩展，对其他编译器无效。你应该做 int* rarr = new int[l1]; 或者更好地使用 std::vector: std::vector<int> rarr(l1).
如果你做的是前者（动态分配使用 new 即 int* rarr = new int[l1]），你必须自己管理内存。所以当你用完它时，你必须删除它：delete[] rarr。请注意，malloc 和 free 不是 c++，它们是 c。 new 和 delete 是 allocating/deallocating 内存的 c++ 方式。
如果您使用矢量，c++ 将处理 deletion/deallocation 内存，因此您不必担心。

现在回到您最初的问题：这样的想法是否会提高您的 space 复杂性：答案是否。它不会。

为什么？考虑一下您正在使用的最大临时存储空间。检查递归的第一个案例。你用的space不就是O(N)吗？因为 larr 和 rarr 的大小都是 N/2。此外，space 复杂度是 O(N) 假设正在释放临时存储。如果不知何故 space 没有被释放，space 复杂度将增加到 O(N)+2*(N/2)+4*O(N/4).... 即 O(Nlog2N) 因为递归的每一步都分配一些 space 它是不自由。

Answer 3

在你的实现中，左右数组定义了自动存储，所以函数释放时是自动的returns但是它带来了两个问题：

足够大的数组将调用未定义的行为，因为分配太多space自动存储会导致堆栈溢出。
可变大小的数组不是标准的 C++。您依赖于特定于编译器的扩展。

您的函数使用的最大堆栈 space 与 N 成正比，因此 space 复杂度为 O(N) 作为预期的。你可以用 new 分配这些数组，当然你必须用 delete 释放它们，否则你会发生内存泄漏，并且丢失的内存量将与N*log2(N).

另一种方法是使用临时数组，在初始调用时分配并传递给递归函数。

另请注意，左右数组的名称非常混乱。 rarr 实际上在 larr 的左边！

这是修改后的版本：

#include <iostream>

using namespace std;

void mergeArr(int *larr, int *rarr, int *arr, int lsize, int rsize) {
    int i = 0, r = 0, l = 0;

    while (l < lsize && r < rsize) {
        if (larr[l] <= rarr[r]) {
            arr[i++] = larr[l++];
        } else {
            arr[i++] = rarr[r++];
        }
    }
    while (l < lsize) {
        arr[i++] = larr[l++];
    }
    while (r < rsize) {
        arr[i++] = rarr[r++];
    }
}

void mergeSort(int *arr, int length) {
    if (length > 1) {
        int l1 = length / 2;
        int l2 = length - l1;
        int *larr = new int[l1];
        int *rarr = new int[l2];

        for (int i = 0; i < l1; i++) {
            larr[i] = arr[i];
        }
        for (int i = l1; i < length; i++) {
            rarr[i - l1] = arr[i];
        }

        mergeSort(larr, l1);
        mergeSort(rarr, l2);
        mergeArr(larr, rarr, arr, l1, l2);
        delete[] larr;
        delete[] rarr;
    }
}

int main() {
    int arr[] = { 1, 10, 2, 7, 5 };
    int length = sizeof arr / sizeof *arr;
    mergeSort(arr, length);
    for (int i = 0; i < length; i++) {
        cout << arr[i] << " ";
    }
    return 0;
}

在合并排序算法中，在合并数组后释放左右子数组是否会对 space 复杂度产生影响？

In merge sort algorithm, will freeing the left and right sub arrays after the arrays have been merged make any difference in the space complexity?

c++

algorithm

sorting

mergesort

space-complexity