Rangkuman: Divide and Conquer

1. Pengertian

Divide and Conquer (D&C) adalah sebuah paradigma desain algoritma yang kuat untuk memecahkan masalah dengan tiga langkah utama: membagi, menaklukkan, dan menggabungkan. Paradigma ini sering digunakan untuk masalah yang dapat dipecah menjadi sub-masalah yang lebih kecil, independen, dan mirip dengan masalah aslinya.

2. Tiga Langkah Dasar

1. Divide (Bagi):

   Pecah masalah besar menjadi dua atau lebih sub-masalah yang lebih kecil. Sub-masalah ini idealnya memiliki tipe yang sama dengan masalah aslinya, namun dalam skala yang lebih kecil.

2. Conquer (Taklukkan):

   Selesaikan sub-masalah secara rekursif. Jika sub-masalah cukup kecil (kasus dasar), selesaikan secara langsung.

3. Combine (Gabungkan):

   Gabungkan solusi dari sub-masalah yang ditaklukkan untuk mendapatkan solusi dari masalah asli.

3. Kapan Menggunakan Divide and Conquer?

• Ketika masalah dapat dipecah menjadi sub-masalah yang independen dan identik (hanya berbeda ukuran).
• Solusi dari sub-masalah dapat digabungkan dengan mudah.
• Dapat menghasilkan algoritma yang lebih efisien dibandingkan metode brute-force.

4. Contoh Algoritma Divide and Conquer

a. Merge Sort

• Divide: Membagi array menjadi dua sub-array sampai setiap sub-array hanya memiliki satu elemen.
• Conquer: Mengurutkan setiap sub-array (satu elemen sudah terurut).
• Combine: Menggabungkan (merge) dua sub-array yang terurut menjadi satu array terurut yang lebih besar.
• Kompleksitas Waktu: $O(N \log N)$

b. Quick Sort

• Divide: Memilih sebuah elemen sebagai 'pivot' dan mempartisi array di sekitar pivot, sehingga semua elemen yang lebih kecil dari pivot berada di kirinya, dan yang lebih besar di kanannya.
• Conquer: Secara rekursif mengurutkan sub-array di kiri dan kanan pivot.
• Combine: Tidak ada langkah combine terpisah karena array sudah terurut setelah partisi dan rekursi selesai.
• Kompleksitas Waktu: $O(N \log N)$ rata-rata, $O(N^2)$ terburuk.

c. Binary Search (Pencarian Biner)

• Divide: Membagi ruang pencarian menjadi dua bagian berdasarkan nilai tengah.
• Conquer: Mencari elemen di salah satu bagian (kiri atau kanan).
• Combine: Tidak ada, karena masalah direduksi menjadi sub-masalah yang lebih kecil sampai ditemukan atau tidak ada lagi.
• Kompleksitas Waktu: $O(\log N)$

5. Keuntungan & Kerugian

Keuntungan:

• Seringkali menghasilkan algoritma yang efisien.
• Sesuai untuk pemrograman paralel karena sub-masalah bisa diselesaikan secara independen.
• Memanfaatkan memori cache secara efisien (cache-friendly).

Kerugian:

• Overhead rekursi (penggunaan memori untuk stack panggilan).
• Kadang-kadang lebih sulit untuk dipahami dan diimplementasikan dibandingkan pendekatan iteratif.
• Tidak cocok jika sub-masalah sangat tumpang tindih.