Unidad I- Complejidad

1.3 Complejidad

1.3.1 Tiempo de ejecución de un algoritmo

Como se mide el tiempo de ejecución de un programa en función de N numero de datos?
Esta función se puede medir físicamente calculándola con un reloj o se puede calcular sobre el código contando las instrucciones a ejecutar y multiplicándolo por el tiempo requerido por cada instrucción.


En este ejemplo siendo t1 el tiempo que lleva ejecutar la sentencia s1 y t2 el tiempo que lleva ejecutar la sentencia s2 un numero n de veces dentro del ciclo for.

Reglas practicas para calcular la complejidad de un algoritmo

1. Sentencia sencilla: Se refiere a las sentencias de asignación entrada salida de datos , siempre y cuando no trabajen sobre estructuras cuyo tamaño esta relacionado con N. Como requieren tiempo constante de ejecución su complejidad es del orden constante (O(1)).
2. Secuencia de sentencias: Su complejidad esta dada por la suma de las complejidades individuales de acuerdo al tipo de sentencias que se trate tomandose en cuenta el orden mas alto.
3. Decisión (if): La condición suele ser de orden constante O(1) , sumando en la peor rama posible ya sea la del then o del else.
4. Bucles (ciclos): En los ciclos con contador explicito existen dos casos que el tamaño N forme parte de los limites del ciclo o no.


b) Evolución de variable de control No Lineal (while): En los ciclos multiplicativos como el while y el do while el incremento o decremento de la variable de control no es lineal lo que hace incrementar el orden de complejidad como en los ejemplos siguientes:
ejemplo 1:
c=1;
while (c1)
{
S1;
C=c/2;
}
Entonces complejidad logarítmica O(log n)

5. Llamadas a procedimientos: La complejidad de llamar a un procedimiento esta dada por la complejidad del contenido del procedimiento en si, es decir, su complejidad depende del tipo de instrucciones o sentencias que existan en el cuerpo del procedimiento. En conclusión la complejidad de un procedimiento tiende a complicarse si se trata de procedimientos recursivos.
Ejemplo: función factorial (no recursiva)
Int factorial (int n) //sentencia Entrada O(1)
{
Int fact=1; //sentencia asignación O(1)
For(int i=n;i>0;i--) //ciclo contador explicito O(n)
Fact=fact*i; //sentencia asignación O(1)
Return fact; //sentencia salida O(1)
}
Entonces: Complejidad Lineal O(n) por el ciclo for con numero de interacciones iguales a n.

Ordenes de complejidad
O(1) Constante Ideal
O(n) Lineal Eficiente
O(log n) Logarítmico Eficiente
O(n log n) Casi Lineal Eficiente
O(n^k) Polinomial Tratable
O(K^n) Exponencial Intratables
O(n!) Factorial Intratables

1.3.2. Complejidad en el espacio

- Complejidad Espacial: Es la memoria que utiliza un programa para su ejecución. Lo que implica que la eficiencia en memoria de un algoritmo lo indica la cantidad de espacio requerido para ejecutarlo es decir, el espacio en memoria que ocupan todas las variables propias del algoritmo.
Ejemplo: Algoritmo de búsqueda en arboles.
Función busqueda_arboles(problema)
Devuelve solución/fallo
Inicio búsqueda de árbol con estado inicial
Ciclo hacer
Si no hay cantidades para expandir
Entonces devolver fallo
En otro caso escoger nodo para expandir.
Si el nodo es el objetivo
Entonces devolver solución
En otro caso expandir nodo
Resultados obtenidos
Depth Nodes Time Memory
0 1 1 millisecond 100 bytes
2 111 .1 seconds 11 kilobytes
4 11,111 11 seconds 1 megabytes
6 10^6 18 minutes 111 megabytes
8 10^8 31 hours 11 gigabytes
10 10^10 128 days 1 terabyte
12 10^12 35 years 111 terabytes

Notas:
Factor de ramificación 10 nodos sucesores p/cada uno como máximo
Profundidad del árbol infinita