DAA - Bagilah & Taklukkan

Banyak algoritme bersifat rekursif untuk menyelesaikan masalah tertentu secara rekursif menangani sub-masalah.

Di divide and conquer approach, sebuah masalah dibagi menjadi beberapa masalah yang lebih kecil, kemudian masalah yang lebih kecil diselesaikan secara mandiri, dan akhirnya solusi dari masalah yang lebih kecil digabungkan menjadi solusi untuk masalah besar.

Umumnya, algoritma divide-and-conquer memiliki tiga bagian -

Divide the problem menjadi sejumlah sub-masalah yang merupakan contoh kecil dari masalah yang sama.
Conquer the sub-problemsdengan memecahkannya secara rekursif. Jika cukup kecil, selesaikan sub-masalah sebagai kasus dasar.
Combine the solutions ke sub masalah menjadi solusi untuk masalah aslinya.

Pro dan kontra dari Divide and Conquer Approach

Pendekatan divide and conquer mendukung paralelisme karena sub-masalah bersifat independen. Oleh karena itu, algoritma yang dirancang dengan menggunakan teknik ini, dapat berjalan pada sistem multiprosesor atau pada mesin yang berbeda secara bersamaan.

Dalam pendekatan ini, sebagian besar algoritma dirancang dengan menggunakan rekursi, oleh karena itu manajemen memori sangat tinggi. Untuk stack fungsi rekursif digunakan, di mana status fungsi perlu disimpan.