Fundamentos de la Eficiencia Algorítmica: Medición y Notación Asintótica
Existen varias formas de resolver un problema.
¿Cómo escogemos entre ellos? Generalmente hay dos metas en el diseño de programas computacionales:
· El diseño de un algoritmo que sea fácil de entender, codificar y
depurar (Ingeniería de Software)
.
.
· El diseño de un algoritmo que haga uso eficiente de los recursos de la computadora (Análisis y Diseño de algoritmos).
El análisis de algoritmos nos permite medir la dificultad de un problema y evaluar la eficiencia de un algoritmo.
No se puede medir el tiempo en segundos porque no existe un computador estándar de referencia, en su lugar medimos el número de operaciones básicas o elementales
Las operaciones básicas son las que realiza el computador en tiempo acotado por una constante, por ejemplo:
• Operaciones aritméticas básicas
•Asignaciones de tipos predefinidos
•Saltos (llamadas a funciones, procedimientos y retorno)
•Comparaciones lógicas
•Acceso a estructuras indexadas básicas (vectores y matrices)
Es posible realizar el estudio de la complejidad de un algoritmo sólo en base a un conjunto reducido de sentencias, por ejemplo, las que más influyen en el tiempo de ejecución.
Para medir el tiempo de ejecución de un algoritmo existen varios métodos.
Algunos de ellos son:
A) Benchmarking
La técnica de benchmark considera una colección de entradas típicas representativas de una carga de trabajo para un programa.
B) Profiling
Consiste en asociar a cada instrucción de un programa un número que representa la fracción del tiempo total tomada para ejecutar esa instrucción particular. Una de las técnicas más conocidas (e informal) es la Regla 90-10, que afirma que el 90% del tiempo de ejecución se invierte en el 10% del código.
C) Análisis
Consiste en agrupar las entradas de acuerdo a su tamaño, y estimar el tiempo de ejecución del programa en entradas de ese tamaño, T(n). Esta es la técnica que se estudiará en el curso.
De este modo, el tiempo de ejecución puede ser definido como una función de la entrada.
Denotaremos T(n) como el tiempo de ejecución de un algoritmo para una entrada de tamaño n.
Denotaremos T(n) como el tiempo de ejecución de un algoritmo para una entrada de tamaño n.
El interés principal del análisis de algoritmos radica en saber cómo crece el tiempo de ejecución, cuando el tamaño de la entrada crece. Esto es la eficiencia asintótica del algoritmo. Se denomina “asintótica” porque analiza el comportamiento de las funciones en el límite, es decir, su tasa de crecimiento.
La notación asintótica se describe por medio de una función cuyo dominio es los números naturales (N ) estimado a partir de tiempo de ejecución o de espacio de memoria de algoritmos en base a la longitud de la entrada. Se consideran las funciones asintóticamente no negativas.
La notación asintótica captura el comportamiento de la función para valores grandes de N.
Las notaciones no son dependientes de los tres casos anteriormente vistos, es por eso que una notación que determine el peor caso puede estar presente en una o en todas las situaciones.