Perbaikan Rekuersif (3)

Menganalisis algoritma Menampilkan deret fibonacci.

Berikut adalah algoritmanya :

function fibo(input n:integer)→integer

Kamus:

Algoritma:

if(n=1) or (n=2)  then

    fibo ← 1

else

    fibo ←  fibo(n-1)+fibo(n-2)

endif

endfunction

penyelesaian :

      1.      Operasi dasar utama = penjumlahan

      

      2.      Menentukan hubungan recurrence

Basis :

Fibo = 1, jika n = 1 atau n = 2;

recurrence :

fibo =  (n-1)+ (n-2)

    

      penjumlahan(+)

      penjumlahan(+)=1

      [F(x-1)+F(x-2)+1]

      T(n)+[ T(n-1)+1]+[ T(n-2)+1]

      T(n-1)=[ T(n-1-1)+1]+[ T(n-2-2)+1]

      T(n-1)=[ T(n-2)+1]+[ T(n-4)+1]

      T(n-2)=[ T(n-3)+1]+[ T(n-6)+1]

      T(n-3)=[ T(n-4)+1]+[ T(n-8)+1]

      Titik henti = T(1)=0

      T(n)=[ T(n-1)+1]+[ T(n-2)+1]

          =[ T(n-2)+1+1]+[ T(n-4)+1+1]

          =[ T(n-3)+1+1+1]+[ T(n-4)+1+1+1]

      T(n)=[ T(n-i)+i]+[ T(n-2i)+i]

      n-i=1

      -i=1-n

       i=n-1

 

       T(n)=[ T(n-i)+i]+[ T(n-2i)+i]

          =T(-n(n-1))+(n-1)+ T(n-2(n-1))+n-i

          = T(n-n+1)+(n-1)+ T(n-2n+1)+n-i

          = T(1)+(n-1)+(-n+1)+(n-1)

          =0+(n-1)+(-n+1)+(n+1)

          =n-1 £ O(n)