以下伪码的大O复杂度是多少？

Question

以下伪码的计算复杂度是多少？

integer recursive (integer n) {
   if (n == 1)
      return (1);
   else
      return (recursive (n-1) + recursive (n-1));
}

在现实世界中，调用将得到优化并产生线性复杂性，但是在计算大o的内存模型下，复杂度是多少？2^n。

Answer 1

你的复杂性将是

​

为什么会这样呢？简单的数学归纳法证明：

• N=1:特例，计数步骤= 1。
• N=2，很明显

= 2，所以这是正确的

• 让它对N=K是正确的，也就是说，对于N=K，它将是

​

• 假设是N=K+1。recursive函数将递归地为N=K调用两次：recursive(K+1) = recursive(K) + recursive(K)，因为它遵循代码。这就是：

。所以，对于N=K+1我们有

步骤。

所以我们已经证明了N的复杂性

在一般情况下(从数学归纳的定义)。