Design and Analysis of Algorithms CNH2G3- Week 5 Kompleksitas waktu algoritma rekursif part 2: Metode Karakteristik Dr. Putu Harry Gunawan (PHN)
Review 1. Tentukan kompleksitas waktu Big-Oh untuk relasi rekursi berikut: ( 1, n=1 T (n) = T (n − 1) + 1, n≥2 2. Tentukan kompleksitas waktu Big-Oh untuk relasi rekursi berikut: ( 2, n=0 T (n) = T (n − 1) + T (n − 2), n≥1
1
(0.1)
(0.2)
Metode Karakteristik:Solusi Umum
Relasi rekursi dibedakan menjadi dua, yakni relasi rekursi non homogen dan homogen. Penyelesaian menggunakan metode karakteristik, dibedakan berdasarkan tipe dari relasi rekursi. Berikut adalah diberikan tahapan penyelesaian secara umum bentuk relasi rekursif: 1. Diberikan bentuk rekursif: T (n) = α1 T (n − 1) + α2 T (n − 2) + · · · + αk T (n − k) + f (n)
(1.1)
f (n) = tn Pd (n)
(1.2)
Pd (n) = b0 nd + b1 nd−1 + · · · + bk
(1.3)
dengan:
2. Langkah pertama dalam menyelesaikan relasi rekursi menggunakan metode karakteristik adalah mengasumsikan bahwa relasi rekursi dalam tipe homogen yakni f (n) = 0, sehingga relasinya: T (n) = α1 T (n − 1) + α2 T (n − 2) + · · · + αk T (n − k).
(1.4)
Selanjutnya dengan memisalkan T (n) = xn , sehingga didapat: xn = α1 xn−1 + α2 xn−2 + · · · + αk xn−k , n
x − α1 x
n−1
− α2 x
n−2
1
− · · · − αk x
n−k
= 0.
(1.5) (1.6)
Kemudian, jika xn−k merupakan suku dengan orde terkecil, maka Persamaan (1.6) dibagi dengan xn−k menjadi xk − α1 xk−1 − α2 xk−2 − · · · − αk = 0 3. Sehingga diperoleh persamaan karakteristik: xk − α1 xk−1 − α2 xk−2 − · · · − αk (x − t)d+1 = 0
(1.7)
(1.8)
dengan t dan d didapatkna dari langkah 1 (INGAT suku (x − t)d+1 hanya berlaku untuk kasus relasi rekursi NON HOMOGEN, JIka HOMOGEN maka bernilai 1). 4. Cari solusi dari Persamaan (1.8). Secara umum, solusi dari persamaan karakteristik ada dua macam kasus: (a) Kasus solusi berbeda: Jika semua akar persamaan karakteristik berbeda {x1 , x2 , x3 , · · · }, maka solusi umumnya adalah: T (n) = c1 xn1 + c2 xn2 + c3 xn3 + · · · (1.9) dengan c1 , c2 , c3 , · · · merupakan konstanta yang harus dicari. (b) Kasus solusi sama: Jika semua akar persamaan karakteristik sama {x1 = x2 = x3 = · · · = x}, maka solusi umumnya adalah: T (n) = (c1 + c2 n + c3 n2 + · · · )xn
(1.10)
dengan c1 , c2 , c3 , · · · merupakan konstanta yang harus dicari. Berikut Algoritma untuk menggunakan Metode Karakteristik: 1. Start. 2. Tentukan bentuk persamaan rekursif. 3. Selesaikan bentuk rekursif dalam bentuk HOMOGEN dan misalkan T (n) = xm , kemudian bagi dengan suku orde terkecil. 4. Bentuk persamaan Karakteristik. 5. Bentuk solusi umum berdasarkan akar-akar persamaan Karakteristik. 6. Temukan koefisien-koefisien dari solusi umum. 7. End.
2
2
Menyelesaikan relasi rekursi HOMOGEN
Berikut akan diberikan contoh-contoh untuk menyelesaikan relasi rekursi bentuk Homogen: 1. Diberikan relasi berikut n=0 0, T (n) = 1, n=1 3T (n − 1) − 2T (n − 2),
(2.1) n≥2
Langkah-langkah penyelesainnya adalah (a) Persamaan rekursi bentuk homogen f (n) = 0: T (n) − 3T (n − 1) + 2T (n − 2) = 0
(2.2)
Misalkan T (n) = xn , maka didapat xn − 3xn−1 + 2xn−2 = 0,
(2.3)
selanjutnya dengan membagi persamaan dengan suku orde terkecil xn−2 didapat persamaan karakteristik: x2 − 3x + 2 = 0 (2.4) (b) Akar akar dari persamaan datas adalah: (x − 2)(x − 1) = 0
(2.5)
dengan x1 = 1 dan x2 = 2, karena akar-akarnya berbeda maka solusi umumnya adalah: T (n) = c1 xn1 + c2 xn2 n
= c1 1 + c2 2
(2.6)
n
(2.7)
(c) Selanjutnya cari koefisien c1 dan c2 didapat: T (0) = c1 10 + c2 20 = 0 T (1) = c1 11 + c2 21 = 1 Dari persamaan di atas didapat hasil akhir adalah c1 = −1 dan c2 = 1, sehingga solusi umumnya didapat: T (n) = − (1n ) + (2n ) = 2n − 1 ∈ O(2n ).
(2.8)
2. Exercise: diberikan relasi rekursi dari masalah Barisan Fibonacci berikut n=0 0, T (n) = 1, n=1 T (n − 1) + T (n − 2), n≥2 3. Exercise: diberikan relasi rekursi berikut 0, n=0 1, n=1 T (n) = 2, n=2 7T (n − 1) − 15T (n − 2) + 9T (n − 3), 3
(2.9)
(2.10) n≥3
3
Menyelesaikan relasi rekursi NON-HOMOGEN
Berikut akan diberikan contoh-contoh untuk menyelesaikan relasi rekursi bentuk NonHomogen: 1. Diberikan relasi rekursi untuk masalah faktorial ( 0, T (n) = T (n − 1) + 1,
n=0 n>1
(3.1)
Langkah-langkah penyelesainnya adalah: (a) Relasi rekursinya adalah: T (n) = T (n − 1) + 1
(3.2)
dengan: f (n) = 1 = 1n (1 · n0 ) sehingga didapatkan t = 1 dan d = 0. (b) Asumsikan dahulu persamaan dalam bentuk HOMGEN yakni f (n) = 0 sehingga didapat: T (n) = T (n − 1) T (n) − T (n − 1) = 0 Misalkan T (n) = xn , maka didapatkan xn − xn−1 = 0,
(3.3)
selanjutnya dengan membagi persamaan dengan suku orde terkecil xn−1 didapat persamaan karakteristik: (x − 1) (x − t)d+1 = 0 (x − 1) (x − 1) = 0 (c) Sehingga didapatkan akar-akar kembar yakni x1 = x2 = 1 sehingga solusi umumnya adalah T (n) = (c1 + c2 n)1n = c1 + c2 n (d) Selanjutnya cari koefisien c1 dan c2 didapat: T (0) = c1 = 0 T (1) = c1 + c2 = 1 Dari persamaan di atas didapat hasil akhir adalah c1 = 0 dan c2 = 1, sehingga solusi umumnya didapat: T (n) = n ∈ O(n). 4
(3.4)
2. Diberikan relasi rekursi untuk masalah Menara Hanoi ( 1, n=1 T (n) = 2T (n − 1) + 1, n>1
(3.5)
Langkah-langkah penyelesainnya adalah: (a) Relasi rekursinya adalah: T (n) = 2T (n − 1) + 1
(3.6)
dengan: f (n) = 1 = 1n (1 · n0 ) sehingga didapatkan t = 1 dan d = 0. (b) Asumsikan dahulu persamaan dalam bentuk HOMGEN yakni f (n) = 0 sehingga didapat: T (n) = 2T (n − 1) T (n) − 2T (n − 1) = 0 Misalkan T (n) = xn , maka didapatkan xn − 2xn−1 = 0,
(3.7)
selanjutnya dengan membagi persamaan dengan suku orde terkecil xn−1 didapat persamaan karakteristik: (x − 2) (x − t)d+1 = 0 (x − 2) (x − 1) = 0 (c) Sehingga didapatkan akar-akar berbeda yakni x1 = 2 dan x2 = 1 sehingga solusi umumnya adalah T (n) = c1 2n + c2 1n = c1 2n + c2 (d) Selanjutnya cari koefisien c1 dan c2 didapat: T (1) = 2c1 + c2 = 1 T (2) = 4c1 + c2 = 3 Dari persamaan di atas didapat hasil akhir adalah c1 = 1 dan c2 = −1, sehingga solusi umumnya didapat: T (n) = 2n − 1 ∈ O(2n ). 3. Diberikan relasi rekursi untuk masalah Minimum dan Maksimum n=1 0, T (n) = 1, n=2 n 2T 2 + 2, n>2 Langkah-langkah penyelesainnya adalah: 5
(3.8)
(3.9)
(a) Relasi rekursinya adalah: T (n) = 2T
n 2
+2
(3.10)
dengan memisalkan n = 2m , maka relasi rekursinya adalah m 2 m +1 T (2 ) = 2T 2 = 2T 2m−1 + 1 dan f (m) = 2 = 1m (2 · m0 ) sehingga didapatkan t = 1 dan d = 0. (b) Asumsikan dahulu persamaan dalam bentuk HOMGEN yakni f (m) = 0 sehingga didapat: T (2m ) = 2T 2m−1 T (2m ) − 2T 2m−1 = 0 Misalkan T (m) = xm , maka didapatkan xm − 2xm−1 = 0,
(3.11)
selanjutnya dengan membagi persamaan dengan suku orde terkecil xm−1 didapat persamaan karakteristik: (x − 2) (x − t)d+1 = 0 (x − 2) (x − 1) = 0 (c) Sehingga didapatkan akar-akar berbeda yakni x1 = 2 dan x2 = 1 sehingga solusi umumnya adalah T (n) = c1 2m + c2 1m Karena n = 2m , maka m =2 log n, 2
T (n) = c1 2
log n
+ c2 1
2
log n
= c1 n + c2 (d) Selanjutnya cari koefisien c1 dan c2 didapat: T (1) = c1 + c2 = 0 T (2) = 2c1 + c2 = 1 Dari persamaan di atas didapat hasil akhir adalah c1 = 1 dan c2 = −1, sehingga solusi umumnya didapat: T (n) = 2n − 1 ∈ O(n). 6
(3.12)
Atau dengan cara lain: T (4) = 4c1 + c2 = 2T (2) + 2 = 4 T (8) = 8c1 + c2 = 2T (4) + 2 = 10 Dari persamaan di atas didapat hasil akhir adalah c1 = 3/2 dan c2 = −2, sehingga solusi umumnya didapat: 3 T (n) = n − 2 ∈ O(n). 2
4
(3.13)
Teorema Master
Pembahasan menggunakan metode karakteristik untuk algoritma rekursif pada bab sebelumnya hanya berlaku untuk kasus umum. Kasus khusus yakni untuk strategi Divide & Conquer, Kompleksitas waktu asimtotik dapat dicari menggunakan teorema Master Theorem 4.1 (Master) Untuk suatu general Divide and Conquer recurrence: n T (n) = aT + f (n) (4.1) b Jika f (n) ∈ O(nd ) dengan d ≥ 0, dalam persamaan general Divide and Conquer recurrence di atas, maka d a < bd O(n ) T (n) ∈ (4.2) O(nd log n) a = bd b log a d O(n ) a>b
Exercise Gunakan Teorema Master untuk mencari kompleksitas waktu asimtotik pada relasi rekursi untuk masalah Minimum dan Maksimum di bawah ini: n=1 0, T (n) = (4.3) 1, n=2 n 2T 2 + 2, n>2
References 1. Anany, L. (2003). Introduction to the design and analysis of algorithms. Villanova University. 2. http://www.annedawson.net/BigOh.htm
7
5
Homework 1. Selesaikan relasi rekurensi berikut dengan menggunakan Metode Karakteristik serta tambahkan pula dengan Teorema master untuk soal (d-e): (a) ( T (n) =
0, T (n − 1) + 5,
n=1 n≥2
(5.1)
n=1 n≥2
(5.2)
(b) ( T (n) =
4, 3T (n − 1),
(c) ( T (n) =
0, n=0 T (n − 1) + T (n − 2) + T (n − 3),
n>0
(5.3)
(d) ( T (n) =
1, T (n/2) + n,
n=1 n>1
(5.4)
1, T (n/3) + 1,
n=1 n>1
(5.5)
(e) ( T (n) =
2. Diberikan algoritma untuk menghitung jumlah pangkat 3 dari deret, S(n) = n3 + (n − 1)3 + · · · + 23 + 13 . ALGORITHM S(n) //Input: A positive integer n //Output: The sum of the first n cubes if n = 1 return 1 else return S(n - 1) + n * n * n
(a) Tentukan relasi rekursi dari algoritma di atas dan selesaikan menggunakan metode Karakteristik.
8
