SEJARAH, DEFINISI DAN CARA KERJA ALGORITMA DIVIDE AND CONQUER

 Nama    : Ilham Baihaqi

Kelas    : IF 20 E

NPM    : 20312152

Sejarah, Definisi dan Cara Kerja Algoritma Divide and Conquer

A. Sejarah Algoritma Divide and Conqueror

Algoritma Divide And Conquer ditemukan oleh seorang ilmuwan Rusia bernama Anatolii Alexeevich Karatsuba pada tahun 1960. Pada mulanya, Anatolii menemukan algoritma yang lebih cepat untuk mengalihkan dua buah bilangan bulat yang besar dengan kompleksitas O(nlog 3).

B. Definisi Algoritma Divide and Conqueror

  Algoritma Divide and Conquer merupakan algoritma yang sangat populer di dunia Ilmu Komputer. Divide and Conquer merupakan algoritma yang berprinsip memecah-mecah permasalahan yang terlalu besar menjadi beberapa bagian kecil sehingga lebih mudah untuk diselesaikan. Langkah-langkah umum algoritma Divide and Conquer :

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 ).

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

    Objek masalah yang di bagi adalah masukan (input) atau instances yang berukuran n: tabel (larik), matriks, dan sebagainya, bergantung pada masalahnya. Tiap-tiap upa-masalah mempunyai karakteristik yang sama (the same type) dengan karakteristik masalah asal, sehingga metode Divide and Conquer lebih natural diungkapkan dalam skema rekursif. Sesuai dengan karakteristik pembagian dan pemecahan masalah tersebut, maka algoritma ini dapat berjalan baik pada persoalan yang bertipe rekursif (perulangan dengan memanggil dirinya sendiri). Dengan demikian, algoritma ini dapat diimplementasikan dengan cara iteratif ( perulangan biasa ), karena pada prinsipnya iteratif hampir sama dengan rekursif. Salah satu penggunaan algoritma ini yang paling populer adalah dalam hal pengolahan data yang bertipe array ( elemen larik ). Mengapa ? Karena pengolahan array pada umumnya selalu menggunakan prinsip rekursif atau iteratif. Penggunaan secara spesifik adalah untuk mencari nilai minimal dan maksimal serta untuk mengurutkan elemen array. Dalam hal pengurutan ini ada empat macam algoritma pengurutan yang berdasar pada algoritma Divide and Conquer, yaitu merge sort, insert sort, quick sort, dan selection sort. Merge sort dan Quick sort mempunyai kompleksitas algoritma O(n ²log n). Hal ini lebih baik jika dibandingkan dengan pengurutan biasa dengan menggunakan algoritma brute force.

C. Cara Kerja Algoritma Divide and Conqueror

Divide : artinya membagi masalah menjadi beberapa sub-masalah yang memiliki masalah dengan permasalahan 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 solusi 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