В алгоритме сортировки слиянием, будет ли освобождение левого и правого подмассивов после слияния массивов какой-либо разницы в сложности пространства?

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]; - это нелегально с ++. Это просто расширение, предоставляемое g ++ и недопустимое для других компиляторов. Вам следует либо int* rarr = new int[l1];, либо еще лучше использовать std::vector: std::vector<int> rarr(l1).
2. Если вы делаете первое (динамическое распределение c с использованием new, то есть int* rarr = new int[l1]), у вас есть управлять памятью самостоятельно. Поэтому, когда вы закончите использовать его, вы должны удалить его: delete[] rarr. Имейте в виду, malloc и free - это не c ++, они c. new и delete - это способ выделения / освобождения памяти c ++.
3. Если вы используете вектор, c ++ будет обрабатывать удаление / освобождение памяти, поэтому вам не нужно беспокоиться.

Теперь вернемся к вашему первоначальному вопросу: улучшит ли ваша идея такую ​​сложность пространства: ответ НЕТ . Не будет

Почему? Подумайте о максимальном временном хранилище, которое вы используете. Проверьте первый случай вашей рекурсии. Разве это не пространство, которое вы используете O(N)? потому что larr и rarr будут иметь размер N/2. Более того, сложность пространства составляет O(N) при условии освобождения временного хранилища. Если пространство каким-либо образом не освобождается, сложность пространства увеличивается до O(N)+2*(N/2)+4*O(N/4)...., что составляет O(Nlog2N), поскольку каждый шаг рекурсии выделяет некоторое пространство, которое оно не освобождает.

Answer 2

В вашей реализации левый и правый массивы определяются с помощью автоматического c хранилища, поэтому освобождение автоматически c, когда функция возвращается, но это создает 2 проблемы:

• достаточно большой Массив вызовет неопределенное поведение, поскольку выделение слишком большого пространства с помощью автоматического c хранилища приведет к переполнению стека .
• массивов переменного размера не являются стандартным C ++. Вы полагаетесь на расширение 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;
}

Answer 3

Освобождение временных массивов не влияет на сложность пространства, потому что мы должны учитывать максимальное потребление памяти - это примерно размер исходного массива.

С точки зрения производительности, кажется разумным выделять временное хранилище один раз в начало сортировки, повторное использование на каждом этапе и освобождение после завершения всей работы.