在合并排序算法中，合并数组后释放左右子数组对空间复杂度有什么影响吗？

Question

在用于合并排序的教程视频之一中，曾提到，一旦左右子数组必须合并到父数组，为了降低空间复杂性，我们需要释放为左右分配的内存子数组。但是，只要我们退出函数调用，局部变量就会被破坏。如果我错了，请纠正我。那么释放内存的行为会有所不同吗？

这是我编写的代码：

#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

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

1. int rarr[l1],larr[l2];-这是非法的c ++。这只是g ++提供的扩展，在其他编译器中无效。您应该执行int* rarr = new int[l1];，甚至最好使用std::vector：std::vector<int> rarr(l1)。
2. [如果您正在做前者（使用new，即int* rarr = new int[l1]进行动态分配），则必须自行管理内存。因此，使用完毕后，您必须将其删除：delete[] rarr。请注意，malloc和free不是c ++，而是c。 new和delete是分配内存的c ++方法。
3. 如果使用向量，c ++将处理内存的删除/重新分配，因此您不必担心。

现在回到您的原始问题：这样的想法是否会改善您的空间复杂性：答案是NO。不会的

为什么？考虑一下您正在使用的最大临时存储空间。检查您的递归的第一种情况。您使用的是O(N)空间吗？因为larr和rarr的大小均为N/2。此外，假设要释放临时存储，则空间复杂度为O(N)。如果以某种方式没有释放空间，则空间复杂度将增加到O(N)+2*(N/2)+4*O(N/4)....，即O(Nlog2N)，因为递归的每个步骤都分配了一些没有释放的空间。

Answer 2

释放临时数组不会影响空间复杂性，因为我们必须考虑最大的内存消耗-它与初始数组的大小有关。

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

Answer 3

在您的实现中，左右数组是用自动存储定义的，所以当函数返回时，自动释放是自动的，但是会带来两个问题：

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

您的函数使用的最大堆栈空间与N成正比，因此空间复杂度为预期的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;
}