Complejidad de los algoritmos

Tamaño de problema

Ejemplo 1.

Es posible diseñar un algoritmo para jugar ajedrez que triunfe siempre: el algoritmo elige la siguiente tirada examinando todas las posibles secuencias de movimientos desde el tablero actual hasta uno donde sea claro el resultado y elige la tirada que le asegure el triunfo; el pequeño inconveniente de este algoritmo es que dicho espacio de búsqueda se ha estimado en 1000^40 tableros por lo que puede tardarse años en tomar una decisión

Se considera que si un problema tiene una solución que toma años en computar, dicha solución no existe.

Ejemplo 2.

Ordenar un conjunto de valores

Si el conjunto tiene 2 elementos es más fácil resolverlo que si tiene 20, análogamente un algoritmo tique resuelva el problema tardará más tiempo mientras más grande sea el conjunto y requerirá una cantidad de memoria mayor para almacenar los elementos del conjunto.

"En general la cantidad de recursos que consume un algoritmo para resolver un problema se incrementa conforme crece el tamaño del problema"

Dependiendo del problema en particular, uno o varios de sus parámetros serán elegidos como tamaño del problema.

Determinar el tamaño del problema es relativamente fácil realizando un análisis del problema si el problema ya ha sido comprendido.

Función complejidad

La función complejidad, f(n); donde n es el tamaño del problema, da una medida de la cantidad de recursos que un algoritmo necesitará al implantarse y ejecutarse en alguna computadora.

La cantidad de recursos que consume un algoritmo crece conforme el tamaño del problema se incrementa, la función complejidad es monótona creciente f(n) >= f(m) si n > m con respecto al tamaño del problema.

La memoria y el tiempo de procesador son los recursos sobre los cuales se concentra todo el interés en el análisis de un algoritmo, así pues se distinguen dos clases de función complejidad:

1. Función complejidad espacial. Mide la cantidad de memoria que necesitará un algoritmo para resolver un problema de tamaño n: fe(n)

2. Función complejidad temporal. indica la cantidad de tiempo que requiere un algorimo para resolver un problema de tamaño n; viene a ser una medida de la cantidad de instrucciones de CPU que requiere el algoritmo para resolver un problema de tamaño n: ft(n)


La cantidad de memoria que utiliza un algoritmo depende de la implementación, no obstante, es posible obtener una medida del espacio necesario con la sola inspección del algoritmo.

Para obtener esta cantidad es necesario sumar todas las celdas de memoria que utiliza. En general se requerirán dos tipos de celdas de memorias:

1. Celdas estáticas. Son las que se utilizan en todo el tiempo que dura la ejecución del programa

2. Celdas dinámicas. Se emplean sólo durante un momento de la ejecución, y por tanto pueden ser asignadas y devueltas conforme se ejecuta el algoritmo, el espacio de la pila utilizado por las llamadas re cursivas

El tiempo que emplea un algoritmo en ejecutarse refleja la cantidad de trabajo realizado, así, la complejidad temporal da una medida de la cantidad de tiempo que requeriá la implementación de un algoritmo para resolver el problema, por lo que se le puede determinar en forma experimental.

Para encontrar el valor de la función complejidad de un algoritmo A que se codifica un lenguaje de programación L; se compila utilizando el compilador C; se ejecuta en la máquina M y se alimenta con un conjunto de casos S. Se deberá de medir el tiempo que emplea para resolver los casos (análisis a posteriori).

Análisis Temporal

Medir la complejidad temporal de manera experimental presenta, entre otros, el inconveniente de que los resultados obtenidos dependen de:

• Las entradas proporcionadas
• La calidad del código generado por el compilador utilizado
• La máquina en que se hagan las pruebas

Cada operación requiere cierta cantidad constante de tiempo para ser ejecutada, por esta razón si se cuenta el número de operaciones realizadas por el algoritmo se obtiene una estimación del tiempo que le tomará resolver el problema.

Dado un algoritmo, se puede determinar que tipos de operaciones utiliza y cuantas veces las ejecuta para una entrada especifica (análisis a priori).

Para evitar que factores prácticos se reflejen en el cálculo de la función complejidad, el análisis temporal y el espacial a priori se realiza únicamente con base al algoritmo escrito en pseudocódigo.

Como el pseudocódigo no se puede ejecutar para medir la cantidad de tiempo que consume, la complejidad temporal no se expresará en unidades de tiempo, sino en términos de la cantidad de operaciones que realiza,

Análisis Espacial

Los casos en la función complejidad espacial, se pueden definir análogamente, considerando ahora el conjunto C(n); como el conjunto formado por el número de celdas de memoria utilizadas por el algoritmo para resolver cada instancia del problema.

Medición del tiempo de ejecución

Cantidad de instrucciones básicas (o elementales) que se ejecutan.

Ejemplo

1. Asignación de variables
2. Lectura o escritura de variables
3. Saltos (goto's) implícitos o explícitos
4. Operaciones aritméticas
5. Evaluación de condiciones
6. Llamada a sentencias simples
7. Llamas y retornos de función*

*Las funciones tienen un coso de tiempo que hay que considerar a parte

Medición de la memoria requerida

Cantidad de celdas de memoria (o elementales) que se requieren

Ejemplo

1. Variables del algoritmo
2. Numero de objetos instanciados requeridos
3. Tamaño de las estructuras de datos empleadas
4. Memoria de Entrada/Salida requerida
5. Tamaño de arreglo, matrices y otro tipo de memoria continua estática o dinámica empleada por el algoritmo