DAA - Masalah Max-Min
Mari kita bahas satu masalah sederhana yang bisa diselesaikan dengan teknik divide and conquer.
Pernyataan masalah
Masalah Max-Min dalam analisis algoritma adalah menemukan nilai maksimum dan minimum dalam sebuah array.
Larutan
Untuk menemukan angka maksimum dan minimum dalam larik tertentu numbers[] ukuran n, algoritme berikut dapat digunakan. Pertama kami mewakilinaive method dan kemudian kami akan mempresentasikan divide and conquer approach.
Metode Naif
Metode naif adalah metode dasar untuk menyelesaikan masalah apa pun. Dalam metode ini, jumlah maksimum dan minimum dapat ditemukan secara terpisah. Untuk mencari angka maksimum dan minimum, algoritma langsung berikut dapat digunakan.
Algorithm: Max-Min-Element (numbers[])
max := numbers[1]
min := numbers[1]
for i = 2 to n do
if numbers[i] > max then
max := numbers[i]
if numbers[i] < min then
min := numbers[i]
return (max, min)
Analisis
Jumlah perbandingan dalam metode Naive adalah 2n - 2.
Jumlah perbandingan dapat dikurangi dengan menggunakan pendekatan divide and conquer. Berikut tekniknya.
Bagi dan Taklukkan Pendekatan
Dalam pendekatan ini, larik dibagi menjadi dua bagian. Kemudian menggunakan pendekatan rekursif, jumlah maksimum dan minimum di setiap bagian ditemukan. Nanti, kembalikan maksimal dua maksimal setiap separuh dan minimal dua minimal tiap separuh.
Dalam soal yang diberikan ini, jumlah elemen dalam array adalah $ y - x + 1 $, di mana y lebih besar atau sama dengan x.
$ \ mathbf {\ mathit {Max - Min (x, y)}} $ akan mengembalikan nilai maksimum dan minimum dari array $ \ mathbf {\ mathit {numbers [x ... y]}} $.
Algorithm: Max - Min(x, y)
if y – x ≤ 1 then
return (max(numbers[x], numbers[y]), min((numbers[x], numbers[y]))
else
(max1, min1):= maxmin(x, ⌊((x + y)/2)⌋)
(max2, min2):= maxmin(⌊((x + y)/2) + 1)⌋,y)
return (max(max1, max2), min(min1, min2))
Analisis
Membiarkan T(n) jadilah jumlah perbandingan yang dibuat dengan $ \ mathbf {\ mathit {Max - Min (x, y)}} $, di mana jumlah elemen $ n = y - x + 1 $.
Jika T(n) mewakili angka-angka tersebut, maka relasi perulangan dapat direpresentasikan sebagai
$$ T (n) = \ begin {cases} T \ left (\ lfloor \ frac {n} {2} \ rfloor \ right) + T \ left (\ lceil \ frac {n} {2} \ rceil \ right ) +2 & untuk \: n> 2 \\ 1 & untuk \: n = 2 \\ 0 & untuk \: n = 1 \ end {cases} $$
Mari kita asumsikan n adalah dalam bentuk kekuatan 2. Karenanya,n = 2k dimana k adalah ketinggian pohon rekursi.
Begitu,
$$ T (n) = 2.T (\ frac {n} {2}) + 2 = 2. \ left (\ begin {array} {c} 2.T (\ frac {n} {4}) + 2 \ end {larik} \ kanan) + 2 ..... = \ frac {3n} {2} - 2 $$
Dibandingkan dengan metode Naïve, pada pendekatan divide and conquer jumlah pembandingnya lebih sedikit. Namun, dengan menggunakan notasi asimtotik kedua pendekatan direpresentasikan olehO(n).