Complejidad

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 "