Design and Analysis of Algorithm

Design and Analysis of Algorithm Week 5: Kompleksitas waktu algoritma rekursif part 2

Dr. Putu Harry Gunawan1 1 Department

of Computational Science School of Computing Telkom University

Dr. Putu Harry Gunawan (Telkom University)

Design and Analysis of Algorithm

1 / 34

Outline 1

Review

2

Metode Karakteristik:Solusi Umum Metode Karakteristik:Solusi Umum

3

Menyelesaikan relasi rekursi HOMOGEN Menyelesaikan relasi rekursi HOMOGEN

4

Menyelesaikan relasi rekursi NON-HOMOGEN Menyelesaikan relasi rekursi NON-HOMOGEN

5

Teorema Master Teorema Master

6

References References

7

Exercise Exercise



2 / 34

Exercise 1

Tentukan kompleksitas waktu Big-Oh untuk relasi rekursi berikut: ( 1, n=1 T (n) = T (n − 1) + 1, n≥2



(1.1)

3 / 34

Exercise 2

Tentukan kompleksitas waktu Big-Oh untuk relasi rekursi berikut: ( 2, n=0 T (n) = T (n − 1) + T (n − 2), n≥1



(1.2)

4 / 34

Outline 1

Review

2


3


4


5


6


7

Exercise Exercise



5 / 34

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:



6 / 34

Rekursif

Diberikan bentuk rekursif: T (n) = α1 T (n − 1) + α2 T (n − 2) + · · · + αk T (n − k) + f (n) (2.1) dengan: f (n) = t n Pd (n)

(2.2)

Pd (n) = b0 nd + b1 nd−1 + · · · + bk

(2.3)



7 / 34

Rekursif

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).

(2.4)

Selanjutnya dengan memisalkan T (n) = x n , sehingga didapat: x n = α1 x n−1 + α2 x n−2 + · · · + αk x n−k , n

x − α1 x


n−1

− α2 x

n−2

− · · · − αk x


n−k

= 0.

(2.5) (2.6)

8 / 34

Rekursif

Selanjutnya dengan memisalkan T (n) = x n , sehingga didapat: x n = α1 x n−1 + α2 x n−2 + · · · + αk x n−k ,

(2.7)

x n − α1 x n−1 − α2 x n−2 − · · · − αk x n−k = 0.

(2.8)

Kemudian, jika x n−k merupakan suku dengan orde terkecil, maka Persamaan (2.8) dibagi dengan x n−k menjadi x k − α1 x k−1 − α2 x k−2 − · · · − αk = 0



(2.9)

9 / 34

Rekursif

Sehingga diperoleh persamaan karakteristik: x k − α1 x k−1 − α2 x k−2 − · · · − αk (x − t)d+1 = 0

(2.10)

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).



10 / 34

Rekursif

Cari solusi dari Persamaan (2.10). Secara umum, solusi dari persamaan karakteristik ada dua macam kasus: Kasus solusi berbeda: Jika semua akar persamaan karakteristik berbeda {x1 , x2 , x3 , · · · }, maka solusi umumnya adalah: T (n) = c1 x1n + c2 x2n + c3 x3n + · · ·

(2.11)

dengan c1 , c2 , c3 , · · · merupakan konstanta yang harus dicari.



11 / 34

Rekursif

Kasus solusi sama: Jika semua akar persamaan karakteristik sama {x1 = x2 = x3 = · · · = x}, maka solusi umumnya adalah: T (n) = (c1 + c2 n + c3 n2 + · · · )x n

(2.12)

dengan c1 , c2 , c3 , · · · merupakan konstanta yang harus dicari.



12 / 34

Algoritma

Berikut Algoritma untuk menggunakan Metode Karakteristik: 1

Start.

2

Tentukan bentuk persamaan rekursif.

3

Selesaikan bentuk rekursif dalam bentuk HOMOGEN dan misalkan T (n) = x m , 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.



13 / 34

Outline 1

Review

2


3


4


5


6


7

Exercise Exercise



14 / 34

Homogen

Berikut akan diberikan contoh-contoh untuk menyelesaikan relasi rekursi bentuk Homogen: Diberikan relasi berikut   n=0  0, T (n) = (3.1) 1, n=1   3T (n − 1) − 2T (n − 2), n≥2



15 / 34

Homogen

Exercise: diberikan relasi rekursi dari masalah Barisan Fibonacci berikut   n=0  0, T (n) = (3.2) 1, n=1   T (n − 1) + T (n − 2), n≥2



16 / 34

Homogen

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.3) n≥3

17 / 34

Outline 1

Review

2


3


4


5


6


7

Exercise Exercise



18 / 34

Non-Homogen

Berikut akan diberikan contoh-contoh untuk menyelesaikan relasi rekursi bentuk Non-Homogen: Diberikan relasi rekursi untuk masalah faktorial ( 0, n=0 T (n) = (4.1) T (n − 1) + 1, n>1



19 / 34

Non-Homogen

Diberikan relasi rekursi untuk masalah Menara Hanoi ( 1, n=1 T (n) = 2T (n − 1) + 1, n>1



(4.2)

20 / 34

Non-Homogen

Diberikan relasi rekursi untuk masalah Minimum dan Maksimum   n=1  0, T (n) = 1, n=2   n n>2 2T 2 + 2,



(4.3)

21 / 34

Outline 1

Review

2


3


4


5


6


7

Exercise Exercise



22 / 34

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 (Master) Untuk suatu general Divide and Conquer recurrence: n T (n) = aT + f (n) b

(5.1)

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) ∈ (5.2) O(nd log n) a = bd  b log a  O(n ) a > bd Dr. Putu Harry Gunawan (Telkom University)


23 / 34

Teorema Master

Exercise Gunakan Teorema Master untuk mencari kompleksitas waktu asimtotik pada relasi rekursi untuk masalah Minimum dan Maksimum di bawah ini:   n=1  0, (5.3) T (n) = 1, n=2   n n>2 2T 2 + 2,



24 / 34

Outline 1

Review

2


3


4


5


6


7

Exercise Exercise



25 / 34

References

References 1

Anany, L. (2003). Introduction to the design and analysis of algorithms. Villanova University.



26 / 34

Outline 1

Review

2


3


4


5


6


7

Exercise Exercise



27 / 34

Exercise 1

Selesaikan relasi rekurensi berikut: ( 0, T (n) = T (n − 1) + 5,



n=1 n≥2

(7.1)

28 / 34

Exercise 2

Selesaikan relasi rekurensi berikut: ( 4, T (n) = 3T (n − 1),


n=1 n≥2


(7.2)

29 / 34

Exercise 3

Selesaikan relasi rekurensi berikut: ( 0, T (n) = T (n − 1) + n,



n=0 n>0

(7.3)

30 / 34

Exercise 4

Selesaikan relasi rekurensi berikut: ( 1, T (n) = T (n/2) + n,



n=1 n>1

(7.4)

31 / 34

Exercise 5

Selesaikan relasi rekurensi berikut: ( 1, T (n) = T (n/3) + 1,



n=1 n>1

(7.5)

32 / 34

Exercise 6

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

1

Tentukan relasi rekursi dari algoritma di atas dan selesaikan.

2

Bandingkan dengan algoritma yang tidak ditulis dengan rekursif.



33 / 34

The end of week 4

Thank you for your attention!



34 / 34

Design and Analysis of Algorithm

Recommend Documents