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

帰納法による: の計算がfor allfib(k)よりも少ない場合、の計算書については、C*2^kk < nfib(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( for 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

再帰方程式を解く必要があります。

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

3 に答える 3