Algoritma Divide & Conquer

Dalam ilmu komputer , Devide dan Conquer (D & C) adalah penting desain algoritma berdasarkan multi-bercabang rekursi . Sebuah algoritma devide dan conquer rekursif bekerja dengan memecah masalah menjadi dua atau lebih sub-masalah yang sama (atau terkait) jenis, sampai ini menjadi cukup sederhana untuk dipecahkan secara langsung.. Solusi ke sub masalah kemudian dikombinasikan untuk memberikan solusi bagi masalah yang asli.

Teknik dasar dari algoritma ini efisien untuk semua jenis masalah, seperti sortasi (misalnya, quicksort , menggabungkan jenis ), mengalikan jumlah besar (misalnya Karatsuba ), analisis sintaksis (misalnya, top-down parser ), dan menghitung Fourier diskrit transformasi ( FFTs ).

Di sisi lain, kemampuan untuk memahami dan desain algoritma D & C adalah keterampilan yang membutuhkan waktu untuk menguasai. Seperti ketika membuktikan suatu teorema dengan induksi, itu perlu untuk menggantikan masalah yang asli oleh umum atau masalah yang lebih rumit untuk mendapatkan rekursi berjalan, dan tidak ada metode sistematis untuk menemukan generalisasi yang tepat.

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), dan

Combine: mengabungkan solusi masing-masing upa-masalah sehingga membentuk solusi masalah semula.

Obyek permasalahan yang dibagi :
masukan (input) atau instances yang berukuran n seperti:
- tabel (larik),
- matriks,
- eksponen,
- dll, bergantung pada masalahnya.

Tiap-tiap masalah mempunyai karakteristik yang sama (the same type) dengan karakteristik masalah asal, sehingga metode Divide and Conquer lebih natural diungkapkan dalam skema rekursif.

Sumber disini