SoloCodigo

Programación General => Pascal => Mensaje iniciado por: Ocean Soul en Jueves 8 de Septiembre de 2005, 23:33

Título: Analisis De Eficiencia De Algoritmos
Publicado por: Ocean Soul en Jueves 8 de Septiembre de 2005, 23:33
Saludos, tengo un problema: No me sale este ejercicio: Expresar en funcion de n el tiempo de ejcucion exacto del sgt codigo;

Procedure Misterio(n:integer);
Var
     i,k,j:integer;

Begin
       For I:=1 to n-1 do
            For J:=1 to n do
                 for K:=1 to j do
                         {alguna proposicion que requiera tiempo de ejecucion = 5}
end;

Gracias de antemano.
Título: Re: Analisis De Eficiencia De Algoritmos
Publicado por: Amilius en Viernes 9 de Septiembre de 2005, 00:53
Fácil, como son iteracciones multiplicas.

para I: n-1

para J: n

para K: (1+n)/2 //vamos que esto lo puede hacer un niño de 8 años  :D

para el proceso interno: 5

Multiplicas todo y con algo de álgebra despejas n.

=(n-1)*n*(1+n)/2*5
Título: Re: Analisis De Eficiencia De Algoritmos
Publicado por: Ocean Soul en Viernes 9 de Septiembre de 2005, 01:30
Bueno estoi aprendiendo... <_<

Como sea: Estoy de acuerdo que
para I: n-1
para J: n


Pero... Por qué dices que: para K: (1+n)/2 ??? (Me explicarias claramente?) :unsure:

Gracias denuevo.
Título: Re: Analisis De Eficiencia De Algoritmos
Publicado por: Lastent en Lunes 12 de Septiembre de 2005, 03:28
Si porfavor explica porque para K usas (1+n)/2
Título: Re: Analisis De Eficiencia De Algoritmos
Publicado por: Amilius en Martes 13 de Septiembre de 2005, 05:16
:huh: ¿Cuál es el PROMEDIO EXACTO de ciclos de k? si estos ciclos van en serie aritmética de 1 a n: pues (1+n)/2.

La suma total de TODOS los ciclos que realiza k es (1+n)/2*n  (una simple serie aritmética, fácil de demostrar).  Como QUEREMOS sacar el promedio dividimos la SUMA TOTAL entre n y queda (1+n)/2  ;)