Apunte De Nociones De Análisis De Complejidad De Algoritmos

Algoritmos y Programación II - 7541

curso Calvo

Complejidad algorítmica: Al desarrollar un algoritmo para resolver un problema, una vez que hemos verificado que cumple sus objetivos, es decir, que es eficaz para aquello para lo que lo diseñamos, y a veces antes de la etapa de codificación, por lo general nos preguntamos por otras cuestiones también importantes: ¿cuánto tardará? ¿hará sutrabajo en menos tiempo que algún otro? las estructuras en donde se almacenan los datos ¿ocuparán demasiado espacio? ¿puedo encontrar otro algoritmo que haga lo mismo en un tiempo menor? ¿puedo encontrar otro que use menos espacio de memoria? Estas preguntas se refieren a dos recursos básicos que utilizará el algoritmo cuando, ya codificado, se ejecute: el tiempo insumido en la ejecución y el espacio(de memoria) utilizado. Qué es la eficiencia de un algoritmo: El consumo de recursos hace referencia a la eficiencia. Se dice que un algoritmo es más eficiente, si utiliza menos recursos que ese otro. La eficiencia de un programa se determina básicamente estudiando el consumo de: -tiempo (de ejecución) -espacio (de memoria) La eficiencia en el uso del recurso tiempo se estudia como análisis de“complejidad temporal” o “coste temporal”; estudia el tiempo necesario para ejecutar un algoritmo. El análisis de la “complejidad espacial” se ocupa de la cantidad de espacio de memoria (estática + dinámica) necesaria para ejecutar un algoritmo. En particular, en este apunte, nos ocuparemos del consumo de tiempo. El estudio del tiempo consumido por un algoritmo pueden ser realizado “a posteriori”, sise mide el tiempo real de ejecución para determinados valores de entrada y en determinado procesador, o “a priori”, si de manera teórica se analiza una función relacionada con el tiempo de ejecución de ese algoritmo. Tamaño de un problema ¿Cómo analizar el consumo de tiempo de un algoritmo? Al trabajar con el cálculo del consumo de tiempo o coste temporal por lo general se hace referencia altamaño de la entrada del problema, o tamaño del problema. ¿De qué se trata? La idea es sencilla. Por lo general en los problemas podemos determinar al menos un elemento cuyo tamaño o valor influya sobre el tiempo de ejecución del algoritmo. Ejemplo: Si estamos haciendo una búsqueda secuencial en un vector, el tiempo dependerá de la cantidad de elementos del vector. Es decir, existirá, por supuesto, laposibilidad de encontrar el dato al primer intento, pero “en general”, el tiempo depende del tamaño del vector.
1

Algoritmos y Programación II - 7541

curso Calvo

Si estamos calculando el factorial de un número, el valor del mismo número está en relación directa con el tiempo de ejecución del algoritmo. Si queremos obtener el valor del elemento de cierta posición en la sucesión deFibonacci, esa posición corresponde al tamaño del problema, porque determinará el tiempo de ejecución del algoritmo. Este “tamaño del problema” o “tamaño de la entrada”, como vemos, depende de la naturaleza del problema, y está dado por aquel o aquellos elementos que produzcan, al crecer, un aumento de tiempo de ejecución. El principio de invarianza o cómo ignorar algunos elementos: Como sabemos, eltiempo de ejecución de un algoritmo codificado (programa) para un cierto tamaño de entrada al que podemos representar como N, depende, entre otros, de los siguientes factores: La calidad del código objeto generado por el compilador. Las características de las instrucciones de máquina empleadas en la ejecución del programa. La velocidad del microprocesador El lenguaje usado en la codificación etc…. Sinembargo, al analizar de manera teórica la complejidad temporal, haremos abstracción (léase “decidiremos ignorar”) de estos elementos. Esto significa que decidimos no considerar las diferencias de tiempo provenientes de características como las mencionadas antes. Esto se indica mediante el principio de invarianza. Principio de invarianza: Dado un algoritmo y dos implementaciones I1 e I2, que...