Divide and Conquer
Komputer pada awalnya diciptakan
sebagai perangkat untuk melakukan kalkulasi secara otomatis dan akurat.
Meskipun awalnya hanya berfokus pada kalkukasi numerik, komputer modern yang
dijumpai sekarang telah melakukan kalkulasi pada banyak hal, seperti teks ataupun
gambar. Berbagai kalkulasi dan analisa yang dilakukan komputer biasanya
diimplementasikan melalui perangkat lunak. Dengan semakin besarnya ruang
lingkup hal-hal yang dilakukan oleh komputer, perangkat lunak yang dikembangkan
juga menjadi semakin kompleks. Algoritma, sebagai bagian dari perangkat lunak
yang melakukan pemrosesan, juga memerlukan berbagai teknik baru. 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)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
Apa yang kita lakukan pada kode di
atas?
- 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.
Singkatnya, setelah membagikan list
menjadi dua bagian terus menerus sampai bagian terkecilnya, kita menjumlahkan
kedua nilai list tersebut, seperti pada gambar berikut:
Langkah
Kerja Divide and Conquer
Apa kelebihan pendekatan dengan
membagi-bagikan masalah ini? Dengan menggunakan bahasa dan library yang tepat,
kita dapat membagi-bagikan setiap bagian rekursif (left = ... dan right = ...)
ke satu unit kerja baru, yang dikenal dengan nama thread. Mekanisme
pada sistem operasi atau compiler kemudian akan
membagi-bagikan tugas pembagian dan perhitungan lanjutan agar dapat dijalankan
secara paralel, misalnya dengan membagikan tugas ke dalam beberapa core prosesor,
atau bahkan ke dalam mesin lain (jika terdapat sistem dengan banyak mesin).
Dengan membagi-bagikan pekerjaan ke
dalam banyak unit, tentunya pekerjaan akan lebih cepat selesai! Teknik
memecah-mecah pekerjaan untuk kemudian dibagikan kepada banyak pekerja ini
dikenal dengan nama divide and conquer.
Membangun Algoritma Divide and Conquer
Sebuah algoritma divide and conquer
(selanjutnya disebut dengan D&C) memiliki tiga langkah, yaitu:
- Divide (Memecah): pada langkah
ini kita memecahkan masalah atau data ke dalam bentuk yang sama, tetapi
dalam ukuran yang lebih kecil. Pemecahan langkah biasanya dilakukan dengan
menggunakan algoritma rekursif, sampai ukuran data menjadi sangat kecil
dan dapat diselesaikan dengan algoritma sederhana.
- Conquer (Menaklukkan): dalam
langkah ini kita mencoba menyelesaikan masalah atau data yang telah
dipecahkan pada langkah pertama, dengan menggunakan algoritma sederhana.
- Combine (Menggabungkan):
setelah menjalankan langkah conquer, tentunya kita harus menggabungkan
kembali hasil dari masing-masing pecahan yang ada, untuk mendapatkan hasil
akhir kalkulasi. Langkah combine mencoba mencapai hal tersebut.
Algoritma D&C, jika
diimplementasikan menggunakan library atau bahasa yang tepat
akan meningkatkan efisiensi algoritma secara logaritmik. Mari kita lakukan
analisis pada fungsi sum di atas, untuk melihat
kompleksitas algoritmanya:
def sums(lst):
if len(lst) >= 1: # 1 langkah
return lst[0] # 1 langkah
mid = len(lst) // 2 # 1 langkah
left = sums(lst[:mid]) # sums(mid) langkah
right = sums(lst[mid:]) # sums(mid) langkah
return left + right # 1 langkah
yang secara matematis dapat
dituliskan seperti berikut:
f(n)=4+f(n2)+f(n2)=4+2f(n2)f(n)=4+f(n2)+f(n2)=4+2f(n2)
karena ukuran dari mid adalah
panjang list (nn) dibagi dua. Dengan begitu, kompleksitas dari algoritma
adalah:
f(n)=2f(n2)=2(2(n4))=2(2(2(n8)))...=2k(n2k)f(n)=2f(n2)=2(2(n4))=2(2(2(n8)))...=2k(n2k)
dengan syarat berhenti adalah
ketika k≥1k≥1, sehingga:
n2knk=1=2k=log2nn2k=1n=2kk=log2n
Kompleksitas dari fungsi sums adalah O(logn)O(logn), meningkat dari O(n)O(n) pada algoritma awal!
Secara umum, kompleksitas algoritma
D&C adalah O(nlogn)O(nlogn), jika ukuran data adalah nn,
dan pada setiap langkahnya kita membagikan masalah ke dalam pp sub-masalah.
Contoh D&C 1: Merge Sort
Merge sort, seperti namanya,
merupakan algoritma yang dirancang untuk melakukan pengurutan terhadap sekumpulan
bilangan. Ide utama dari merge sort sama dengan algoritma perhitungan total
yang telah kita lakukan sebelumnya, yaitu membagi-bagikan keseluruhan list
menjadi komponen kecil, dan kemudian mengurutkan komponen tersebut dan
menggabungkannya kembali menjadi sebuah list besar.
Berikut adalah merge sort yang
diimplementasikan dalam bahasa python:
def merge_sort(lst):
if len(lst) <= 1:
return lst
mid = len(lst) // 2
left = merge_sort(lst[:mid])
right = merge_sort(lst[mid:])
return merge(left, right)
def merge(left, right):
result = []
while len(left) > 0 or len(right)
> 0:
if len(left) > 0 and len(right)
> 0:
if left[0] <= right[0]:
result.append(left.pop(0))
else:
result.append(right.pop(0))
elif len(left) > 0:
result.append(left.pop(0))
elif len(right) > 0:
result.append(right.pop(0))
return result
Dari kode di atas terlihat bahwa
merge sort memiliki dua bagian, yang dituliskan dalam dua buah fungsi: merge dan merge_sort.
Fungsi merge_sort memiliki logika dan cara kerja yang sama dengan fungsi
penjumlahan total yang kita bangun sebelumnya, dengan perbedaan pada bagian
yang melakukan penggabungan list (return merge(left, right)).
Penggabungan list sendiri dilakukan
dengan cukup sederhana dan gamblang, yaitu hanya membandingkan elemen-elemen
dari dua buah list yang dikirimkan satu per satu, untuk kemudian disimpan ke
dalam variabel result secara terurut. Untuk lebih jelasnya, mari kita coba
bedah algoritma pada fungsi merge, langkah demi langkah.
Misalkan kita memanggil fungsi merge seperti
berikut:
left = [3, 5]
right
= [1, 4]
merge(left,
right)
Note
Ingat bahwa list pada variabel left maupun right harus
sudah terurut jika ukuran list lebih dari 1. Fungsi merge dengan
argumen list berukuran >> 1 hanya dipanggil dari
hasil merge dua buah list berukuran satu dalam kasus merge_sort.
Jika kita mengikuti langkah demi
langkah pada kode, maka pada setiap iterasi while kita akan mendapatkan nilai
masing-masing variabel sebagai berikut:
#
Awal fungsi
left = [3, 5]
right = [1, 4]
result
= []
#
Iterasi 1
left = [3, 5]
right = [4]
result
= [1]
#
Iterasi 2
left = [5]
right = [4]
result
= [1, 3]
#
Iterasi 3
left = [5]
right = []
result
= [1, 3, 4]
#
Iterasi 4
left = []
right = []
result
= [1, 3, 4, 5]
Penggabungan seperti di atas
dilakukan pada setiap submasalah yang telah dipecah oleh merge_sort,
sampai kita mendapatkan sebuah list dengan ukuran yang sama pada list awal.
Untuk mempermudah pengertian, gambar di bawah menunjukkan proses pemecahan dan
penggabungan kembali dari merge sort:
Langkah
Kerja Merge Sort
Proses divide terjadi ketika kotak
dan panah berwarna merah, sementara conquer dan combine terjadi ketika kotak
dan panah diberi warna biru. Proses conquer merupakan proses di mana kita
mengurutkan elemen dalam list, dan combine adalah ketika kita menggabungkan
hasil urutan dari list tersebut.
Contoh D&C 2: Binary Search
Binary search merupakan salah satu
algoritma pencarian yang paling efisien, dengan kompleksitas O(logn)O(logn). Algoritma ini memanfaatkan teknik divide and conquer
dengan memecah lingkup pencarian data menjadi setengahnya pada setiap kali
divide. Kekurangan dari binary search yaitu bahwa algoritma ini hanya dapat
digunakan pada sebuah data atau lsit yang telah terurut.
Langsung saja, implementasi binary
search menggunakan python:
def binary_search(data, search_val, min_idx, max_idx):
if max_idx < min_idx:
print("%d not found
in list"%search_val)
return -1
mid_idx = (min_idx + max_idx) // 2
if data[mid_idx] > search_val:
return binary_search(data, search_val,
min_idx, mid_idx - 1)
elif data[mid_idx] < search_val:
return binary_search(data, search_val,
mid_idx + 1, max_idx)
else:
print("%d found in
index %d"%(search_val, mid_idx))
return mid_idx
Mari kita lihat cara kerja binary
search. Misalkan kita diberikan data berupa list bilangan seperti berikut:
[1,
2, 4, 6, 7, 8, 9, 10]
dan diminta untuk mencari letak
angka 2 pada list tersebut. Sebelum mulai menjalankan
algoritma, pastinya kita harus mengetahui nilai-nilai awal terelbih dahulu.
Adapun nilai awal yang dibutuhkan untuk fungsi binary_search adalah sebagai berikut:
data = [1, 2, 4, 6, 7, 8, 9, 10]
search_val
= 2
min_idx = 0
max_idx = len(data) - 1 # 7
Nilai indeks minimal (batas awal
pencarian) yang pertama tentunya adalah 0, dengan nilai maksimal (batas akhir
pencarian) adalah ukuran dari list itu sendiri. Di langkah awal binary search,
dilakukan perhitungan terhadap nilai tengah dari min_idx dan max_idx terlebih
dahulu, untuk mendapatkan titik awal pencarian. Perhitungan nilai tengah
dilakukan pada kode berikut:
mid_idx
= (min_idx + max_idx) // 2
Setelah mendapatkan nilai tengah,
kita lalu melakukan cek apakah nilai dari data pada indeks tersebut lebih
besar atau lebih kecil dibandingkan nilai yang akan kita cari (2).
Langkah pengecekan ini dilakukan pada perintah if berikut:
if
data[mid_idx] > search_val:
# nilai lebih besar daripada 2
elif
data[mid_idx] < search_val:
# nilai lebih kecil daripada 2
else:
# nilai adalah 2 (ditemukan)
Dalam kasus ini, nilai dari mid_idx adalah 3,
dan karena data[3] berisi 6, maka kita akan melakukan
pemotongan terhadap seluruh nilai pada data setelah 6,
karena nilai tersebut sudah pasti tidak diperlukan lagi (ingat, data harus
terurut pada binary search). Kita lalu memanggil fungsi binary_search lagi, kali ini dengan mencari hanya pada submasalah
(list) berikut (perhatikan bagaimana pada pemanggilan binary_search yang kedua nilai max_idx kita
ubah menjadi mid_idx - 1):
[1,
2, 4]
Dan dengan mengaplikasikan logika
yang sama dengan tahap sebelumnya, kita akan langsung menemukan bilangan yang
dicari.
§ Alamat web Program studi, Fakultas, Universitas : http://ti.ftik.teknokrat.ac.id, http://ftik.teknokrat.ac.id, www.teknokrat.ac.id
§ Nama Mahasiswa : NADIYA SAFITRI
§ NPM : 19316014
§ Kelas : Tk19B
Tidak ada komentar:
Posting Komentar