c - 递归函数的空间复杂度(Time & Space)

Question

下面有递归函数，我没有计算时空复杂度。我查看了一些资源，但对我的理解还不够清楚。谁能用最简单的方式解释一下求解的方法，并回答问题？

顺便说一下，我试图解决时间复杂度，我发现 O(2^n)。是否正确？

int func(int n) { 
     if (n < 3)
         return 3;
     else {
         return func(n-3)*func(n-3);
     }
}

Answer 1

是的，时间复杂度确实是O(2 ^ n)。

时间复杂度的递推关系为:T(n) = 2 * T(n - 3)

将上述等式应用 k 次:T(n) = 2 * 2 * 2 ... k 次 * T(n - 3 * k) = 2 ^ k * T(n - 3k)

当k为n/3时，T(n) = 2 ^ k = 2 ^ (n/3) = O(2 ^ n)

一次只有一个函数在运行，堆栈深度最大可以是k。因此，空间复杂度为 n/3 或 O(n)