1.3.1 Tiempo de ejecución de un algoritmo.

¿Cómo 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 calculando con un reloj o se puede calcular sobre el código contando las instrucciones o ejecutar y multiplicándolo por el tiempo requerido por cada instrucción.

Reglas practicas para calcular la complejidad de un algoritmo
1.- Sentencia sencilla: se requiere la sentencia de asignación, entrada o salida de datos siempre y cuando no trabajen sobre estructuras cuyo tamaño esta relacionado con N (número de datos). Como requiere un tiempo constante de ejecución, su complejidad s de orden O (1).
2.- Secuencia de sentencias: su complejidad esta dada por la suma de las complejidades individuales de acuerdo al tipo de sentencia que se trate, tomándose n cuenta el orden más alto.
3.- Decisión (if): la solución sele ser de orden constante O (1), sumando en la peor rama posible ya sea la de then o else.
4.-Bucles (ciclos): a) en los ciclos con contador explicito existen dos casos que el tamaño N forme parte e los limites del ciclo o no.
Ej. Caso 1:
For (int i=0; i{S1;}
Entonces K*0=O (1) constante
Caso 2:
For (int i=0; i>N; i++)
{S1;}
Entonces N*O (1)=O(n) Lineal

b) Evolución de variable DE CONTROL NO LINEAL (WHILE)
En los ciclos multiplicativos como while y do while el incremento o decremento de la variable de control no es lineal, lo que hace incrementar el orden de complejidad como en:
Ejemplo:
C=1; //incremento
While(c{
S1;
C=2*C;
}
Entonces complejidad O (log n) Logarítmica.
Ejemplo:
C=n; //decremento
While(c>1)
{S1;
C=c/2;
}
Complejidad 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 procedimiento recursivos.
Ejemplo:
Función factorial (no recursiva)
int factorial (int n)//sentencia entrada O (1)
{
int fact=1; //sentencia asignación O(n)
for (int i=0; 1>O; i--)// ciclo contador explicito O(n)
fact=fact*i; //sentencia de asignación O (1)
Return fact; //sentencia salida O (1)
}
Entonces: complejidad lineal O(n) por el ciclo for o numero de iteraciones igual a n.
ORDENES DE COMPLEJIDAD
O (1) Constante ideal
O(n) Lineal eficiente
O (log n) Logarítmico eficiente
O(n log n) casi logarítmico eficiente
O(n^k) polinomial tratable
O (K^n) Exponencial intratable
O (n!) Factorial ingtratable