Algoritma Divide and Conquer

Algoritma Divide and Conquer merupakan algoritma yang sangat populer
di dunia Ilmu Komputer. Divide and Conquer merupakan algoritma yang
berprinsip memecah-mecah permasalahan yang terlalu besar menjadi beberapa
bagian kecil sehingga lebih mudah untuk diselesaikan.

Langkah-langkah umum algoritma Divide and Conquer :
Divide : Membagi masalah menjadi beberapa upa-masalah yang memiliki
kemiripan dengan masalah semula namun berukuran lebih kecil ( idealnya
berukuran hampir sama ).
Conquer : Memecahkan ( menyelesaikan ) masing-masing upa-masalah ( secara
rekursif ).
Combine : Menggabungkan solusi masing-masing upa-masalah sehingga
membentuk solusi masalah semula.

Objek masalah yang di bagi adalah masukan (input) atau instances yang
berukuran n: tabel (larik), matriks, dan sebagainya, bergantung pada masalahnya.
Tiap-tiap upa-masalah mempunyai karakteristik yang sama (the same type)
dengan karakteristik masalah asal, sehingga metode Divide and Conquer lebih
natural diungkapkan dalam skema rekursif.

Sesuai dengan karakteristik pembagian dan pemecahan masalah tersebut,
maka algoritma ini dapat berjalan baik pada persoalan yang bertipe rekursif
( perulangan dengan memanggil dirinya sendiri ). Dengan demikian, algoritma ini
dapat diimplementasikan dengan cara iteratif ( perulangan biasa ), karena pada
prinsipnya iteratif hampir sama dengan rekursif.
Salah satu penggunaan algoritma ini yang paling populer adalah dalam hal
pengolahan data yang bertipe array ( elemen larik ).
Mengapa ? Karena1pengolahan array pada umumnya selalu menggunakan prinsip rekursif atau iteratif.

Penggunaan secara spesifik adalah untuk mencari nilai minimal dan
maksimal serta untuk mengurutkan elemen array. Dalam hal pengurutan ini ada
empat macam algoritma pengurutan yang berdasar pada algoritma Divide and
Conquer, yaitu merge sort, insert sort, quick sort, dan selection sort. Merge sort
dan Quick sort mempunyai kompleksitas algoritma O(n ²log n). Hal ini lebih baik
jika dibandingkan dengan pengurutan biasa dengan menggunakan algoritma brute
force.

Skema Umum Algoritma Divide and Conquer :
prosedure DIVIDE_n_CONQUER(input n : integer)
{ Masukan: masukan yang berukuran n
Keluaran: solusi dari masalah semula
}
Deklarasi
r, k : integer
Algoritma
if n ≤ n0 then { masalah sudah cukup kecil }
SOLVE sub-masalah yang berukuran n ini
else
Bagi menjadi r sub-masalah, masing-masing
Berukuran n/
for masing-masing dari r upa-masalah do
DIVIDE_n_CONQUER(n/k)
endfor
COMBINE solusi dari r sub-masalah menjadi
solusi masalah semula
endif

SUMBER : gapra.files.wordpress.com/2009/01/algoritma-divide-and-conquer.pdf