SoloCodigo

Programación General => Pascal => Mensaje iniciado por: Ocean Soul en Martes 13 de Septiembre de 2005, 21:59

Título: Analisis De Eficiencia De Algoritmos
Publicado por: Ocean Soul en Martes 13 de Septiembre de 2005, 21:59
Hola denuevo...
Les tengo una pregunta: Como calculo el tiempo exacto en funcion de n del siguiente algoritmo?

Function Rec1(n:integer):integer;
Begin
         if n<=1 then rec1:=1 else
         rec1:=rec1(n-1) + rec1(2*n);
end;

Gracias!!!
Título: Re: Analisis De Eficiencia De Algoritmos
Publicado por: Alpha_ en Sábado 24 de Septiembre de 2005, 23:07
Citar
Function Rec1(n:integer):integer;
Begin
         if n<=1 then rec1:=1 else
         rec1:=rec1(n-1) + rec1(2*n);
end;
A ver.. voy a aventurarme, siempre tuve dramas con esto.

condicion = 1 + acciones
acciones = 1 o accion de asignacion = max(1, asignacion)
asignacion = costo(rec1(n-1) + rec1(2n))

Acciones = max(1, costo(rec1(n-1) + rec1(2n)) = costo(rec1(n-1) + rec1(2n))
condicion = 1 + costo(rec1(n-1) + rec1(2n))

Y entonces, en los niveles de recursividad sería:
1: 1 + rec1(n-1) + rec(2n)
2: 1 + (1 + rec1) + rec(4n)
3: 1 + (1 + 1 + rec1) + rec(6n)
...

en definitiva, tendríamos, para n: n + rec1 + rec1(n^2)
...

...hmm no. Estoy olvidadísimo de esto. Algo de por acá está mal, pero lo dejo como para que tengas una base, a ver si lográs sacarlo. Tengo que revisar unas carpetas viejas.  :blink:
Título: Re: Analisis De Eficiencia De Algoritmos
Publicado por: fuhrer en Viernes 30 de Septiembre de 2005, 19:44
Hola que tal.

Viendo el código, podria decirse que el programa nunca terminaria, ya que en la instrucción

Código: Text
  1.  rec1:=rec1(n-1) + rec1(2*n);
  2.  

se decrementa n por un lado, pero por el otro se duplica n.

Asi que llendonos por el lado donde n se se duplica, tendremos que

Código: Text
  1. Rec1(2n)
  2. Rec1(4n)
  3. Rec1(8n)
  4.    .  .  .
  5. Rec1(2^k n)
  6.  

Pero como la condicion de paro es n <= 1 entonces k se ira al infinito y por lo tanto el programa no se detendria.

Ahora tendría que programar el código para ver que sucede, si es que aun no lo has hecho.

Hasta luego.
Título: Re: Analisis De Eficiencia De Algoritmos
Publicado por: Ocean Soul en Miércoles 5 de Octubre de 2005, 23:00
Gracias!!!!  :)