DAA - Max-Min Problem

Rozważmy prosty problem, który można rozwiązać za pomocą techniki dziel i rządź.

Stwierdzenie problemu

Problem Max-Min w analizie algorytmu polega na znalezieniu maksymalnej i minimalnej wartości w tablicy.

Rozwiązanie

Aby znaleźć maksymalną i minimalną liczbę w danej tablicy numbers[] wielkościowy n, można użyć następującego algorytmu. Najpierw reprezentujemynaive method a potem przedstawimy divide and conquer approach.

Metoda naiwna

Metoda naiwna to podstawowa metoda rozwiązania każdego problemu. W tej metodzie maksymalną i minimalną liczbę można znaleźć osobno. Aby znaleźć wartości maksymalne i minimalne, można użyć następującego prostego algorytmu.

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)

Analiza

Liczba porównań w metodzie Naive wynosi 2n - 2.

Liczbę porównań można zmniejszyć, stosując metodę dziel i rządź. Oto technika.

Podejście dziel i zwyciężaj

W tym podejściu tablica jest podzielona na dwie połowy. Następnie przy użyciu podejścia rekurencyjnego znajduje się maksymalne i minimalne liczby w każdej połowie. Później zwróć maksymalnie dwa maksima z każdej połowy i co najmniej dwie minima z każdej połowy.

W tym zadaniu liczba elementów w tablicy wynosi $ y - x + 1 $, gdzie y jest większa niż lub równa x.

$ \ mathbf {\ mathit {Max - Min (x, y)}} $ zwróci maksymalne i minimalne wartości tablicy $ \ mathbf {\ mathit {numery [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))

Analiza

Pozwolić T(n) być liczbą porównań wykonanych przez $ \ mathbf {\ mathit {Max - Min (x, y)}} $, gdzie liczba elementów $ n = y - x + 1 $.

Jeśli T(n) reprezentuje liczby, wówczas relację powtarzania można przedstawić jako

$$ T (n) = \ begin {cases} T \ left (\ lfloor \ frac {n} {2} \ rfloor \ right) + T \ left (\ lceil \ frac {n} {2} \ rceil \ right) ) +2 & dla \: n> 2 \\ 1 & dla \: n = 2 \\ 0 & dla \: n = 1 \ end {cases} $$

Załóżmy, że n ma postać mocy 2. W związku z tym,n = 2^k gdzie k jest wysokością drzewa rekurencji.

Więc,

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

W porównaniu do metody Naiwnej, w podejściu dziel i rządź, liczba porównań jest mniejsza. Jednak przy użyciu notacji asymptotycznej oba podejścia są reprezentowane przezO(n).