Kompleksitas Waktu untuk Algoritma Rekursif

Kompleksitas Waktu untuk Algoritma Rekursif Bentuk rekursif : - suatu subrutin/fungsi/ prosedur yang memanggil dirinya sendiri. - Bentu dimana pemanggilan subrutin terdapat dalam body subrutin - Dengan rekursi, program akan lebih mudah dilihat Bentuk rekursi bertujuan untuk : - menyederhanakan penulisan program - menggantikan bentuk iterasi Syarat bentuk rekursif: - ada kondisi terminal (basis) - subroutine call yang melibatkan parameter yang nilainya menuju kondisi terminal (recurrence) Menghitung kompleksitas bentuk rekursif Untuk bentuk rekursif, digunakan teknik perhitungan kompleksitas dengan relasi rekurens. Contoh : 1. Menghitung faktorial Function Faktorial (input n : integer) → integer {menghasilkan nilai n!, n tidak negatif} Algoritma If n=0 then Return Else Return n*faktorial (n-1) Endif Kompleksitas waktu : - untuk kasus basis, tidak ada operasi perkalian → (0) - untuk kasus rekurens, kompleksitas waktu diukur dari jumlah perkalian (1) ditambah kompleksitas waktu untuk faktorial (n-1) Jadi relasi rekurrens : 0 ,n=0 ⎧ T (n ) = ⎨ ⎩T (n − 1) + 1 , n > 0

Desain & Analisis Algoritma – ZK Abdurahman Baizal

Kompleksitas waktu : T (n ) = 1 + T (n − 1) = 1 + 1 + T (n − 2) = 2 + T (n − 2) = 2 + 1 + T (n − 3) = 3 + T (n − 3) = ………. ………. = n + T(0) =n+0 Jadi T(n) = n T(n) ∈ O(n) 2. Menara Hanoi → Legenda di Hanoi, tentang kisah pendeta Budha bersama murid-muridnya.

B

A

C

Permasalahan : Bagaimana memindahkan seluruh piringan tersebut ke sebuah tiang yang lain (dari A ke B); setiap kali hanya satu piringan yang boleh dipindahkan, tetapi tidak boleh ada piringan besar di atas piringan kecil. Ada tiang perantara C. Kata pendeta, jika pemindahan berhasil dilakukan, maka DUNIA KIAMAT !!! Procedure Hanoi (input n, A, B, C:integer) Algoritma If n=1 then Write (‘Pindahkan piringan dari’,A,’ke’,B) Else Hanoi(n-1,A,C,B) Writeln(‘Pindahkan piringan dari’,A,’ke’,B) Hanoi(n-1,C,B,A) Endif


Relasi Rekurrens : 1 , n =1 ⎧ T (n ) = ⎨ ⎩2T (n − 1) + 1 , n > 1 Kompleksitas waktu : T (n ) = 1 + 2T (n − 1) = 1 + 2(1 + 2T (n − 2)) = 1 + 2 + 22 T (n − 2) = 1 + 2 + 22 (1 + 2T (n − 3)) = 1 + 2 + 22 + 23 T (n − 3) = ……. = ……. = 1 + 2 + 22 + ....... + 2 n − 2 + 2n −1T (1) = 1 + 2 + 22 + ..... + 2n −1.1 = 2n − 1

(

)

Jadi T (n ) = 2 n − 1

( )

T (n ) ∈ O 2 n

T (n ) = 2n − 1 adalah jumlah seluruh perpindahan piringan dari satu tiang ke tiang lainnya. Jika perpindahan 1 piringan butuh waktu 1 detik, maka waktu yang dibutuhkan : 264 − 1 detik

= 10.446.744.073.709.551.615 = kira-kira 600 milyar tahun (???!!!) 3. Persoalan Minimum & Maksimum procedure MinMaks2(input A : TabelInt, i, j : integer, output min, maks : integer) { Mencari nilai maksimum dan minimum di dalam tabel A yang berukuran n elemen secara Divide and Conquer. Masukan: tabel A yang sudah terdefinisi elemen-elemennya Keluaran: nilai maksimum dan nilai minimum tabel } Deklarasi min1, min2, maks1, maks2 : integer Algoritma: if i=j then min←Ai

{ 1 elemen }


maks←Ai else if (i = j-1) then { 2 elemen } if Ai < Aj then maks←Aj min←Ai else maks←Ai min←Aj endif else { lebih dari 2 elemen } k←(i+j) div 2 { bagidua tabel pada posisi k } MinMaks2(A, i, k, min1, maks1) MinMaks2(A, k+1, j, min2, maks2) if min1 < min2 then min←min1 else min←min2 endif if maks1<maks2 then maks←maks2 else maks←maks2 endif

Relasi rekurrens:

0 ,n =1 ⎧ ⎪ T (n ) = ⎨ 1 ,n = 2 ⎪2T ( n / 2) + 2 , n > 2 ⎩ Penyelesaian: Asumsi: n = 2k, dengan k bilangan bulat positif, maka T(n) = 2T(n/2) + 2 = 2(2T(n/4) + 2) + 2 = 4T(n/4) + 4 + 2 = 4T(2T(n/8) + 2) + 4 + 2 = 8T(n/8) + 8 + 4 + 2 = ...


k–1

=2

k −1

T(2) +

∑2

i

i =1

= 2k – 1 ⋅ 1 + 2k – 2 2 2 = 2( log n )−1 + 2( log n ) − 2 = n/2 + n – 2 = 3n/2 – 2 Jadi T (n ) = 3n − 2 2 T (n ) ∈ O(n ) Untuk mengetahui kompleksitas bentuk rekursif, maka T (n ) harus diubah dalam bentuk yang bukan rekursif Bagaimana mengubah bentuk rekursif ke non rekursif ? Ada dua macam cara untuk menyelesaikan masalah ini, yaitu cara coba-coba dan dengan persamaan karakteristik : 1. Cara coba-coba. Cara ini dilakukan dengan menentukan pola deret yang terbentuk (cara induksi). Contoh untuk cara ini telah ditunjukkan dalam mencari kompleksitas waktu untuk beberapa bentuk rekursif sebelumnya. Cara ini agak sulit dan perlu pengalaman.

Contoh : a n = 1,2 ⎧ T (n ) = ⎨ ⎩T (n − 1) + T (n − 2 ) + b n ≥ 3 T(1) = T(2) = a T (3) = T (1) + T (2 ) + b = a + a + b = 2a + b T (4 ) = T (2 ) + T (3) + b = a + 2a + b + b = 3a + 2b T (5) = T (3) + T (4 ) + b = 2a + b + 3a + 2b + b = 5a + 4b T (6 ) = T (4 ) + T (5) + b = 3a + 2b + 5a + 4b + b = 8a + 7b

→ Sulit untuk diformulasikan 2. Metode dengan persamaan karakteristik Bentuk Persamaan Linier Tak Homogen

Langkah-langkahnya adalah sebagai berikut : 1. Perhatikan bentuk rekursifnya : T (n ) = a1T (n − 1) + a2T (n − 2) + .... + akT (n − k ) + f (n ) Desain & Analisis Algoritma – ZK Abdurahman Baizal

f (n ) = t n Pd (n ) → polinomial dengan orde / derajat terbesar d

Pd (n ) = b0 n d + b1 n d −1 + .... + bk 2. Asumsi f (n ) = 0 → bentuk homogen T (n ) = a1T (n − 1) + a 2T (n − 2 ) + .... + a k T (n − k ) Misal T (n ) = x n x n = a1 x n −1 + a 2 x n − 2 + ... + a k x n −k

x n − a1 x n −1 − a 2 x n − 2 − ... − a k x n − k = 0 Persamaan di atas kemudian dibagi dengan x n − k (ini jika x n − k adalah suku dengan orde terkecil), sehingga didapatkan : x k − a1 x k −1 − a 2 x k − 2 − ... − a k = 0 3. Diperoleh persamaan karakteristik : (x k − a1 x k −1 − a2 x k −2 − ... − ak )(x − t )d +1 = 0 t didapatkan dari langkah 1. 4. Ada 2 macam kasus : Kasus 1 Semua akar karakteristik berbeda {x1 , x 2 , x3 ,...} Solusi Umum: n n n T (n ) = c1 x1 + c 2 x 2 + c3 x3 + .... c1 , c 2 , c3 ,... adalah konstanta yang harus dicari Kasus 2 Semua akar karakteristik sama, yaitu x1 = x2 = .... = x Solusi Umum: T (n ) = c1 + c 2 n + c3 n 2 + c 4 n 3 + ... .x n

(

)

Contoh 1: Kasus faktorial 0 ,n=0 ⎧ T (n ) = ⎨ ⎩T (n − 1) + 1 , n > 0

(i) T (n ) = T (n − 1) + 1 f (n ) = 1 = 1n (n 0 ) →t=1 d=0 (ii) persamaan homogen T (n ) = T (n − 1) T (n ) − T (n − 1) = 0


Misal T (n ) = x n , maka x n − x n −1 = 0 Persamaan terakhir ini dibagi dengan x n −1 (suku dengan orde terkecil), didapatkan :

⇔x–1=0 (iii) Persamaan karakteristik (x – 1)(x – 1) = 0 Akar – akarnya adalah : x1 = 1 x 2 = 1 Akar sama, jadi termasuk kasus 2, sehingga solusi umum :

T (n ) = (c1 + c 2 n ).1n = c1 + c 2 n Dari relasi rekurens : T (0 ) = 0 T (1) = T (0 ) + 1 = 1 ………..(*) Dari solusi umum: T (0 ) = c1 T (1) = c1 + c2 ………(**) Dari (*) dan (**) didapatkan persamaan : c1 = 0 c1 + c 2 = 1 Dari kedua persamaan terakhir ini diperoleh c1 = 0 dan c 2 = 1 Dengan demikian diperoleh : T (n ) = c1 + c 2 n =n Jadi kompleksitas waktunya adalah T (n ) = n dan T (n ) ∈ O(n ) Contoh 2: Kasus Menara Hanoi

Relasi rekurrens : 1 , n =1 ⎧ T (n ) = ⎨ ⎩1 + 2T (n − 1) , n > 1 (i) T (n ) = 2T (n − 1) + 1 f (n ) = 1


= 1n (1.n 0 ) →t=1 d=0 (ii) Persamaan homogen Misal T (n ) = x n T (n ) = 2T (n − 1) ⇔ T (n ) − 2T (n − 1) = 0

x n − 2 x n −1 = 0 Persamaan terakhir ini dibagi x n −1 (suku dengan orde terkecil), didapatkan :

x–2=0 (iii) Diperoleh persamaan karakteristik : (x – 2)(x – 1) = 0 Dari persamaan karakterik diperoleh akar-akar : x1 = 2 x 2 = 1 → akar-akar berbeda, sehingga termasuk dalam kasus 1, sehingga solusi umum: T (n ) = c1 2 n + c 2 1n = c1 2 n + c 2 Cari c1 dan c2 : Dari relasi rekurrens : T (1) = 1 ………(*) T (2) = 3 Dari Solusi umum: T (1) = 2c1 + c2 ……(**) T (2 ) = 4c1 + c2 Dari (*) dan (**) 2c1 + c2 = 1 4c1 + c2 = 3 Dari 2 persamaan terakhir ini, diperoleh c1 = 1 dan c2 = -1 Jadi T (n ) = c1 2 n + c 2 = 2n − 1 Jadi kompleksitas waktu :


T (n ) = 2 n − 1 Kompleksitas waktu Asimptotik: T (n ) ∈ O 2n

( )

Contoh 3: Kasus Minmax2 , n =1 ⎧0 ⎪ ,n=2 T (n ) = ⎨1 ⎪2T (n ) + 2 , n > 2 2 ⎩

(i) T (n ) = 2T (n 2 ) + 2 Dimisalkan n = 2 m ⎛ 2m ⎞ ⎟⎟ + 2 T (2 m ) = 2T ⎜⎜ ⎝ 2 ⎠

(

)

= 2T 2 m −1 + 2 (ii) Persamaan homogen : Misal T 2 m = x m

( )

( ) ( )

( ) ( )

T 2 m = 2T 2 m −1 T 2 m − 2T 2 m −1 = 0 x m − 2 x m −1 = 0 Persamaan terakhir ini dibagi dengan x m −1 (suku dengan orde terkecil), didapatkan : x–2=0 f (n ) = 2

( )

= 1n 2n 0 →t=1 d=0

(iii) Diperoleh persamaan karakteristik : (x − 2)(x − 1) = 0 Akar-akarnya : x1 = 2 x 2 = 1 Solusi : T (m ) = c1 2 m + c 2 1m Karena n = 2 m → m= 2 log n T (n ) = c1 2 log n + c 2 1 = c1 n + c 2 2

2

log n


Cari c1 dan c2 : Dari relasi rekurrens : T (4 ) = 2T (2 ) + 2 =4 T (8) = 2T (4 ) + 2 ……..(*) = 10 Dari solusi umum: T (4) = 4c1 + c 2 ………..(**) T (8) = 8c1 + c 2 Dari (*) dan (**) 4c1 + c 2 = 4 8c1 + c 2 = 10 Dari dua persamaan ini diperoleh c1 =

3

2

dan c 2 = −2

Jadi kompleksitas waktu : 3n T (n ) = −2 2

Kompleksitas waktu asimptotik : T (n ) ∈ O(n ) Bentuk Persamaan Linier Homogen

Bentuk Persaman Linier Homogen adalah : T (n ) = a1T (n − 1) + a2T (n − 2) + .... + akT (n − k ) + f (n ) Dengan f (n ) = 0 Jadi bentuk Persaman Linier Homogen adalah : T (n ) = a1T (n − 1) + a2T (n − 2) + .... + akT (n − k ) Contoh 4: Deret Fibonacci

Relasi rekurrens : n=0 ⎧0 ⎪ T (n ) = ⎨1 n =1 ⎪T (n − 1) + T (n − 2 ) n > 1 ⎩ (i) Persamaan rekursi : T (n ) − T (n − 1) − T (n − 2 ) =0 Misal T (n ) = x n , maka


x n − x n −1 − x n − 2 = 0 Persamaan terakhir ini dibagi x n − 2 , didapatkan : x 2 − x − 1 = 0 → persamaan karakteristik (ii) Akar persamaan karakteristik adalah : x1 =

1+ 5 2

x1 =

dan

1− 5 2

→ akar-akar berbeda, sehingga termasuk dalam kasus 1, sehingga solusi umum: n

⎛1− 5 ⎞ ⎛1+ 5 ⎞ ⎟ ⎟ + c2 ⎜ T (n ) = c1 ⎜⎜ ⎜ 2 ⎟ ⎟ 2 ⎠ ⎝ ⎠ ⎝

n

(iii) Cari c1 dan c2 : Dari relasi rekurrens dan solusi umum diperoleh : 0

0

⎛1+ 5 ⎞ ⎛1− 5 ⎞ ⎟ + c2 ⎜ ⎟ T (0) = c1 ⎜⎜ ⎟ ⎜ 2 ⎟ =0 2 ⎝ ⎠ ⎝ ⎠ 1

1

⎛1+ 5 ⎞ ⎛1− 5 ⎞ ⎟ + c2 ⎜ ⎟ T (1) = c1 ⎜⎜ ⎟ ⎜ 2 ⎟ =1 2 ⎝ ⎠ ⎝ ⎠ 1 −1 dan c2 = 5 5 (iv) Masukkan ke solusi umum kembali, sehingga didapatkan : Dari 2 persamaan terakhir ini, diperoleh c1 =

(

)

n

(

)

⎡ 1+ 5 ⎤ ⎡ 1− 5 ⎤ ⎢ ⎥ −⎢ ⎥ 2 ⎦ ⎣ 2 ⎦ ⎣ T (n ) = 5

n


Contoh 5: Misal kita punya relasi rekurrens : 0 ⎧ ⎪ 1 ⎪ T (n ) = ⎨ 2 ⎪ ⎪⎩7T (n − 1) − 15T (n − 2 ) + 9T (n − 3)

n=0 n =1 n=2 n>2

(i) Persamaan rekursi : T (n ) − 7T (n − 1) + 15T (n − 2 ) − 9T (n − 3) = 0 Misal T(n) = xn, maka persamaan di atas menjadi : x n − 7 x n −1 + 15 x n − 2 − 9 x n − 3 = 0 x 3 − 7 x 2 + 15 x − 9 = 0 Persamaan terakhir ini dibagi x n − 3 (suku dengan orde terkecil), didapatkan : x 3 − 7 x 2 + 15 x − 9 = ( x − 1)( x − 3)(x − 3) = 0 → persamaan karakteristik (ii) Akar persamaan karakteristik adalah : x1 = 1 , x2 = x3 = 3

→ tidak semua akar-akarnya sama (juga tidak semua berbeda), jadi perpaduan antara kasus 1 dan kasus 2, sehingga solusi umumnya adalah : T (n ) = c11n + c2 3n + c3n3n (iii) Cari c1 dan c2 : Dari relasi rekurrens dan solusi umum diperoleh : T (0) = c110 + c2 30 + c3 (0)(30 ) = 0 T (1) = c111 + c2 31 + c3 (0)(31 ) = 1

T (0) = c112 + c2 32 + c3 (0)(32 ) = 2 Disederhanakan menjadi : c1 + c2 = 0 c1 + 3c2 + 3c3 = 1 c1 + 9c2 + 18c3 = 2 Dari ketiga persamaan ini didapatkan c1 = −1 , c2 = 1, dan c3 = − 13


(iv) Masukkan ke solusi umum kembali, sehingga didapatkan :

( )

( )

( )

⎛ 1⎞ T (n ) = (− 1) 1n + (1) 3n + ⎜ − ⎟ n3n ⎝ 3⎠ n n −1 = −1 + 3 − n3

Cara yang telah dibahas didepan adalah bagaimana mencari T(n) untuk algoritma rekursif, yang berlaku secara umum. Khusus untuk strategi Divide & Conquer, kita bisa juga mencari kompleksitas waktu asimptotik (ingat! hanya kompleksitas waktu asimptotik, bukan T(n) ) dengan menggunakan teorema Master. Teorema Master : Untuk suatu general Divide and Conquer recurrence :

( b )+ f (n)

T (n ) = aT n

( )

Jika f (n ) ∈ O n d dimana d ≥ 0 dalam persamaan general Divide and Conquer recurrence di atas, maka

( ) (

⎧O n d ⎪ T (n ) ∈ ⎨O n d log n ⎪O n b log a ⎩

(

)

)

a < bd a = bd a > bd

(analogous results hold for the Θ and Ω notations, too) Contoh : Persoalan Minimum & Maksimum (procedure MinMax2) → salah satu contoh strategi divide and conquer. , n =1 ⎧0 ⎪ ,n=2 T (n ) = ⎨1 ⎪2T (n ) + 2 , n > 2 2 ⎩

Dari relasi rekurens di atas, diperoleh a = 2, b = 2, d = 0. sehingga a > b d , sehingga 2 T (n ) ∈ O n log 2 atau T (n ) ∈ O(n ) .

(

)

Contoh yang lain disampaikan di kuliah, ya!!!

ooooOOO Selamat Menikmati OOOoooo


Kompleksitas Waktu untuk Algoritma Rekursif

Recommend Documents