Page 76 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
P. 76
INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS
if (a[i]>max)
max=a[i];
else if (a[i]<min)
min=a[i];
Ahora, el mejor caso surge cuando los elementos están en forma creciente, ya que en el mejor de
los casos se requieren n-1 comparaciones, mientras que en el peor de los casos se necesitan 2(n-1)
comparaciones. El promedio será:
[2(n-1) + n-1] / 2 = (3n-1) / 2 – 1.
A continuación, el algoritmo 2.11 muestra una forma recursiva para encontrar el máximo y el mínimo
de un conjunto de elementos y maneja la estrategia de divide y conquistarás. Este algoritmo envía
cinco parámetros: el primero es el arreglo para trabajar; los otros dos se manejan como paso de
parámetros por valor, y los dos últimos se manejan como pase de parámetros por referencia. En este
caso, el segundo y tercer parámetro indican el índice del subconjunto a analizar, y los dos últimos
parámetros sirven para retornar el mínimo y máximo de un subconjunto determinado. Al término de
la recursión se obtienen el mínimo y máximo del conjunto dado.
Algoritmo 2.11. Encontrando el máximo y mínimo en forma recursiva
70
