Unidad 1. Complejidad de algoritmos

Apuntes

Unidad 1. Complejidad de algoritmos Análisis de algoritmos Dra. Blanca Esthela Solís Recéndez 1 UNIDAD 1. Complejidad de algoritmos 1.1 Introducción Un algoritmo es un procedimiento computacional bien definido que toma un valor, o conjunto de valores, como entrada y produce un valor, o conjunto de valores, como salida. Propiedades típicas de un algoritmo : • Entrada: el algoritmo recibe una entrada. • Salida: el algoritmo produce una salida. • Precisión: los pasos están indicados de forma precisa. • Determinismo: los resultados intermedios de cada paso de ejecución son únicos y son determinados sólo por las entradas y los resultados de los pasos anteriores. • Finitez: el algoritmo termina; así que, termina después de que un número finito de instrucciones han sido ejecutadas. • Completez: la salida producida por el algoritmo es correcta. • Generalidad: el algoritmo se aplica a un conjunto de entradas. El análisis de algoritmos consiste en predecir la cantidad de recursos (tiempo, memoria, comunicación) que un algoritmo requerirá para cualquier entrada. El tiempo de corrida es el número de “pasos” ejecutados. Este “paso” debe definirse de manera que ...