Algoritmos

La importancia de los algoritmos.
Introducción.
El primer paso hacia una comprensión de por qué el estudio y conocimiento de algoritmos es tan importante es definir y entender exactamente que es un algoritmo. Conforme el popular libro de texto algoritmos Introduction to Algorithms (Second Edition by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein), “un algoritmo escualquier procedimiento computacional bien definido que toma un valor, o conjunto de valores, como entrada y produce algún valor, o conjunto de valores como salida”. En otras palabras, los algoritmos son como instructivos para llevar a cabo una tarea bien definida. Así, un pedazo de código que calcula los términos de la secuencia Fibonacci es una implementación de un algoritmo particular. Incluso unasimple función para sumar dos números es un algoritmo en un sentido, aunque sea uno simple.
Algunos algoritmos, como aquellos que calculan las secuencias Fibonacci, son intuitivos y pueden ser innatamente integrados en nuestro pensamiento lógico y nuestras habilidades para resolver problemas. Sin embargo, para la mayoría de nosotros, es mejor estudiar los algoritmos complejos y así poder usarloscomo bloques de construcción para una más eficiente resolución de problemas lógicos en el futuro. En realidad, es posible que se sorprenda solo al saber como muchos algoritmos complejos son usados por personas cada día cuando ellos checan su e-mail o su lista de música en sus computadoras. Este artículo introducirá algunas ideas básicas relacionadas con el análisis de algoritmos, y después pondráestas en práctica con unos pocos ejemplos ilustrando porque es tan importante saber acerca de algoritmos.
Análisis de tiempo de ejecución.
Uno de los aspectos más importantes de un algoritmo es que tan rápido es este. Muchas veces es fácil hacer un algoritmo para resolver un problema, pero si el algoritmo es lento, es hora de volver al pizarrón. Ya que la velocidad exacta de un algoritmo dependede donde el algoritmo sea ejecutado, así como los detalles exactos de su implementación, los científicos en computación típicamente hablan del tiempo de ejecución relativo al tamaño de la entrada. Por ejemplo, si la entrada consiste en N enteros, un algoritmo podría tener un tiempo de ejecución proporcional a N2, representado como ON2. Esto significa que si tú ejecutas una implementación de estealgoritmo en tu computadora con una entrada de tamaño N, se tomará C*N2 segundos, donde C es alguna constante que no cambia con el tamaño de la entrada.
Sin embargo, el tiempo de ejecución de muchos algoritmos complejos puede variar debido a otros factores que no sean el tamaño de la entrada. Por ejemplo, un algoritmo de ordenación puede ejecutarse mucho más rápido cuando le damos un conjunto deenteros que ya esta ordenado que cuando le damos el mismo conjunto de enteros con un orden al azar. A consecuencia, a menudo escucharas personas hablar acerca de el tiempo de ejecución en el peor de los casos (worst-case runtime), o el tiempo de ejecución promedio de los casos (average-case runtime). El tiempo de ejecución en el peor de los casos (worst-case runtime) es el tiempo que tomaría elalgoritmo en ejecutarse si se le da la más insidiosa de todas las posibles entradas. El tiempo de ejecución promedio de los casos (average-case runtime) es el tiempo promedio que se tomaría el algoritmo en ejecutarse si le damos todas las posibles entradas. De los dos, el worst-case runtime es más fácil de razonar, y por lo tanto es más frecuentemente usado como un punto de referencia para unalgoritmo dado. El proceso para determinar el worst-case runtime y el average-case runtime para un algoritmo dado puede ser difícil, ya que es usualmente imposible ejecutar un algoritmo con todas las entradas posibles. Existen muchos recursos buenos en línea que pueden ayudarte en la estimación de estos valores.
Tiempo aproximado de terminación para algoritmos con N=100
Complejidad | Tiempo de...