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