algorithm - 大哦运行时分析如下代码

Question

public static long A (int N) {
  if (N <= 1) 
    return 1;

  return N + A(N-1) + A(N-2);
}

这是我的方法:堆栈将有 N-1 + N-2 次调用。也就是 N + N 和 2N。

然而答案是 2^N。我不太明白。

Answer 1

这是一种非常非正式的思考方式。

假设 N=10。然后进行 2 次调用，一次调用 N=9，一次调用 N=8。对于其中的每一个，也将进行 2 次调用，对于 N=9，一次调用 N=8 和 N=7，对于 N=8，一次调用 N=7 和 N=6。

因此每当 N 增加 1 时，调用次数将乘以 2。

因此，O(2^N) 是正确的。