1.3 Complejidad

1.3.1 Tiempo de Ejecucion de un Algoritmo.
Como se mide el tiempo de ejecucion de un programa en funcion de N (numero de datos)?
Esta funcion se puede medir fisicamente calculandolo con un reloj o se puede calcular sobre el codigo, contando las instrucciones a ejecutar y multiplicandolo por el tiempo requerido por cada instruccion.

Ejemplo:
Sentencia 1

. Sentencia 2
. entonces
. . T(N)=t1+t2*N
En este ejemplo, siendo t1 el tiempo que lleve ejecutar la sentencia S1 y t2 el tiempo que lleve ejecutar la sentencia S2 un numero de n veces dentro del ciclo "for".

=Reglas Prácticas para calcular la complejidad de un algoritmo=
1.- Sentencia Sencilla: Se refiere a las sentencias de asignación, entrada o salida de datos siempre y cuando no trabajen sobre estructuras cuyo tamaño está relacionado con N(número de datos). Como requiere un tiempo constante de ejecución su complejidad es el orden 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 tomándose en cuenta el orden mas alto.
3.-Sentencia de Decisión (if): La condición suele ser de orden constante, osea O(1), sumando en la peor rama posible ya sea la del THEN o la de ELSE.
4.-Bucles (Ciclos): en los ciclos con contador explicito existen 2 casos y el tamaño N forme parte de los límites del ciclo o no.
4a) Contador Explicito
Caso 1 For (int i=0;;i++)
{S1;}
Entonces K*O(1)=O(1) Constante
Caso 2 For (int i=0;;i++)
{S1;}
Entonces N*O(1)=O(n) Lineal

4b) 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:
Ej. c=1;//Incremento
While (c1)
{
S1;
c=c/a
}
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.
NOTA: Procedimiento Recursivo: el que se manda llamar a si mismo un a y otra ves.
Ej. Función Factorial (no recursiva) Programa 9
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 asignacion O(1)
Return fact; //sentencia salida O(1)
}
Entonces: Complejidad Lineal O(n) por el ciclo for con numero de iteraciones igual a n

ORDENES DE COMPLEJIDAD
O(1) Constante Ideal
O(n) Lineal Eficiente
O(log n) Logaritmico Eficiente
O(n log n) Casi Lineal Eficiente
O(n^k) Polinomial Tratable
O(k^n) Exponencial Intratables
O(n!) Factorial Intratables