"nested" 递归函数的时间和 space 复杂度

Question

在之前的intro to cs exam中有一道题：计算函数f1的space和时间复杂度作为n的函数，假设malloc(n)的时间复杂度为O(1) 及其 space 复杂度为 O(n)。

int f1(int n) {
    if(n < 3)
        return 1;

    int* arr = (int*) malloc(sizeof(int) * n);
    f1(f1(n – 3));
    free(arr);

    return n;
}

官方的解决方案是：时间复杂度：O(2^(n/3))，space复杂度：O(n^2)

我试图解决它，但我不知道如何解决，直到我在我的笔记本上看到一张纸条说：因为函数 returns n 那么我们可以处理 f(f(n-3))作为 f(n-3)+f(n-3) 或作为 2f(n-3)。在这种情况下，问题变得与这个问题非常相似：

我试过用这种方法解决，我得到了正确的答案。

对于时间复杂度：

T(n)=2T(n-3)+1 , T(0)=1

T(n-3)=2T(n-3*2)+1

T(n)=2*2T(n-3*2)+2+1

T(n-3*2)=2T(n-3*3)+1

T(n)=2*2*2T(n-3*3)+2*2+2+1

...

T(n)=(2^k)T(n-3*k)+2^(k-1)+...+2^2+2+1

n-3*k=0

k=n/3

===> 2^(n/3)+...+2^2+2+1=2^(n/3)[1+(1/2)+( 1/2^2)+...]=2^(n/3)*常数

这样我得到了O(2^(n/3))

对于 space 复杂度：树的深度是 n/3 并且每次我们执行 malloc 所以我们得到 (n/3)^2 因此 O(n^2).

我的问题：

为什么我们可以将 f1(f1(n – 3)) 视为 f1(n-3)+f1(n-3) 或 2f1(n-3)？
如果函数没有returnn而是改变了它，例如：returnn/3而不是returnn，那么我们如何解决呢？我们是否将其视为 2f1((n-3)/3)？
如果我们不能始终将 f1(f1(n – 3)) 视为 f1(n-3)+f1(n-3) 或 2f1(n-3) 那么我们如何绘制递归树以及我们如何使用归纳法 T(n) 编写和求解它？

Answer 1

为什么我们可以将 f1(f1(n – 3)) 视为 f1(n-3)+f1(n-3) 或 2f1(n-3) ?

因为i)嵌套的f1先求值，它的return值用来调用外层的f1；所以这些嵌套调用等同于：
```
int result = f1(n - 3);
f1(result);
```
... 和 ii) f1 的 return 值只是它的参数（基本情况除外，但渐近无关紧要），所以上面进一步等价至：
```
f1(n - 3);
f1(n - 3); // result = n - 3
```
如果函数没有return n而是改变了它，例如：return n/3而不是returnn，那我们怎么解决呢？我们是否将其视为 2f1((n-3)/3)?

只有外部调用受到影响。同样，使用之前的等效表达式：
```
f1(n - 3); // = (n - 3) / 3
f1((n - 3) / 3);
```
即只是 f1(n - 3) + f1((n - 3) / 3) 你的例子。
如果我们不能始终将 f1(f1(n – 3)) 视为 f1(n-3)+f1(n-3) 或 2f1(n -3) 那我们怎么画递归树，用归纳法T(n)怎么写和求解？

您始终可以像上面那样将它们分成两个单独的调用，再次记住，只有第二个调用会受到 return 结果的影响。如果这与 n - 3 不同，那么您将需要一个递归树而不是简单的扩展。看具体问题，不用说了。

"nested" 递归函数的时间和 space 复杂度

Time and space complexity of a "nested" recursive function

recursion

big-o

time-complexity

space-complexity