-2

このプログラムは、フィボナッチ数を計算します。再帰関係を使用して時間複雑度を調べたい。

Fib(n)
if n<=1
  return n
else
  x= Fib(n-1)
  y= Fib(n-2)
  return x+y

このプログラムの漸化式は T(n)=T(n-1)+T(n-2)+c

私はそれを消費しようとしましたが、解決策を見つけることができませんでした.

 =2T(n-1)+T(n-3)+c+c
 =3T(n-3)+2T(n-4)+c+c+3c
 =5T(n-4)+3T(n-3)+c+c+3c+5c
 -------------------------
 -------------------------
 -------------------------
4

3 に答える 3

1

関数を何回呼び出すかを考える必要があります。各呼び出しは 2 回行われるため、二分木が作成されます。

n

(n-1)--------------(n-2)

(n-2)--(n-3)------(n-3)---(n-4)

等々。

最初に 1 に達したときのツリーのレベルを考慮し、それ以下はすべて無視します。これはレベル n/2 で発生します (各レベルの最小数が右端であり、常に 2 ずつ減少するため)。n/2 までの各レベルのノードは、常に前のレベルの 2 倍であることは明らかです。

したがって、ノードの総数は 1 + 2 + 2^2 + ... + 2^(n/2) = 2^(n/2+1) - 1 = O(2^(n/2)) です。

これは、時間計算量が少なくとも指数関数的であることを意味します。

おそらくもっと正確に計算できますが、実際には、この実装を避けるにはこれで十分です。

于 2013-04-03T09:11:42.940 に答える
0

再帰関係について注意すべきことは、それがフィボナッチ再帰自体と同じであるということです。これは、c計算しているフィボナッチ数に関係なく、作業時間の単位を実行していることを意味します。計算した最初の数ステップから自分で確認できます。はc、フィボナッチ数のように成長し始めます。

基本的に、再発は O(Fib(n)) になります。フィボナッチ数は で指数関数的でnあるため、指数関数的な作業を行うことになります。

これを行うためのより良い方法は、数字の 1 つを覚えておくことです。このような：

Fib(n):
    if n <= 2:
        return 1,0
    else:
        x,y = Fib(n-1)
        return x+y,x

を呼び出すとFib(n)、Fib(n) と Fib(n-1) の 2 つの値が得られます。あなたが返す余分なxものは Fib(n-2) を「覚えている」ので、2回計算する必要はありません。この繰り返しはT(n) = T(n-1) + c、つまり O(n) になります。

それができたら、これを素敵な小さな for ループに減らすことができます。

x = 1, y = 0
for i from 3 to n:
    x,y = x+y,x
于 2013-04-03T09:27:49.513 に答える