BigO(n)或theta(n)在递归中的辅助空间

Question

我正在写这个递归函数来计算前n个数字的和。我知道它有一个直接的公式，但我这样做是为了练习递归。

int sum(int n)
{
if (n==0)
return 0;

return n + sum(n-1);
}

我很困惑这个函数是否需要辅助空格，是O(n)还是theta(n)?

Answer 1

未经编译器优化，空间复杂度可以表示为O(n)或Θ(n)。前者是指空间增长速度不超过c*n，其中c为常数;后者是指空间增长速度介于c1*n和c2*n之间，其中c1和c2为常数。你可以在这里看到更正式的定义。

编译器优化后，情况就不同了。

sum(int):
xor     eax, eax
test    edi, edi
je      .L1
.L2:
add     eax, edi
sub     edi, 1
jne     .L2
.L1:
ret

这是GCC 12.1在优化级别-O2下生成的x64汇编代码，可以看到没有递归，因此空间复杂度为O(1)。