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 fisicsamente calulandola con un reloj o se puede calcular con el codigo contando las intrucciones a ejecutar y multiplicandoli por el tiempo requerido por cada intruccion.

ejemplo:

s1;

for(int i=0;i

s2;

entonces:

t(n)=t1+t2*2

en este ejemplo siento t1 el tiempo que yeve el ejecutar lacentencia s1 y t2 el tiepo que lleve ejecutar la sentencia 2 un numero n de veses dentro del siclo for.

=reglas practicas para calcular la omplejidad de un algoritmo=

1.-sentencia sencilla:se refiere alas sentencia de asigacion mostrada en la asalida de datos simpre yc cunado no trnaaje sobre estructuras cullo tamano esta relacionado con N. como requiere un tiempo constante de ejecucion su complejidad es del orden 1

2.-secuencia de sentencia: su complejidad esta dada por la suma de las complejidades individuales de acuerdo al tipo de sentencias tomandose en cuneta el orden mas alto.

3.-decision (if): la cindicion suele ser de orden constante O(1), sumando en la peor rama posible ya sea d la del then o l a del else

4.-bucles(ciclos): en los cilcos con contaddor explisito existen dos casos el tamana N forme parte de los limites del ciclo o no.ejemplo:

caso 1 for(int i=0;i

{s1;}

entonsesk*O(1)=O(1) constante

caso 2 for(int i=0;i

{s1;}

entonses  N*O(1)=O(1) lineal

no lineal(while)

en los cickos multiplicatios com el whiley el do while el inremento de la variable control no es nineal no que ase incrementar el orden de complejidad como en los ejemplos siguientes.

ejemplo:

c=1;

while(c

{

s1;

c=2*c;

}

entonses complejidad o(log N)

logaritmico

c=N;

while(c>1)

{

S1;

C=C/2;

}

COMPLEJIDAD LOG(log n)

5.-llamdas de procedimientos: la complejidad e llamar a un prosedoimiento esta dada por la cmplejidad del contididdo del proisedimeinto  en si , es desir su complejidad depende del tipo de intrucciones o sentencias que existan en el cuerpo del prodedimiento. en clonclucion la comliejidad dein prosedimineto tiende a complidarse si se trata de prosediminetos recursibos.

===========

=progrma#9=

===========

ej.funcion factorial(no recursiva)

int factorial(int n)//sentencia entrada O(1)

{

int fact=1;//sentencia asinacion O(1)

for(int i=n;i>0;i--)//ciclo contador explicita O(n)

fact=fact*1;//sentencia asignacion O(1)

return fact;//sentencia salida O(1)

}

entonces:complejidad linealO(n)por el ciclo for con numeros de interaccion igual a n.

ordenes de complejidad

O(1)constante           idela

O(n)lineal              eficente

O(log n)logaritmico     eficente

O(n log n)casi lineal   eficente

O(n*)polinomial         tratable

o(K^n)exponencial       intratables

o(n!)factorial          intratables