DAA - Problema Max-Min

Consideriamo un semplice problema che può essere risolto con la tecnica del divide et impera.

Dichiarazione problema

Il problema Max-Min nell'analisi algoritmica è trovare il valore massimo e minimo in un array.

Soluzione

Per trovare i numeri massimi e minimi in un dato array numbers[] di dimensioni n, è possibile utilizzare il seguente algoritmo. Per prima cosa rappresentiamo ilnaive method e poi ci presenteremo divide and conquer approach.

Metodo naïve

Il metodo naïve è un metodo di base per risolvere qualsiasi problema. In questo metodo, il numero massimo e minimo possono essere trovati separatamente. Per trovare i numeri massimi e minimi, è possibile utilizzare il seguente algoritmo semplice.

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)

Analisi

Il numero di confronto nel metodo Naive è 2n - 2.

Il numero di confronti può essere ridotto utilizzando l'approccio divide et impera. Di seguito è la tecnica.

Approccio Dividi e Conquista

In questo approccio, l'array è diviso in due metà. Quindi utilizzando l'approccio ricorsivo si trovano i numeri massimi e minimi in ciascuna metà. Successivamente, restituisci il massimo di due massimi di ciascuna metà e il minimo di due minimi di ciascuna metà.

In questo dato problema, il numero di elementi in un array è $ y - x + 1 $, dove y è più grande di O uguale a x.

$ \ mathbf {\ mathit {Max - Min (x, y)}} $ restituirà i valori massimo e minimo di un 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))

Analisi

Permettere T(n) essere il numero di confronti effettuati da $ \ mathbf {\ mathit {Max - Min (x, y)}} $, dove il numero di elementi $ n = y - x + 1 $.

Se T(n) rappresenta i numeri, quindi la relazione di ricorrenza può essere rappresentata come

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

Supponiamo che n è sotto forma di potere di 2. Quindi,n = 2k dove k è l'altezza dell'albero di ricorsione.

Così,

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

Rispetto al metodo Naïve, nell'approccio divide et impera, il numero di confronti è inferiore. Tuttavia, utilizzando la notazione asintotica entrambi gli approcci sono rappresentati daO(n).