Analisa Algoritma

Divide and ConquerDivide and Conquer

Prinsip DasarPrinsip Dasar

Membagi n input menjadi k sub set Membagi n input menjadi k sub set input yang berbeda (1< k < n)input yang berbeda (1< k < n)

Dari k sub set input yang berbeda Dari k sub set input yang berbeda akan terdapat k subproblemakan terdapat k subproblem

Setiap subproblem mempunyai solusi Setiap subproblem mempunyai solusi masing-masing (k sub solusi)masing-masing (k sub solusi)

Dari k sub solusi akan diperoleh Dari k sub solusi akan diperoleh solusi yang optimal yang diharapkansolusi yang optimal yang diharapkan

Jika subproblem masih dianggap besar Jika subproblem masih dianggap besar maka dapat dipecah lagi menjadi sub sub maka dapat dipecah lagi menjadi sub sub problem yang lebih kecil lagiproblem yang lebih kecil lagi

Metoda DANDC dapat digunakan lagi Metoda DANDC dapat digunakan lagi secara rekursifsecara rekursif

Pemecahan n input menjadi k input Pemecahan n input menjadi k input sehingga menimbulkan k sub problem dpt sehingga menimbulkan k sub problem dpt dilakukan apabila k subproblem tsb dilakukan apabila k subproblem tsb mempunyai sifat yang sama terhadap mempunyai sifat yang sama terhadap persoalan semulapersoalan semula

INPUT 3

subproblem

subsolusi

INPUT k

subproblem

subsolusi

INPUT 2

subproblem

subsolusi

INPUT 1

subproblem

subsolusi

Solusi optimal

N INPUT

Algoritma DANDCAlgoritma DANDC

Procedure DANDC(p,q)Procedure DANDC(p,q)Global n,A(1:N): integer m,p,qGlobal n,A(1:N): integer m,p,qIf small(p,q) then G(p,q)If small(p,q) then G(p,q)

else else m m DIVIDE(p,q) DIVIDE(p,q)COMBINE(DANDC(p,m),DANDC(m+1,q)COMBINE(DANDC(p,m),DANDC(m+1,q)

EndifEndifEnd DANDCEnd DANDC

Small(p,q) adalah fungsi bernilai boole yang Small(p,q) adalah fungsi bernilai boole yang menentukan apakah ukuran input (q-p+1) menentukan apakah ukuran input (q-p+1) cukup kecil sehingga tak perlu dipecah lagi, cukup kecil sehingga tak perlu dipecah lagi, jika demikian maka G(p,q) yang diproses, jika jika demikian maka G(p,q) yang diproses, jika tidak maka fungsi DIVIDE(p,q) yg diprosestidak maka fungsi DIVIDE(p,q) yg diproses

Fungsi DIVIDE(p,q) menghasilkan bilangan Fungsi DIVIDE(p,q) menghasilkan bilangan bulat yg menguraikan input menjadi dua bulat yg menguraikan input menjadi dua bagian. Misalnya input dari p sampai q, bagian. Misalnya input dari p sampai q, dipecah menjadi p:m dan m+1:qdipecah menjadi p:m dan m+1:q

Pecahan tadi menjadi dua subproblem dan Pecahan tadi menjadi dua subproblem dan menghasilkan dua subsolusi misalnya X dan Ymenghasilkan dua subsolusi misalnya X dan Y

Fungsi COMBINE(X,Y) merupakan fungsi Fungsi COMBINE(X,Y) merupakan fungsi penentu solusi umum atau yg diharapkan penentu solusi umum atau yg diharapkan dgn memanfatkan solusi X dan Y.dgn memanfatkan solusi X dan Y.

Algoritma DANDCAlgoritma DANDC Procedure maxmin(I,j,fmax,fmin)Procedure maxmin(I,j,fmax,fmin) Integer I,jInteger I,j Global n, A(1:n)Global n, A(1:n) CaseCase : i=j : fmax <- fmin <- A(i): i=j : fmax <- fmin <- A(i) : I = j-1 : if A(i) < A(j): I = j-1 : if A(i) < A(j) Then fmax <- A(j); fmin <- A(i)Then fmax <- A(j); fmin <- A(i) Else fmax <- A(i) ; fmin <- A(j)Else fmax <- A(i) ; fmin <- A(j) EndifEndif : ELSE mid <- | (i+j)/2 |: ELSE mid <- | (i+j)/2 | CALL maxmin (I,mid,gmax,gmin)CALL maxmin (I,mid,gmax,gmin) CALL maxmin(mid+1,j, hmax, hmin)CALL maxmin(mid+1,j, hmax, hmin) Fmax <- MAX(gmax, hmax)Fmax <- MAX(gmax, hmax) Fmin <- MIN (gmin, hmin)Fmin <- MIN (gmin, hmin) EndcaseEndcase End maxminEnd maxmin

11 22 33 44 55 66 77 88 99

2222 1313 -5-5 -8-8 1515 6060 1717 3131 4747

Carilah min dan max nya

Procedure straitmaxmin(A,n,max,min)Procedure straitmaxmin(A,n,max,min)MaxMax min min A(1) A(1)For i=2 to n doFor i=2 to n do

if A(i) > maxif A(i) > maxthen max then max A(i) A(i)

else if A(i) < min else if A(i) < min then min then min A(i) A(i)

endifendifendifendif

EndforEndforEnd straitmaxminEnd straitmaxmin

BEST CASE22 44 55 1010

Max=2 ; Min=2i=2 A(2) > max maka max = 4i=3 A(3) > max maka max = 5i=4 A(4) > max maka max = 10

Jadi diperoleh min=2 dan max =10

Operasi pembandingan yang dilakukan sebanyak 3 atau (n-1)

Worst caseWorst case1010 55 44 22

Max=10; min=10i=2; A(2) > max

A(2) < min , mk min=5i=3; A(3) > max

A(3) < min, mk min =4i=4; A(4) > max

A(4) < min, mk min =2

Jadi min=2 max=10

Operasi pembandingan yang dilakukan sebanyak 6 atau 2(n-1)

Average caseAverage case

Rata-rata dari best case dan worst Rata-rata dari best case dan worst casecase

[(n-1) + 2(n-1) ]/2 = 3/2 (n-1)[(n-1) + 2(n-1) ]/2 = 3/2 (n-1)

1,9

1,5 6,9

1,3 4,5 6,7 8,9

1,2 3,3

60,-8

22,-8 60,17

22,-5 15,8 60,17 47,31

22,13 -5,-5

T(n/2) + T(n/2)+2 ; utk n > 2T(n/2) + T(n/2)+2 ; utk n > 2

T(n) = 1T(n) = 1 ; utk n = 2 ; utk n = 2

00 ; utk n = 1 ; utk n = 1

MergesortMergesort

Terdapat barisan n input elemen yang Terdapat barisan n input elemen yang ditempatkan dalam sebuah array. ditempatkan dalam sebuah array.

Pisahkan n elemen tsb menjadi dua Pisahkan n elemen tsb menjadi dua bagian.bagian.

Jika masing-2 bagian masih terlalu Jika masing-2 bagian masih terlalu besar, dapat dibagi lagi. besar, dapat dibagi lagi.

Setiap bagian diurutkan, lalu Setiap bagian diurutkan, lalu digabungkan dengan bagian lain.digabungkan dengan bagian lain.

Algoritma mergesortAlgoritma mergesort

Terdiri dari dua prosedur yaitu Terdiri dari dua prosedur yaitu mergesort dan mergemergesort dan merge

Mergesort utk mengurutkanMergesort utk mengurutkan Merge utk menggabungkanMerge utk menggabungkan

Procedure mergesort(low,high)Procedure mergesort(low,high)

If low < high If low < high

then mid then mid [ (low+high) / 2] [ (low+high) / 2]

CALL mergesort(low,mid)CALL mergesort(low,mid)

CALL mergesort(mid+1, high)CALL mergesort(mid+1, high)

CALL merge(low, mid, high)CALL merge(low, mid, high)

EndifEndif

End mergesortEnd mergesort

Procedure merge(low,mid,high)Procedure merge(low,mid,high)

HHlow; I low; I low; j low; j mid+1mid+1

While h <= mid AND j <= high doWhile h <= mid AND j <= high do

if A(h)<= A(j) if A(h)<= A(j)

then B(i) then B(i) A(h) A(h)h h h+1 h+1

else B(i) else B(i) A(j) A(j)

j j j + 1 j + 1

endifendif

I < I +1I < I +1

RepeatRepeat

If h > mid thenIf h > mid thenfor k for k j to high doj to high do

B(i) B(i) A(k) A(k)I I I +1 I +1

repeatrepeatelse for k else for k h to mid do h to mid do

B(i) B(i) A(k)A(k) I I I +1 I +1repeatrepeat

EndifEndifFor k For k low to high do low to high do

A(k) A(k) B(k) B(k)RepeatRepeatEnd mergeEnd merge