以下伪代码的大O复杂度是什么？

下面的计算复杂度是多少伪代码？以下伪代码的大O复杂度是什么？

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

在现实世界中，调用将得到优化，并产生线性复杂，但与RAM模型上大哦计算，这将是复杂性？ 2^n？

这样的复杂性似乎是2^n，但可以减少到n。 –

是的，这似乎是'2^n'。 – 2013-11-27 09:36:07

在每次递归时，递归树都以2的因子分支。所以在递归结束时，你有一个深度为“n”的完整二叉树，所以顺序是“Θ（2^n）”。 – Shahbaz

该算法目前形式的复杂性确实是O（2 ⁿ），因为在每个呼叫级别上，呼叫次数都会增加两次。

第一呼叫（递归（N））构成一个呼叫

下一级（递归（N-1））构成2个呼叫

在基础案例（递归（1）），它构成2 ^n-1来电。

因此的功能的总呼叫数量是1 + 2 + ... + 2 ^n-1个 = 2 ^Ñ -1

所以复杂度为O（2 ^Ñ）。

其他景点：

正如你所说，这可以很容易地制成O（n）的（或者是O（log n）的使用快速幂这种特殊情况下）的记忆化，或者动态规划。

2013-11-27 09:38:56 justhalf

你的复杂性将是 enter image description here

为什么会这样呢？简单mathematical induction证明：

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复杂性将是共用的情况下（从数学归纳法的定义） enter image description here 。

2013-11-27 09:44:27

回答