Tiempo de ejecucion de un algoritmo
Cómo se mide el tiempo de ejecución de un programa en función de N-->(número 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.
==Reglas practicas para calcular la complejidad de un algoritmo==
1.-Sentencia Sencilla
Asignacion, E/O de datos
Se refiere a las sentencias de asignación de entrada y salida de datos siempre y cuando
no trabajen sobre estructuras cuyo tamanio esta relacionado con N. Como requiere un
tiempo contanste de ejecución su complejidad es el del orden Constante--> O(1)
2.- Sentencia de Sentencias: Suma de complejidad
Su complejidad esta dada por la suma de complejidades individuales de acuerdo al tipo de
sentencias que se trata tomandose encuenta el orden mas alto.
3.- Decisión (if): La condicion 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 o contadores Explicitos, existen dos casos el tamanio N forme parte de los limites del ciclo o no.
Ejemplo
a)contador explicito-->
for (int i=0;i {s1}
entonces k* O(1)=O(1)
for (int i=0;i {s1}
entoncesN*O(1)=O(n)Lineas
b)Evolucion de variables de control
No lineal(While)-->
En los ciclos multiplicativos como el while y el do while, el incremento o el decremento de la
variable e control no es lineal, lo que hace incrementar el orden de complejidad como en los
ejemplos siguientes
==EJEMPLO incremento==
c=1;
while (c
{
s1;
c=2*c;
}
Entonces la complejidad logaritmica O(log n)
==EJEMPLO decremento==
c=N
while (c>1)
{
s1;
c=c/2;
}
Complejidad logaritmica O(log n)
5.- Llamadas de Procedimientos:
La complejidad de llamar a un procedimiento esta dada por la complejidad del contenido en 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 tiene a complicarse si se trata de procedimientos recursivos(llamandose a si mismo).
==EJEMPLO==
Funcion factorial (no recursiva) (Iterativo<--ciclos)
int factorial(int n)/*Sentencia entrada O(1)*/
{
int fact=1;/*sentencia de asignacion O(1)*/
for (int i=n;1>0,i--)/*Ciclo contador explicito O(n)*/
fact=fact*1;/*Sentencia de asignacion O(1)*/
return fact;/*Sentencia de salida O(1)*/
}
entonces: Complejidad lineal O(n) po el ciclo for con numero de iteraciones iguales a n.
_____________________________________________________________________________________________
==Ordenes de complejidad==
O(1) Constante Ideal
O(n) Lineal Eficiente
O(log n) Logaritmico "
O(n log n) Casi lineal "
O(n^k) Polinomial Tratable
O(k^n) Exponencial Intratables
O(n!) Factorial "
