· Prinsip dasar dari metoda ini adalah membagi n input menjadi k subset input yang berbeda (1<k≤n). Dari k subset input yang bebeda akan terdapat k subproblem . Setiap subproblem mempunyai solusi masing-masing, sehingga akan diperoleh solusi yang optimal.
· Metoda DandC menggunakan teknik rekursif.
· DandC digunakan untuk menyelesaikan persoalan searching dan sorting.
 |
Algoritma DandC secara umum :
procedure DandC(p,q)
global n, A(1:N); integer m,p,q
if SMALL(p,q) then G(p,q)
else
m←DIVIDE (p,q)
COMBINE(DandC(p,m), DandC(m+1,q))
endif
end DandC
Keterangan :
· Small(p,q) adalah fungsi bernilai boole yang menentukan apakah input q-p+1 berukuran cukup kecil sedemikian sehingga solusinya dapat dihitung tanpa pemecahan. Jika demikian halnya maka fungsi G(p,q) yang akan diproses atau dieksekusi. Pada keadaan lain, fungsi divide (p,q) yang diproses.
· Fungsi divide(p,q) menghasilkan bilangan bulat yang menguraikan input menjadi dua bagian. Misal m= divide(p,q) maka input dipecah menjadi A(p:m) dan A(m+1:q).
· Fungsi combine merupakan fungsi yang menentukan solusi umum atau solusi yang diharapkan dari persoalan semula A(p:q)
SEARCHINGØ Menentukan bilangan maksimum dan minimum dengan menggunakan teknik iteratif.
Algoritma :
procedure straitmaxmin(A,n,max,min)
integer i,n
max←min←A(1)
for i←2 to n do
if A(i) > max
then max←A(i)
else
if A(i)<min
then min←A(i)
endif
repeat
endstaritmaxmin
1. Keadaan Terbaik (Best Case)
Keadaan ini akan tercapai jika elemen-elemen pada array disusun secara menaik (increasing).
Contoh: array A berisi 4 bilangan yang disusun secara menaik
| 2 | 4 | 5 | 10 |
A =
Jika dijalankan dengan algortima straitmaxmin maka akan diperoleh:
max←min←A(1)=2
i=2
A(2) > max ?
4 > 2 ? ya → max = 4 ……………1 operasi perbandingan
i=3
A(3) > max ?
5 > 4 ? ya → max = 5 ……………1 operasi perbandingan
i=4
A(4) > max ?
10 > 5 ? ya → max = 10 ……….1 operasi perbandingan
Sehingga akan diperoleh min=2, max=10
Penyelesaian tersebut diperoleh dengan membutuhkan 3 operasi perbandingan atau secara umum (n-1)satuan opersai, n banyaknya elemen dalam array.
2. Keadaan Terburuk (Worst Case)
Keadaan ini akan tercapai jika elemen-elemen pada array disusun secara menurun (decreasing).
| 80 | 21 | 6 | -10 |
A =
Jika dijalankan dengan algortima straitmaxmin maka akan diperoleh:
max←min←A(1)=80
i=2
A(2) > max ?
21 > 80 ? tidak
A(2) < max ?
21 < 80 ? ya → min = 21 ……………2 operasi perbandingan
i=3
A(3) > max ?
6 > 80 ? tidak
A(3) < max ?
6 < 80 ? ya → min = 6 ……………2 operasi perbandingan
i=4
A(4) > max ?
-10 > 80 ? tidak
A(4) < max ?
21-10 < 80 ? ya → min = -10 …………2 operasi perbandingan
Sehingga akan diperoleh min = -10, max = 80
Penyelesaian tersebut diperoleh dengan membutuhkan 6 operasi perbandingan atau secara umum 2(n-1)satuan opersai, n banyaknya elemen dalam array.
3. Keadaan Rata-rata (Average Case)
Keadaan ini akan tercapai jika elemen-elemen pada array disusun secara acak. Akan diperoleh waktu sebesar (3n/2-1) satuan operasi.
Ø Menentukan bilangan maksimum dan minimum dengan menggunakakan metoda DandC (teknik rekursif)
Algortima :
procedure maxmin(I,j,fmax,fmin)
integer i,j
global n,A(1:n)
case
: i=j ; fmax←fmin←A(i)
: i=j-1 ; if A(i) < A(j) then fmax←A(j); fmin←A(i)
else fmax←A(i); fmin←A(j)
endif
: else mid←½(i+j)/2½
call maxmin(i,mid,gmax,gmin)
call maxmin(mid+1,j,hmax,hmin)
fmax←max(gmax,hmax)
fmin←min(gmin,hmin)
endcase
endmaxmin
Contoh : dalam suatu array terdapat 9 bilangan yaitu
| 22 | 13 | -5 | -8 | 15 | 60 | 17 | 31 | 47 |
A =
Penyelesaian disimulasikan dalam bentuk pohon (tree).
Nilai i=1, j=n=9
 |
|
|
|
|
 | |||
 |
 |  |  | |||
|
|
|
|
 |
Bilangan maksimum = 60
Bilangan minimum = -8
Analisis algoritma :
T(½n/2½) + T(T(½n/2½) + 2 ; untuk n>2 T(n) = 1 ; untuk n= 2
0 ; untuk n =1
Tidak ada komentar:
Posting Komentar