DAA - Problema máximo-mínimo

Consideremos un problema simple que se puede resolver mediante la técnica de dividir y conquistar.

Planteamiento del problema

El problema Max-Min en el análisis de algoritmos es encontrar el valor máximo y mínimo en una matriz.

Solución

Para encontrar los números máximo y mínimo en una matriz dada numbers[] de tamaño n, se puede utilizar el siguiente algoritmo. Primero estamos representando elnaive method y luego te presentaremos divide and conquer approach.

Método ingenuo

El método ingenuo es un método básico para resolver cualquier problema. En este método, el número máximo y mínimo se puede encontrar por separado. Para encontrar los números máximos y mínimos, se puede utilizar el siguiente algoritmo sencillo.

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álisis

El número de comparación en el método Naive es 2n - 2.

El número de comparaciones se puede reducir utilizando el enfoque de divide y vencerás. A continuación se muestra la técnica.

Enfoque de dividir y conquistar

En este enfoque, la matriz se divide en dos mitades. Luego, utilizando el enfoque recursivo, se encuentran los números máximos y mínimos en cada mitad. Posteriormente, devuelve el máximo de dos máximos de cada mitad y el mínimo de dos mínimos de cada mitad.

En este problema dado, el número de elementos en una matriz es $ y - x + 1 $, donde y es mayor o igual a x.

$ \ mathbf {\ mathit {Max - Min (x, y)}} $ devolverá los valores máximo y mínimo de una matriz $ \ mathbf {\ mathit {números [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álisis

Dejar T(n) ser el número de comparaciones hechas por $ \ mathbf {\ mathit {Max - Min (x, y)}} $, donde el número de elementos $ n = y - x + 1 $.

Si T(n) representa los números, entonces la relación de recurrencia se puede representar como

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

Asumamos que n está en forma de poder de 2. Por lo tanto,n = 2^k dónde k es la altura del árbol de recursividad.

Entonces,

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

En comparación con el método Naïve, en el enfoque de divide y vencerás, el número de comparaciones es menor. Sin embargo, usando la notación asintótica, ambos enfoques están representados porO(n).