Programación General > Pascal

 Analisis De Eficiencia De Algoritmos

(1/1)

Ocean Soul:
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!!!

Alpha_:

--- Citar ---Function Rec1(n:integer):integer;
Begin
         if n<=1 then rec1:=1 else
         rec1:=rec1(n-1) + rec1(2*n);
end;
--- Fin de la cita ---
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:

fuhrer:
Hola que tal.

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


--- Código: Text --- rec1:=rec1(n-1) + rec1(2*n); 
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 ---Rec1(2n)Rec1(4n)Rec1(8n)   .  .  .Rec1(2^k n) 
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.

Ocean Soul:
Gracias!!!!  :)

Navegación

[0] Índice de Mensajes