Complejidad de Algoritmos: Tiempo de Ejecución y Clasificación
Enviado por Programa Chuletas y clasificado en Informática y Telecomunicaciones
Escrito el en 
español con un tamaño de 2,72 KB
Complejidad de Algoritmos
Tiempo de Ejecución
La complejidad de un algoritmo describe el tiempo de ejecución de un programa en base a n datos de entrada. Se expresa en términos de T(n), la función de complejidad.
- El tiempo de ejecución de una sentencia simple es T(1).
- Para sentencias de bifurcación (if, case), la complejidad es T(1).
- Para bucles (for, repeat, while) independientes, la complejidad es T(n).
- Para bucles anidados, la complejidad es T(nm), donde m es el número de bucles anidados.
Notación O
El tiempo de ejecución se expresa con la notación O, que ignora factores constantes como:
- El número medio de instrucciones máquina generadas por un compilador.
- El número medio de instrucciones por máquina por segundo ejecutadas por una computadora.
El tiempo de ejecución suele ser proporcional a N, el número de datos a tratar.
Clasificación de Problemas
Los problemas matemáticos se dividen en:
- Indecidibles: No se pueden resolver con un algoritmo.
- Decidibles: Tienen al menos un algoritmo para su cómputo.
- Intratables: No es factible obtener su solución.
- Tratables: Existe al menos un algoritmo que los resuelve en tiempo razonable.
El tiempo de ejecución T(N) se puede medir o calcular. En programas reales, T(N) varía según los datos, definiendo un rango: Tmin(N) <= T(N) <= Tmax(N) (caso mejor, caso peor y caso promedio).
Órdenes de Complejidad
1: Tiempo constante. La mayoría de las instrucciones se ejecutan una vez o muy pocas.
logN: Tiempo logarítmico. El programa es más lento al crecer N, pero es inapreciable.
N: Tiempo lineal. Si N se duplica, el tiempo se duplica.
N·logN: Común en algoritmos como Quick Sort. Si N se duplica, el tiempo es ligeramente mayor al doble.
N2: Tiempo cuadrático. Si N se duplica, el tiempo se cuadruplica.
N3: Tiempo cúbico. Si N se duplica, el tiempo se multiplica por ocho.
2N: Tiempo exponencial. Poco útiles en la práctica. Si N se duplica, el tiempo se eleva al cuadrado.
Memoria
La memoria utilizada por un programa se divide en:
- Estática: Suma de la memoria ocupada por las variables declaradas.
- Dinámica: Depende de la ejecución del algoritmo.