如何计算时间和内存的复杂度

Question

我有以下代码

public int X(int n)
{
    if (n == 0)
        return 0;

    if (n == 1)
        return 1;
    else
        return (X(n- 1) + X(n- 2));
}

我想计算这段代码的时间和内存的复杂度

我的代码由一个常量检查组成 if (n == 0) return 0; 所以这将花费一个常量时间假设 c 所以我们有 c or c 或递归函数的计算我可以' t 计算

谁能帮我解决这个问题？

Answer 1

要计算 X(n) 的值，您正在计算 X(n-1) 和 X(n-2)

   So T(n) = T(n-1) + T(n-2);

      T(0) = 1
      T(1) = 1

这是指数 O(2^n)

如果您想详细证明 O(2^n)，请查看 here。

Space 复杂度是线性的。

（准确地说，如果你考虑递归的栈space，它是O(n)）

How to calculate the complexity of time and memory