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.
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.
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.
Tidak ada komentar:
Posting Komentar