algorithm - 解决斐波那契数的递归

Question

我不知道这个算法中的数学，可以使用一些帮助。

算法：

if n<2 then

  return n

else return fibonacci(n-1) + fibonacci(n-2)

陈述

n < 2 是 O(1)
时间 n >=2 是 O(1)
返回 n 是 O(1) 时间 n>=2 是 - 返回 fib(n-1) + fib(n-2) 是 -

时间 n>=2 为 T(n-1) + T(n-2) +O(1)

总计： O(1) T(n-1) + T(n-2) + O(1)
T(n) = O(1) 如果 n < 2
T(n) = T(n-1) + T (n-2) + O(1) 如果 n>=2

score 4 · Accepted Answer

我想你应该注意到这个函数的递归关系非常熟悉。您可以通过按名称查找这种非常熟悉的重复出现的确切增长速度。

但是，如果您无法进行直观的飞跃，您可以尝试使用简化的问题来限制运行时。本质上，您以保证增加运行时间同时使其更简单的方式修改算法。然后你计算出新算法的运行时间，它给你一个上限。

例如，此算法必须花费更长的时间并且更易于分析：

F(n): if n<2 then return n else return F(n-1) + F(n-1)

score 3 · Accepted Answer

通过归纳：如果的计算fib(k)少于C*2^kall k < n，对于fib(n)我们已经得到的计算书

T(n) = T(n-1) + T(n-2) + K < C*2^(n-1) + С*2^(n-2) + K
     = 0.75*C*2^n + K < C*2^n

足够大C（对于C > K/0.25, as 2^n > 1）。这证明了T(n) < C*2^n，即T(n) = O(2^n)。

（这里T(n)是计算的时间fib(n)，是计算和[已经] 计算时K所需的恒定时间。）fib(n)fib(n-1)fib(b-1)

score 0 · Accepted Answer

0

您需要求解递推方程：

T(0) = 1
T(1) = 1
T(n) = T(n-1) + T(n-2), for all n > 1

于 2010-03-01T01:28:38.107 回答

3 回答 3