Apuntes N 1 Complejidad y Orden

APUNTES Nº1
COMPLEJIDAD Y ORDEN

Algoritmos y Estructuras de Datos

Irene Zuccar Parrini
2015

COMPLEJIDAD ALGORÍTMICA
Análisis de Algoritmos

Complejidad Algorítmica
Análisis de Algoritmos

Algoritmo:
Secuencia finita de instrucciones, que cumplen con lograr alguna tarea concreta. Cada una de las
instrucciones tiene un significado preciso, se ejecutan con una cantidad finita de esfuerzo y enun tiempo
finito, asegurando siempre al finalizar la obtención de una respuesta.

¿Qué es un “buen algoritmo”?:
Existen varios conceptos que definen a un algoritmo como bueno:
 
1. Modularidad.
2. Correctitud:
a) Resuelve el problema computacional para el cual fue diseñado.
b) Para cada entrada, produce la salida deseada.
c) Termina en un tiempo de ejecución finito.
3. Mantenibilidad.
4. Robustez:“Flexible a cambios” (en sus entradas).
5. Facilidad de uso.
6. Tiempo de programación.
7. Simplicidad.
8. Extensible (a otros problemas).
9. Confiabilidad.
3

Complejidad Algorítmica
Análisis de Algoritmos

Criterios para medir eficiencia de un algoritmo:
Existen dos criterios que miden la eficiencia de los algoritmos en términos del tiempo de
ejecución que posean: Criterio Empírico o a-posterioriy Criterio Analítico o a-priori.

4

Complejidad Algorítmica
Análisis de Algoritmos

Criterio Empírico o a-posteriori:
Este criterio funciona siguiendo los siguientes pasos:
 
1. Codificar los algoritmos.
2. Seleccionar los datos de prueba.
3. Ejecutar los programas con las diferentes entradas, midiendo el tiempo que toman en ejecutarse.
4. Graficar los tiempos: Curvas de Rendimiento.
TiempoEjemplo de un gráfico comparativo del tiempo que toman
dos programas que resuelven el mismo problema con
diferentes entradas (Curvas de Rendimiento)
Programa 2

Programa 1

Tamaño de la Entrada (n)
10

20

30

40

50

60

5

Complejidad Algorítmica
Análisis de Algoritmos

Criterio Empírico o a-posteriori: Desventajas
1. Depende del lenguaje de programación usado.
2. Depende de los datos de prueba.3. Dependen de la máquina.
4. Depende de la calidad del programa (programadores).
Conclusión: Es muy poco práctico.

6

Complejidad Algorítmica
Análisis de Algoritmos

Criterio Analítico o a priori:
• Determina matemáticamente cuántos recursos se necesitan para cada algoritmo.
• Esta tarea se denomina estudio de la complejidad: consiste en la obtención de una expresión matemática
que refleja elcomportamiento del algoritmo en función de los datos de entrada.
• La complejidad o eficiencia de un algoritmo debe ser estudiada con respecto a algún recurso crítico: el
tiempo de computación (cuánto tiempo toma ejecutar la implementación de un algoritmo), la cantidad de
espacio necesaria para almacenar los datos requeridos, la cantidad de procesadores necesarios, etc.
• En general se trabaja conla complejidad de tiempo.
• La complejidad de un algoritmo, es una función del tamaño de la entrada(s) al algoritmo.

Complejidad Algorítmica
Análisis de Algoritmos

Criterio Analítico o a priori:
• Formalmente, el tamaño de un dato se refiere a la cantidad de bits necesarios para su almacenamiento.
• No obstante, esa noción depende de la implementación del algoritmo, por lo que no es adecuadapara una
evaluación teórica.
• En consecuencia, se considera simplemente que el tamaño de la entrada(s) es un número natural que
indica la cantidad de elementos de un objeto, por ejemplo, la cantidad de elementos de un arreglo o bien
el número de nodos y de aristas de un grafo.

Complejidad Algorítmica
Análisis de Algoritmos

Criterio Analítico o a priori:
• ¿Qué ocurre con aquellas instancias deentrada que poseen el mismo tamaño? El tiempo que tarda un
algoritmo en resolverlas puede variar mucho….
• No tiene sentido evaluar la eficiencia de un algoritmo solo en función del tamaño de la instancia, pues el
algoritmo debe funcionar correctamente para todas las instancias.
• En el mejor caso, el tiempo requerido suele ser poco…. Pero es poco probable que ocurra. (Ejemplo?)
• También puede...