这个递归插入排序算法的空间复杂度是多少？

Question

void recursiveInsertionSort(vector<int> &arr, int n) {
    if (n <= 1)
        return;
    recursiveInsertionSort(arr, n - 1);
    int val = arr[n - 1], j = n - 2;
    for (j = n - 2; j >= 0 && arr[j] > val; --j)
        arr[j + 1] = arr[j];
    arr[j + 1] = val;
}

为什么每个人都说这个的空间复杂度是 O(n)，因为我通过引用传递数组。

Answer 1

数据向量仍在某处占用空间，即使您的函数通过引用获取它也是如此。

但是即使你不想考虑这个空间，你的代码仍然需要 O(n) 空间。

这是因为您将有 O(n) 次递归调用，每个调用（在您的情况下）占用调用堆栈上的 O(1) 空间（用于存储参数等）。当您处于最内层的递归调用中时，将需要所有这些空间。

一共是O(n)空间.

Answer 2

O(n) 这里表示算法按照输入数据大小的顺序使用空间。这正是你所说的：它使用输入数据大小的一倍。 （虽然不计算使用的堆栈空间）

即使你只复制了一个数组，它仍然是 O(n)，因为 O(2*n) ~ O(n)。如果你按值传递数组，那么空间使用会增加，可能达到 O(n^2)。

Answer 3

它消耗 O(N) 线性空间复杂度，因为在每次递归调用中，您都在创建一个

int

类型的值（val），它占用 O(1) 空间，并且函数调用的大小为 N 次数组，因此值占用 O(1) * N 空间，这导致算法的整体空间复杂度为 O(N)。

O(1) * N = O(N)