Análisis de algoritmos

A continuación, se presenta una explicación intuitiva utilizando el ejemplo del algoritmo de búsqueda para luego profundizar en forma más teórica.

El más sencillo es la búsqueda secuencial pero si el conjunto de elementos se encuentran ordenados (según su clave) dentro del vector se podría aplicar la búsqueda binaria.

De este ejemplo se pueden sacar varias conclusiones.

[3]​ En la Figura 2 se muestra dichos casos de manera gráfica.

Cuando no se especifica lo contrario, la función que describe el rendimiento de un algoritmo suele este caso, dado que este caso garantiza que el algoritmo no tardará mayor cantidad de tiempo, es decir acota superiormente la cantidad de pasos.

Por ejemplo, la búsqueda binaria decimos que se ejecuta en una cantidad de pasos proporcional a un logaritmo, en

No obstante, la eficiencia de dos implementaciones "razonables" cualesquiera de un algoritmo dado están relacionadas por una constante multiplicativa llamada constante oculta.

En otras palabras, para un tamaño de entrada dado n mayor que algún

Este concepto se expresa con frecuencia utilizando la notación O Grande, que brinda una forma conveniente de expresar el peor de los casos para un algoritmo dado.

Por ejemplo, el ordenamiento por inserción crece cuadráticamente a medida que aumenta su tamaño de entrada, entonces se puede decir que este tipo de ordenamiento es del orden de n cuadrado, en notación O Grande sería:

Otro tipo de funciones que pueden ser utilizadas para acotar un algoritmo son las mostradas en la Figura 3.

elementos, y podemos garantizar que una única búsqueda binaria puede realizarse en un tiempo unitario, entonces se requieren, como mucho,

Las medidas exactas de eficiencia son útiles para quienes verdaderamente implementan y usan algoritmos porque tienen más precisión y, así, les permite saber cuánto tiempo pueden suponer que tomará la ejecución.

Para algunas personas, como los desarrolladores de videojuegos, una constante oculta puede significar la diferencia entre éxito y fracaso.

Si, por ejemplo, los números involucrados en la computación pueden ser arbitrariamente grandes, dejamos de poder asumir que la adición requiere un tiempo constante (usando papel y lápiz, compara el tiempo que necesitas para sumar dos enteros de 2 dígitos cada uno y el necesario para hacerlo con dos enteros pero de 1000 dígitos cada uno).

Figura 1: En la figura se muestra la comparación de pasos realizados por los algoritmos de búsqueda lineal y la búsqueda binaria , representados en magenta y cian, respectivamente. En el ejemplo, ambos algoritmos se utilizan para buscar la entrada "Morin, Arthur" en una lista ordenada de 33 nombres. Como la búsqueda lineal ignora el orden de la lista toma 28 pasos para encontrar la entrada, mientras que, la búsqueda binaria lo hace en 5 pasos dado que aprovecha el orden de las entradas.
Figura 2 : Representación gráfica de los tres casos analizados dentro de la complejidad temporal de un algoritmo.
Figura 3 : Gráfico que muestra las funciones comúnmente utilizadas en el análisis de algoritmos representando el número de operaciones N versus el tamaño de entrada n .