Perbaikan 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:

function pangkat(input p,n: integer)→ integer

Kamus:

p,n : integer

 
Algoritma:

If n = 0 then

   pangkat ← 1

else

   pangkat ← p*pangkat(p,n-1)

endif

endfunction

Penyelesaian :

Basis :

Pⁿ = 1 jika n = 0;

recurrence :

pⁿ =  p * p^n-1 jika n > 0;

      

      3.      penyelesaian recurrence:

       

      Operasi  dasar utama =perkalian(*)

      Perkalian(*)=2

      F(x-1)+2

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

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

      T(n-2)= T(n-3)+2

      T(n-3)= T(n-4)+2

      Titik henti T(1)=0

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

                      = T(n-2)+2+2

                      = T(n-3)+2+2+2

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

      n-i=1

     -i=1-n

      i=n-1

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

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

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

         =T(1)+2n-2

         =0+2n-2

         =2n-2 £ O(n)