DAA - Maks-Min Sorunu

Böl ve yönet tekniği ile çözülebilecek basit bir problemi ele alalım.

Sorun bildirimi

Algoritma analizinde Max-Min Problemi, bir dizideki maksimum ve minimum değeri bulmaktır.

Çözüm

Belirli bir dizideki maksimum ve minimum sayıları bulmak için numbers[] boyut naşağıdaki algoritma kullanılabilir. Önce biz temsil ediyoruznaive method ve sonra sunacağız divide and conquer approach.

Naif Yöntem

Naif yöntem, herhangi bir sorunu çözmek için temel bir yöntemdir. Bu yöntemde maksimum ve minimum sayı ayrı ayrı bulunabilir. Maksimum ve minimum sayıları bulmak için aşağıdaki basit algoritma kullanılabilir.

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)

Analiz

Naive yönteminde karşılaştırma sayısı 2n - 2.

Böl ve yönet yaklaşımı kullanılarak karşılaştırma sayısı azaltılabilir. Aşağıdaki tekniktir.

Böl ve Fethet Yaklaşımı

Bu yaklaşımda, dizi ikiye bölünmüştür. Daha sonra özyinelemeli yaklaşım kullanılarak her yarıda maksimum ve minimum sayılar bulunur. Daha sonra, her bir yarının maksimum iki maksimumunu ve her bir yarının minimum iki minimumunu döndürün.

Bu verilen problemde, bir dizideki eleman sayısı $ y - x + 1 $ 'dır, burada y büyüktür veya eşittir x.

$ \ mathbf {\ mathit {Max - Min (x, y)}} $, $ \ mathbf {\ mathit {sayılar [x ... y]}} $ dizisinin maksimum ve minimum değerlerini döndürür.

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

Analiz

İzin Vermek T(n) $ \ mathbf {\ mathit {Max - Min (x, y)}} $ ile yapılan karşılaştırmaların sayısı, burada $ n = y - x + 1 $ öğelerinin sayısı.

Eğer T(n) sayıları temsil ederse, tekrarlama ilişkisi şu şekilde temsil edilebilir:

$$ T (n) = \ başla {vakalar} T \ left (\ lfloor \ frac {n} {2} \ rfloor \ right) + T \ left (\ lceil \ frac {n} {2} \ rceil \ right ) +2 & for \: n> 2 \\ 1 & for \: n = 2 \\ 0 & for \: n = 1 \ end {case} $$

Farz edelim ki n güç biçimindedir 2. Bu nedenlen = 2k nerede k özyineleme ağacının yüksekliğidir.

Yani,

$$ T (n) = 2.T (\ frac {n} {2}) + 2 = 2. \ left (\ begin {dizi} {c} 2.T (\ frac {n} {4}) + 2 \ end {dizi} \ sağ) + 2 ..... = \ frac {3n} {2} - 2 $$

Naif yöntemine kıyasla böl ve yönet yaklaşımında karşılaştırma sayısı daha azdır. Ancak, asimptotik gösterimi kullanarak her iki yaklaşım da şu şekilde temsil edilir:O(n).