Lenguaje De Programacion

Técnica de la O grande para medir la eficiencia de los algoritmos

Una forma de determinar la eficiencia del tiempo de ejecución de un algoritmo es programarlo y medir el tiempo que lleva la versión en particular, en un computador especifico, para un conjunto seleccionado de entradas. Aunque es popular y útil, este enfoque tiene algunos problemas inherentes. Los tiempos de ejecución dependenno sólo del algoritmo base, sino también del conjunto de instrucciones del computador, de la calidad del compilador y de la destreza del programador. El programa también puede adaptarse para trabajar correctamente sobre el conjunto particular de entradas de prueba. Estas dependencias pueden ser muy notorias con un computador, un compilador, un programador o un conjunto de entradas de pruebadistinto. Para superar esos inconvenientes, los expertos en computación han adoptado la complejidad de tiempo asintótica como una medida fundamental del rendimiento de un algoritmo. El termino eficiencia se referid a esta medida y, en especial, a la complejidad de tiempo en el peor caso (en contraposición al promedio). Recuérdense del capítulo 1 las definiciones de (m (n)) y (R (An)). Laeficiencia o complejidad en el peor caso de un algoritmo es m n ) ) , o j l n ) para abreviar, si W n ) ) es la función de n que da el máximo, en todas las entradas de longitud n, del número de pasos dados por el algoritmo en esas entradas. En otras palabras, existe alguna constante c tal que para una n suficientemente grande, cfln) es una cota superior del número de pasos dados por el algoritmocon cualquier entrada de longitud n. En la aseveración de que d a eficiencia de un algoritmo dado es f(n)», existe la implicación de que la eficiencia también es (R (An)), de forma que f(n) es la función de crecimiento más lenta de n que acota el tiempo de ejecución en el peor caso por ambas. Sin embargo, este último requisito no es parte de la definición de (O (f(n)), y algunas veces no esposible asegurar que se tenga la cota de crecimiento superior más lenta. Esta definición de eficiencia ignora factores constantes en el tiempo de ejecución y existen varias razones prácticas para ello. Primero, dado que la mayoría de los algoritmos estén escritos en lenguajes de alto nivel, se deben describir en función de «pasos», los cuales emplean una cantidad constante de tiempo cuando se traducenal lenguaje de máquina de cualquier computador. Sin embargo, exactamente cuánto tiempo requiere un paso depende no sólo del paso mismo, sino del proceso de traducción y del conjunto de instrucciones de la máquina. Así, intentar tener más precisión que para decir que el tiempo de ejecución de un algoritmo es «del orden de A(n)», esto es, O (M(n)), podría empantanar al usuario en detalles demáquinas específicas y sólo sería aplicable a esas máquinas. Una segunda razón importante para tratar con la complejidad asintótica e ignorar factores constantes es que, más que estos factores, es la complejidad asintótica lo que determina para qué tomarlo de entradas puede usarse el algoritmo para producir soluciones en un computador. En el capítulo 1 se analizó con detalle este aspecto. Sin embargo,es necesario tener cautela acerca de la posibilidad de que para problemas muy importantes, como los de clasificación, se pueda considerar adecuado analizar los algoritmos con tal detalle que sean factibles ciertas proposiciones como «el algoritmo A debe ejecutarse con el doble de rapidez que el algoritmo B en un computador típico». Una segunda situación en la cual conviene desviarse de lanoción de eficiencia en el peor caso ocurre cuando se conoce la distribución esperada de las entradas a un algoritmo. En estas situaciones, el análisis del caso promedio puede ser mucho más significativo que el análisis del peor caso. Por ejemplo, en el capítulo previo se analizó el tiempo de ejecución promedio de la clasificación rápida en el supuesto de que todas las permutaciones del orden de...