递归插入排序算法的空间复杂度为何是O(n)而非O(1)？

递归插入排序实现代码 #

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)，想知道其中的原因。

你忽略了递归调用栈的空间开销。

虽然数组是按引用传递，没有额外开辟新的数组存储空间，但递归函数每执行一次调用，都会在程序的调用栈上创建一个栈帧——这个栈帧会保存当前函数的参数（比如n的当前值）、局部变量（val、j）以及返回地址等信息。

对于这个递归插入排序，递归调用的深度是n：从recursiveInsertionSort(arr, n)开始，依次调用到recursiveInsertionSort(arr, n-1)、recursiveInsertionSort(arr, n-2)……直到recursiveInsertionSort(arr, 1)，此时调用栈上会同时存在n个栈帧。每个栈帧的空间是常数级，但总空间开销累加后就是O(n)，这就是整个算法空间复杂度为O(n)的原因。

如果是迭代版本的插入排序，因为不需要递归调用栈的开销，空间复杂度才是O(1)。

内容的提问来源于stack exchange，提问作者user21661616