大哦运行时分析如下代码

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) 是正确的。

Answer 2

每次调用 A 最多会产生 2 次对 A 的调用，其中 N=1 的基本情况会产生恒定成本。总的来说，对 A 的调用最多创建一个高度为 N 的调用的完整二叉树，其中有

sum_{i=0}^{N}2^i = 2^{N+1}-1 in O(2^{N})

个节点。更正式地说，运行时边界可以通过归纳证明获得。

Answer 3

你也可以这么想：

复杂度(N) = 复杂度(N-1) + 复杂度(N-2)。

听起来像斐波那契数列吧？

复杂度(N) =

因此 O(phi^N)。其中 phi=[1+sqrt(5)]/2

Big-oh runtime analysis of the following code