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 ? Karena pengolahan 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.


2. Klasifikasi dari Algoritma / Strategi Divide dan Conquer
Berikut klasifikasi algoritma divide and conquer, kita bisa melihat daftar dan karakteristik dari beberapa algoritma yang ditunjukkan dalam tabel :















Tabel karakteristik dari Algoritma divide and conquer. Catatan bahwa quicksort dan quickhull bisa dikonversi kedalam algoritma yang balance dengan cara menemukan median (titik tengah) yang tepat.

untuk lebih jelasnya silahkan download disini

Sumber :

http://www.informatika.org/~rinaldi/Stmik/Algoritma%20Divide%20and%20Conquer.ppt
http://www.stttelkom.ac.id/staf/zka/Algoritma%20Divide%20and%20Conquer.pdf