Complejidad de

los Algoritmos

Francisco Farren G.

Complejidad

Cantidad de recursos – tiempo y espacio – que

un algoritmo necesita para realizar sus

operaciones.

Tiempo

Aproximación del número de operaciones (pasos)

que el algoritmo desempeña.

Tiempo

Calcular el tiempo en que se ejecuta el algoritmo

no es conveniente, ya que depende de factores

como el hardware y software subjascente

Espacio

Almacenamiento requerido por el algoritmo para

realizar sus operaciones o para soportar la

entrada y salida de datos.

Datos de entrada

El tamaño, forma y orden de los datos de entrada,

son factores que se consideran al definir los

casos de análisis de un algoritmo.

Casos a considerar

Se consideran los casos extremos – mejor y peor

– y el caso promedio.

Peor Caso

Refleja el mayor tiempo que puede demorar

el algoritmo.

Caso promedio

Busca expresar el comportamiento de un

algoritmo frente a datos de entrada TIPICOS o

ALEATORIOS.

Complejidad de tiempo

Función que cuantifica la cantidad de tiempo que

un algoritmo requiere segun el el tamaño de los

datos de entrada.

Comportamiento Asintótico

Se analiza el desempeño de un algoritmo

forzando el tamaño del problema hacia infinito.

Notación Asintótica

Caracteriza el comportamiento de funciones

según su tasa de crecimiento.

Órdenes de Complejidad

Notación Big-O:

O(1) Complejidad constante

O(n2) Complejidad cuadrática

O(log n) Complejidad logarítmica

O(n) Complejidad lineal

O(n log n) Complejidad casi-lineal

O(nb) Complejidad polinómica

O(bn) Complejidad exponencial

O(n!) Complejidad factorial