|
Las estimaciones de tiempo dependen de cómo definamos un paso. Para que el análisis tenga sentido, debemos garantizar que el tiempo requerido para realizar un paso se encuentre acotado superiormente por una constante. Hay que mantenerse precavido en este terreno; por ejemplo, algunos análisis cuentan con que la suma de dos números se hace en un paso. Este supuesto puede no estar garantizado en ciertos contextos. 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).
==¿Qué es análisis de algoritmos?==
Es muy común que los estudiantes principiantes de ciencias de la computación comparen sus programas entre sí. También usted puede haber notado que es común que los programas de computadora se vean muy similares, especialmente los más simples. A menudo surge una pregunta interesante. Cuando dos programas resuelven el mismo problema pero se ven diferentes, ¿es un programa mejor que el otro?
Con el fin de responder esta pregunta, tenemos que recordar que hay una diferencia importante entre un programa y el algoritmo subyacente que el programa está representando. Como dijimos en el Capítulo 1, un algoritmo es una lista genérica, paso a paso, de instrucciones para resolver un problema. Es un método para resolver cualquier caso del problema de tal manera que dada una entrada particular, el algoritmo produzca el resultado deseado. Un programa, por otro lado, es un algoritmo que ha sido codificado en algún lenguaje de programación. Pueden existir muchos programas para el mismo algoritmo, dependiendo del programador y del lenguaje de programación que se esté utilizando.
Para explorar aún más esta diferencia, considere la función que se muestra en el ActiveCode 1. Esta función resuelve un problema familiar: calcular la suma de los primeros n enteros. El algoritmo utiliza la idea de una variable acumuladora que se inicializa en 0. La solución itera entonces a través de los n enteros, agregando cada uno a la variable acumuladora.
==Metodologías para el análisis de algoritmos==
La complejidad de un algoritmo estudia los recursos necesarios (tiempo y memoria) que requiere un algoritmo. El tiempo de ejecución de un algoritmo o es prioritario cuando se analiza un algoritmo. El tiempo de ejecución de un algoritmo o estructura de datos depende de varios factores relativos al hardware (procesador, reloj, memoria, disco, etc) y el software (sistema operativo, lenguaje, compilador, etc.).
== Véase también ==
| 