• Viernes 29 de Marzo de 2024, 01:21

Autor Tema:  Analisis De Eficiencia De Algoritmos  (Leído 1478 veces)

Ocean Soul

  • Miembro activo
  • **
  • Mensajes: 38
    • Ver Perfil
Analisis De Eficiencia De Algoritmos
« en: Martes 13 de Septiembre de 2005, 21:59 »
0
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_

  • Miembro activo
  • **
  • Mensajes: 72
    • Ver Perfil
Re: Analisis De Eficiencia De Algoritmos
« Respuesta #1 en: Sábado 24 de Septiembre de 2005, 23:07 »
0
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:
Alpha
http]

fuhrer

  • Miembro MUY activo
  • ***
  • Mensajes: 329
  • Nacionalidad: mx
    • Ver Perfil
    • http://admin.busquenoseninternet.com
Re: Analisis De Eficiencia De Algoritmos
« Respuesta #2 en: Viernes 30 de Septiembre de 2005, 19:44 »
0
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.

Ocean Soul

  • Miembro activo
  • **
  • Mensajes: 38
    • Ver Perfil
Re: Analisis De Eficiencia De Algoritmos
« Respuesta #3 en: Miércoles 5 de Octubre de 2005, 23:00 »
0
Gracias!!!!  :)