algoritma dan logika

Metoda DIVIDE and CONQUER (DandC)
• Prinsip dasar dari metoda ini adalah membagi n input menjadi k subset input yang berbeda (1 max
then max←A(i)
else
if A(i) 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