Analisis Matematis Algoritma Rekursif (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 :

Analisis Matematis Algoritma Rekursif (2)

Menganalisis algoritma Menghitung c x d dengan c dan d bilangan bulat positif.

Berikut adalah algoritmanya :

Function perkalian(input c,d: integer)→integer

Kamus:

Algoritma:

If d = 1 then

    
   c ← c

else

   
   c ← c + perkalian(c,d-1)

endif

endfunction

penyelesaian :

      

Analisis Matematis Algoritma Rekursif (1)

Pada pertemuan kali ini kita akan menjelaskan tentang analisis algoritma rekursif.

Algoritma rekursif adalah suatu subrutin atau fungsi atau prosedur yang memanggil dirinya sendiri.

Syarat bentuk rekursif adalah :

Basis (kondisi terminal/kondisi terbaik) dan recurrence (yang melibatkan parameter yang nilainya menuju kondisi terminal).

Dan berikut adalah langkah analisis algoritmanya:

      1.Tentukan parameter ukuran input.

      2.Tentukan operasi dasar.

3.Perhatikan apakah butuh worst, average, dan best-case. Jika jumlah eksekusi suatu operasi dasar bervariasi untuk berbagai input berukuran sama maka dibutuhkan perhitungan worst, average, dan best-case.

      4.Tentukan hubungan recurrence, dengan sebuah kondisi awal, untuk jumlah waktu operasi dasar dieksekusi.

      5. Selesaikan recurrence atau setidaknya pastikan OoG dari solusi.

Berikut contoh menganalisa algoritma pangkat sebagai berikut: