3

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

算法:

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

4

3 回答 3

4

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

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

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

F(n): if n<2 then return n else return F(n-1) + F(n-1)
于 2010-03-01T14:25:13.417 回答
3

通过归纳:如果 的计算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)

于 2010-03-01T01:16:34.827 回答
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 回答