我试图使用递归树找到斐波那契级数的复杂性，并得出height of tree = O(n)最坏情况，cost of each level = cn，因此complexity = n*n=n^2
为什么是O(2^n) ?
朴素递归fibonacci的复杂度确实是2n。
T(n) = T(n-1) + T(n-2) = T(n-2) + T(n-3) + T(n-3) + T(n-4) =
= T(n-3) + T(n-4) + T(n-4) + T(n-5) + T(n-4) + T(n-5) + T(n-5) + T(n-6) = ...
在每一步中调用T两次，因此将提供最终的渐近屏障:T(n) = 2⋅2⋅...⋅2 = 2ⁿ
奖励:斐波那契的最佳理论实现实际上是一个接近的公式，使用黄金分割:
Fib(n) = (φⁿ – (–φ)⁻ⁿ)/sqrt(5) [where φ is the golden ratio]
(然而，它在现实生活中受到精度误差的影响，因为浮点运算是不精确的)
fib(n)的递归树应该是这样的:
n
/
n-1 n-2 --------- maximum 2^1 additions
/ /
n-2 n-3 n-3 n-4 -------- maximum 2^2 additions
/
n-3 n-4 -------- maximum 2^3 additions
........
-------- maximum 2^(n-1) additions
- 在2^(n-1)中使用n-1，因为对于fib(5)，我们最终将下降到fib(1)
- 内部节点数=叶子数-1 = 2^(n-1) -1
- 新增节点数=内部节点数+叶子数=(2^1 + 2^2 + 2^3 +…)+ 2^(n-1)
- 我们可以将内部节点的数量替换为2^(n-1) -1，因为它总是小于这个值:= 2^(n-1) -1 + 2^(n-1)~ 2 ^ n
你是正确的，树的深度是O(n)，但你并没有在每一层做O(n)的工作。在每个级别上，每个递归调用都要做O(1)个工作，但是每个递归调用都会贡献两个新的递归调用，一个在它下面的级别上，一个在它下面的级别上。这意味着当你在递归树中越走越远时，每层的调用数量会呈指数级增长。
有趣的是，你实际上可以确定计算F(n)所需的确切调用次数为2F(n + 1) - 1，其中F(n)是第n个斐波那契数。我们可以用归纳法证明。作为基本情况，为了计算F(0)或F(1)，我们只需要对函数进行一次调用，而不进行任何新的调用。我们设L(n)是计算F(n)所需的调用次数。然后是
L (0) = 1 = 2 * 1 - 1 = 2 (1) - 1 = 2 f (0 + 1) - 1
L (1) = 1 = 2 * 1 - 1 = 2 (2) - 1 = 2 f (1 + 1) - 1
现在，对于归纳步骤，假设对于所有n' <N，带N>
1 + L(n - 1) + L(n - 2)
= 1 + 2 f (n - 1) + 1 - 1 + 2 f ((n - 2) + 1) - 1
= 2F(n) + 2F(n - 1) - 1
= 2(F(n) + F(n - 1)) - 1
= 2(F(n + 1)) - 1
= 2F(n + 1) - 1
归纳完毕。
此时，您可以使用Binet的公式来显示L (n) = 2(1/·拉迪奇;5)(((1 +·拉迪奇;5)/2)<一口> n> n> /blockquote>
,因此L O (n) =(((1 +·拉迪奇;5)/2)<一口> n> 的约定
φ;=(1 + &根号;5)/2 &近似;1.6
我们有
L(n) = Θ(φn)
由于φ& lt;2，这是0 (2n)(使用little-o符号)。
有趣的是，我为这个系列选择了L(n)这个名字，因为这个系列被称为莱昂纳多数。除了在这里使用之外，它还出现在对平滑排序算法的分析中。
希望这对你有帮助!
这样看。假设对于k <= n，通过递归计算F(k)，即kth斐波那契数的复杂度最多为2^k。这是我们的归纳假设。则递归计算F(n + 1)的复杂度为
F(n + 1) = F(n) + F(n - 1)
2^n + 2^(n - 1)的。注意,
2^n + 2^(n - 1) = 2 * 2^n / 2 + 2^n / 2 = 3 * 2^n / 2 <= 2 * 2^n = 2^(n + 1).
我们已经通过归纳证明，通过递归计算F(k)最多是2^k的说法是正确的。
t(n)=t(n-1)+t(n-2)可通过树形法求解:
t(n-1) + t(n-2) 2^1=2
| |
t(n-2)+t(n-3) t(n-3)+t(n-4) 2^2=4
. . 2^3=8
. . .
. . .
同样适用于最后一层。2 ^ n
使总时间复杂度=>2+4+8+.....2^n求解上述gp后，我们得到时间复杂度为O(2^n)
斐波那契级数的复杂度为O(F(k))，其中F(k)为第k个斐波那契数。这可以用归纳法来证明。这对于基于基的情况是微不足道的。假设对于所有k<=n，计算F(k)的复杂度为c*F(k) + o(F(k))，那么对于k =n +1，计算F(n+1)的复杂度为c*F(n) + o(F(n-1)) = c*(F(n) + F(n-1)) + o(F(n-1))。
递归Fibonacci级数的复杂度为2^n:
这将是递归Fibonacci
T(n)=T(n-1)+T(n-2) No of elements 2
现在用代入法求解这个关系(代入T(n-1)和T(n-2)的值)
T(n)=T(n-2)+2*T(n-3)+T(n-4) No of elements 4=2^2
再次替换上述项的值，我们将得到
T(n)=T(n-3)+3*T(n-4)+3*T(n-5)+T(n-6) No of elements 8=2^3
完全求解后，得到
T(n)={T(n-k)+---------+---------}----------------------------->2^k eq(3)
这意味着在任何级别上的最大递归调用数将不超过2^n。
对于公式3中的所有递归调用都是ϴ(1)，因此时间复杂度将为2^n* ϴ(1)=2^n
斐波那契数计算的O(2^n)复杂度仅适用于递归方法。使用一些额外的空间，您可以使用O(n)获得更好的性能。
public static int fibonacci(int n) throws Exception {
if (n < 0)
throws new Exception("Can't be a negative integer")
if (n <= 1)
return n;
int s = 0, s1 = 0, s2 = 1;
for(int i= 2; i<=n; i++) {
s = s1 + s2;
s1 = s2;
s2 = s;
}
return s;
}
我无法抗拒将Fib的线性时间迭代算法连接到指数时间递归算法的诱惑:如果有人读了Jon Bentley关于"编写高效算法"的精彩小书，我相信这是一个简单的"缓存"案例:每当计算Fib(k)时，将其存储在数组fibached [k]中。每当Fib(j)被调用时，首先检查它是否被缓存在fibachached [j]中;如果是，返回值;如果不是，使用递归。