DAA - Problema Max-Min

Vamos considerar um problema simples que pode ser resolvido pela técnica de dividir para conquistar.

Declaração do Problema

O problema Max-Min na análise de algoritmos é encontrar o valor máximo e mínimo em uma matriz.

Solução

Para encontrar os números máximo e mínimo em uma determinada matriz numbers[] de tamanho n, o seguinte algoritmo pode ser usado. Primeiro estamos representando onaive method e então apresentaremos divide and conquer approach.

Método Naïve

O método ingênuo é um método básico para resolver qualquer problema. Neste método, o número máximo e mínimo podem ser encontrados separadamente. Para encontrar os números máximo e mínimo, o seguinte algoritmo simples pode ser usado.

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)

Análise

O número de comparação no método ingênuo é 2n - 2.

O número de comparações pode ser reduzido usando a abordagem de dividir para conquistar. A seguir está a técnica.

Abordagem de divisão e conquista

Nesta abordagem, a matriz é dividida em duas metades. Então, usando a abordagem recursiva, os números máximo e mínimo em cada metade são encontrados. Posteriormente, retorne o máximo de dois máximos de cada metade e o mínimo de dois mínimos de cada metade.

Neste problema, o número de elementos em uma matriz é $ y - x + 1 $, onde y é maior que ou igual a x.

$ \ mathbf {\ mathit {Max - Min (x, y)}} $ retornará os valores máximo e mínimo de um 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))

Análise

Deixei T(n) seja o número de comparações feitas por $ \ mathbf {\ mathit {Max - Min (x, y)}} $, onde o número de elementos $ n = y - x + 1 $.

E se T(n) representa os números, então a relação de recorrência pode ser representada como

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

Vamos supor que n está na forma de poder de 2. Conseqüentemente,n = 2^k Onde k é a altura da árvore de recursão.

Então,

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

Em comparação com o método Naïve, na abordagem dividir para conquistar, o número de comparações é menor. No entanto, usando a notação assintótica, ambas as abordagens são representadas porO(n).