Space 递归函数的复杂度 (Time & Space)

Question

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

顺便说一下，我尝试解决时间复杂度，结果发现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 times * T(n - 3 * k) = 2 ^ k * T(n - 3k)

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

一次只有一个函数运行，堆栈深度最大可以是k。所以，space 复杂度是 n / 3 或 O(n)

Space complexity of recursive function (Time & Space)