Nama
: Fajar Saputra
NPM : 21312063
Kelas : IF 21 B
Divide
and Conquer dulunya adalah strategi militer yang dikenal dengan nama divide ut
imperes. Sekarang strategi tersebut menjadi strategi fundamental di dalam ilmu
komputer dengan nama Divide and Conquer. pengertian
a. Divide:
membagi masalah menjadi beberapa upa-masalah yang memiliki kemiripan dengan
masalah semula namun berukuran lebih kecil (idealnya berukuran hampir sama),
b. Conquer:
memecahkan (menyelesaikan) masing-masing upa-masalah (secara rekursif), dan
c. Combine:
mengabungkan solusi masing-masing upa-masalah sehingga membentuk solusi masalah
semula.
Obyek
permasalahan yang dibagi : masukan (input) atau instances yang berukuran n seperti:
- tabel (larik), - matriks, - eksponen, - dll, 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. Perkembangan Algoritma Divide and Conquer
Algoritma divide and conquer sudah lama diperkenalkan sebagai sumber dari
pengendalian proses paralel, karena masalah-masalah yang terjadi dapat diatasi
secara independen. Banyak arsitektur dan bahasa pemrograman paralel mendesain
implementasinya (aplikasi) dengan struktur dasar dari algoritma divide and
conquer. Untuk menyelesaikan masalah-masalah yang besar, dan dibagi (dipecah)
menjadi bagian yang lebih kecil dan menggunakan sebuah solusi untuk menyelesaikan
problem awal adalah prinsip dasar dari pemrograman/strategi divide and conquer.
Definisi Algoritma Devide dan Conquer
Dalam ilmu
komputer, Algoritma divide and conquer adalah paradigma desain algoritma yang
didasarkan pada rekursi multi-cabang. Algoritme bagi-dan-taklukkan bekerja
dengan memecah masalah secara rekursif menjadi dua atau lebih sub-masalah dari
jenis yang sama atau terkait, hingga masalah ini menjadi cukup sederhana untuk
diselesaikan secara langsung.
Cara Kerja Algoritma Devide dan Conquer
Contoh
sederhana : Misalkan, untuk menghitung total jumlah dari bilangan-bilangan yang
ada di dalam sebuah list, kita dapat menggunakan perulangan sederhana
nums = [1, 2,
3, 5, 6, 7, 19, 28, 58, 18, 28, 67, 13]
total = 0
for i in
range(0, len(nums)):
total = total + nums[i]
print(total) #
255
Algoritma
perulangan yang digunakan pada kode di atas memang sederhana dan memberikan
hasil yang benar, tetapi terdapat beberapa masalah pada kode tersebut, yaitu
perhitungan dilakukan secara linear, yang menghasilkan kompleksitas O(n). Hal
ini tentunya cukup ideal untuk ukuran list kecil, tetapi jika ukuran list
menjadi besar (beberapa Milyar elemen) maka perhitungan akan menjadi sangat
lambat. Kenapa perhitungannya menjadi lambat? Karena nilai dari total
tergantung kepada kalkulasi nilai total sebelumnya. Kita tidak dapat melakukan
perhitungan total dari depan dan belakang list sekaligus, sehingga kita dapat
mempercepat perhitungan dua kali lipat. Dengan kode di atas, kita tidak dapat
membagi-bagikan pekerjaan ke banyak pekerja / CPU!
Lalu apa yang
dapat kita lakukan? Langkah pertama yang dapat kita lakukan adalah menerapkan
teknik rekursif untuk membagi-bagikan masalah menjadi masalah yang lebih kecil.
Jika awalnya kita harus menghitung total keseluruhan list satu per satu,
sekarang kita dapat melakukan perhitungan dengan memecah-mecah list terlebih
dahulu:
def sums(lst):
if len(lst) >= 1:
return lst[0]
mid = len(lst) // 2
left = sums(lst[:mid])
right = sums(lst[mid:])
return left + right
print(sums(nums))
# 255
- Baris if len(lst) >= 1 memberikan
syarat pemberhentian fungsi rekursif, yang akan mengembalikan isi dari
list ketika list berukuran 1 (hanya memiliki satu elemen).
- Baris mid = len(lst) // 2 mengambil median
dari list, sebagai referensi ketika kita membagi list menjadi dua bagian.
- Baris left = sum(lst[:mid]) dan selanjutnya membagikan list menjadi dua bagian, dengan nilai mid sebagai tengah dari list.
0 Komentar