Page 72 - INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

INTRODUCCIÓN AL ANÁLISIS DE ALGORITMOS

Sin embargo, encontrar el elemento que ocupe la posición central del conjunto de datos que se va
a analizar es una tarea difícil, ya que existen 1/n posibilidades de lograrlo. Además, el rendimiento
medio del método es aproximadamente (2*ln 2) inferior al caso óptimo, por lo que Hoare, el autor del
método, propone como solución que el elemento X se seleccione arbitrariamente o bien entre una
muestra relativamente pequeña de elemento del arreglo.

Se puede afirmar que el tiempo promedio de ejecución del algoritmo es proporcional a O (n* log n).
En el peor de los casos, es proporcional a O (n ).
2

BúSqueda SecueNcIal

La búsqueda secuencial consiste en revisar elemento tras elemento hasta encontrar el dato indaga-
do o hasta llegar al final del conjunto de datos disponible. Normalmente cuando una función de bús-
queda concluye con éxito, interesa conocer en qué posición fue hallado el elemento que se estaba
buscando. Esta idea se puede generalizar para todos los métodos de búsqueda.
A continuación, en el algoritmo 2.7 se presenta el método de búsqueda secuencial en arreglos des-
ordenados en código C:

Algoritmo 2.7. Método de búsqueda secuencial

Si hubiera dos o más ocurrencias del mismo valor, se encuentra la primera de ellas. Sin embargo, es
posible modificar el algoritmo para obtener todas las ocurrencias de datos buscados.
En el algoritmo 2.8 se presenta una variante de este algoritmo, pero utilizando recursividad en lugar
de interactividad.

66