Algoritma Divide and Conquer

A. Sejarah Algoritma Divide and Conquer

Awalnya Algoritma Divine and Conquer ini adalah algoritma pengurangan dan penaklukan-masalah asli secara berturut-turut akan dipecah menjadi sub-problem tunggal dan dapat diselesaikan secara berulang.

Algoritma Divide and conquer atau jika diartikan berarti Algoritma penurunan dan penaklukan dimana sub-problem berukuran sekitar setengah dari ukuran aslinya, mempunyai sejarah yang panjang. Deskripsi algoritma yang jelas pada komputer tercipta pada tahun 1946 dalam suatu artikel oleh John Mauchly, dalam gagasannya untuk menggunakan daftar item (item list) yang diurutkan untuk memfasilitasi pencarian tanggal sebelumnya sekitar sejauh Babylonia pada 200 SM.

Algoritma Divide and Conquer ditemukan oleh seorang ilmuan asal rusia yang bernama Anatolii Alaxeevich Karatsuba pada tahun 1960. Pada awalnya, Anatolii menemukan algoritma yang lebih cepat untuk mengalikan dua bilangan bulat yang besar dengan kompleksitas O(nlog 3),

Gambar Anatolii Alaxeevich Karatsuba

         

Algoritma Divide and Conquer yang kuno lainnya adalah algoritma Euclidean yang digunakan untuk menghitung suatu pembagian persekutuan terbesar dari dua bilangan dengan mengurangi bilangan tersebut menjadi sub-masalah ekuivalen yang lebih kecil dan semakin kecil.

Contoh awal algoritma Divide and Conquer dengan beberapa sub-masalah adalah seperti yang dideskripsikan Gauss pada tahun 1805 tentang algoritma yang sekarang dinamakan algoritma Cooley-Tukey Fast Fourier Transform (FFT), walaupun ia tidak menganalisis jumlah dari operasinya secara kuantitatif, dan FFT tidak terlalu tersebar luas hingga ditemukan kembali.

B. Definisi Algoritma Divide and Conquer

• Divide : artinya membagi persoalan menjadi beberapa sub-masalah yang memilki kemiripan dengan persoalan semula namun lebih kecil dari sebelumnya atau sama dengan sebelumnya.

• Conquer : artinya menyelesaikan masing-masing sub-masalah secara rekursif.

Algoritma Divide and Conquer adalah algoritma yang sangat populer pada di dunia ilmu komputer. Algoritma Divide and Conquer adalah algoritma yang memiliki prinsip untuk membagi-bagi permasalahan yang terlalu besar menjadi beberapa atau sub-masalah yang lebih kecil sehingga menjadi mudah untuk diselesaikan. sub-sub masalah yang telah dibagi menjadi beberapa bagian yang lebih kecil kemudian akan dicari solusinya, setelah mendapatkan solusinya, solusi dari sub-sub masalah tersebut akan digabung menjadi satu untuk menyelesaikan masalah awal atau masalah utama. 

C. Cara Kerja Algoritma Divide and Conquer

• Divide : artinya membagi persoalan menjadi beberapa sub-masalah yang memilki kemiripan dengan persoalan semula namun lebih kecil dari sebelumnya atau sama dengan sebelumnya.

• Conquer : artinya menyelesaikan masing-masing sub-masalah secara rekursif.

• Combine : artinya menggabungkan solusi dari masing-masing sub-masalah sehingga dapat menyelesaikan masalah utama atau masalah awal.

Algoritma ini akan membagi n input menjadi k subset input yang berbeda (1<k≤n). Dari k subset input yang berbeda akan terdapat k submasalah, setiak submasalah mempunyai solusinya masing-masing. Sehingga akan diperoleh subsolusi k. Kemudian, dari subsolusi k akan diperoleh solusi yang optimal atau solusi yang diharapkan.

Jika submasalah masih dianggap terlalu besar, maka metode Divide and Conquer dapat digunakan lagi secara berulang-ulang