请问以下给出的递归函数的空间复杂度是多少？

参考代码 #

void s (int n)
{
    if(n == 0) return;
    // n^2 space
    vector<vector<int>> a(n, vector<int>(n));
    for(int i = 0; i < n; ++i)
      for(int j = 0; j < n; ++j)
         a[i][j] = i * j;
    s(n-1);
}

复杂度推导 #

我们从两部分统计空间占用：

• 递归栈空间：函数递归调用深度为n+1（从s(n)一直调用到s(0)），每个栈帧的空间是固定的O(1)，所以这部分总复杂度为O(n)，属于低阶项，对最终结果影响很小。
• 局部vector占用空间：每个调用层级创建的二维vectora的生命周期覆盖整个当前函数的执行周期，调用下一层s(n-1)时，当前层的a还未被析构，因此所有层级的vector空间需要累加。总大小为1到n的平方和，量级为O(n³)。

最终结果 #

忽略低阶的栈空间占用，该递归函数的总空间复杂度为O(n³)。

补充说明：如果编译器开启了尾递归优化，调用下一层递归前会销毁当前层的局部变量a并复用栈帧，此时总空间复杂度会降为O(n²)。但常规算法复杂度分析默认不依赖特定编译器优化行为，因此标准结果为O(n³)。

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