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

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(1)），因为我通过引用传递数组。

但我被告知它实际上是 O(n)。这是为什么 ？

Answer 1

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

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

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

总共是O(n) 空间。

注意：
val在这种情况下，在任何给定时间实际上只有 1 个实例处于活动状态，因为它是在递归调用之后分配的。
但即使它是在调用之前定义和使用的，每次调用仍然是 O(1) 空间，并且最终结果是相同的。