DAA - Problème Max-Min

Considérons un problème simple qui peut être résolu par une technique de division et de conquête.

Énoncé du problème

Le problème Max-Min dans l'analyse d'algorithme est de trouver la valeur maximale et minimale dans un tableau.

Solution

Pour trouver les nombres maximum et minimum dans un tableau donné numbers[] de taille n, l'algorithme suivant peut être utilisé. Premièrement, nous représentons lenaive method et ensuite nous présenterons divide and conquer approach.

Méthode naïve

La méthode naïve est une méthode de base pour résoudre n'importe quel problème. Dans cette méthode, le nombre maximum et minimum peut être trouvé séparément. Pour trouver les nombres maximum et minimum, l'algorithme simple suivant peut être utilisé.

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)

Une analyse

Le nombre de comparaison dans la méthode naïve est 2n - 2.

Le nombre de comparaisons peut être réduit en utilisant l'approche de division et de conquête. Voici la technique.

Approche Diviser pour Vaincre

Dans cette approche, le réseau est divisé en deux moitiés. Ensuite, en utilisant une approche récursive, les nombres maximum et minimum dans chaque moitié sont trouvés. Plus tard, renvoyez le maximum de deux maxima de chaque moitié et le minimum de deux minima de chaque moitié.

Dans ce problème donné, le nombre d'éléments dans un tableau est $ y - x + 1 $, où y est supérieur ou égal à x.

$ \ mathbf {\ mathit {Max - Min (x, y)}} $ retournera les valeurs maximum et minimum d'un tableau $ \ mathbf {\ mathit {nombres [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))

Une analyse

Laisser T(n) soit le nombre de comparaisons faites par $ \ mathbf {\ mathit {Max - Min (x, y)}} $, où le nombre d'éléments $ n = y - x + 1 $.

Si T(n) représente les nombres, alors la relation de récurrence peut être représentée par

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

Supposons que n est sous la forme de puissance de 2. Par conséquent,n = 2k où k est la hauteur de l'arbre de récursivité.

Alors,

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

Par rapport à la méthode Naïve, dans l'approche diviser pour conquérir, le nombre de comparaisons est moindre. Cependant, en utilisant la notation asymptotique, les deux approches sont représentées parO(n).