function Pangkat ( x : integer,
n : integer) à integer
//
algoritma untuk menghitung nilai xn secara rekursif
kamus :
x, n : integer
Algoritma :
//input : x dan
n
if ( n = 0 ) then
return 1
else
return ß
x * Pangkat (x, n - 1)
endif
//output : nilai xn
endfunction
Tampilan Perhitungan Pangkat Secara Rekursif
Penyelesaian
:
2. Operasi Dasar :
Base case : (n = 0)
Recursive case : ( x * Pangkat (x, n-1) )
Pilih operasi dasar dari salah satu kondisi base case / recursive case ?
Operasi dasar yang dipilih : =
yang dilakukan 1 kali setiap kali fungsi rekursif dipanggil
Maka T(n) adalah T(0) = 0 untuk n = 0
3. Perhatikan
apakah butuh best, worst, dan average case ?
Jika jumlah eksekusi suatu operasi dasar
bervariasi(berbeda) untuk berbagai input
berukuran sama, maka dibutuhkan
perhitungan best, worst, dan average case.
Maka :
Untuk input n
tertentu misal : 5, maka recursion treenya(pohon rekursifnya) selalu
sama. Banyak komputasi / pemanggilan fungsi rekursif tetap ( 5 kali ).
Jadi : tidak butuh best, worst, dan
average case.
4. Tentukan
hubungan / realasi recurrence, dengan sebuah kondisi awal, untuk jumlah waktu operasi dasar di eksekusi / di jalankan.
Jika
T(n) menyatakan banyaknya basic operation dieksekusi untuk input berukuran n
dan T(n - 1) menyatakan
banyaknya basic operation dieksekusi untuk input berukuran n-1.
Maka
: Hubungan T(n) dan T(n - 1) dinyatakan
dengan
T(0)
= 0 untuk n = 0 ( base
case/kasus dasar )
T(n) =
T(n – 1) + 1 untuk n > 0 (recursive case/kasus rekursif)
5. Menyelesaikan
solusi relasi rekurens yang didapat di nomor 4 (t(n))
·
Untuk
mengetahui kelas efisiensi waktunya kita harus menemukan persamaan langsung (
non recursive ) dari T(n).
·
Menggunakan
metode backward substitution, cari pola dari :
T(n)
= T(n – 1) + 1
T(n)
= (T(n – 2) + 1) + 1 = T(n)
= T(n – 2) + 2
T(n)
= (T(n – 3) + 1 ) + 2 = T(n) =
T(n – 3) + 3
Dan
seterusnya
·
Pola
atau bentuk umumyang didapat adalah
T(n)
= T(n – i) + i
·
Nilai
kondisi awal T(0) disubstitution ke T(n – i) pada bentuk umum T(n).
T(n)
= T(n - i) + i
T(n)
= T(0) + i
T(n)
= 0 + i
T(n)
= i
·
Subtitusi
tersebut mensyaratkan
T(n
– i) = T(0)
n – i
= 0
i = n
nilai i = n disubtitusikan ke bentuk umum
T(n)
= i
Sehingga
T(n)
= i
T(n)
= n
Jadi
T(n) merupakan anggota kelas n
6. Tentukan
g(n) dimana t(n) termasuk salah satu O(g(n)),Ω(g(n)), atau Ɵ(g(n))
Jadi
: T(n) = n
T(n)
є O(n)
Sumber :
- Munir, Renaldi. (2011). Algoritma & Pemrogramman Dalam Bahasa Pascal dan C. (edisi revisi). Bandung ; INFORMATIKA.
- https://zaharaahyesa.wordpress.com/2014/04/10/algoritma-rekursif/
0 komentar:
Posting Komentar