• Domingo 22 de Septiembre de 2019, 13:03

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

Ocean Soul

  • Miembro activo
  • **
  • Mensajes: 38
    • Ver Perfil
Analisis De Eficiencia De Algoritmos
« en: Jueves 8 de Septiembre de 2005, 23:33 »
0
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.

Amilius

  • Miembro HIPER activo
  • ****
  • Mensajes: 665
    • Ver Perfil
Re: Analisis De Eficiencia De Algoritmos
« Respuesta #1 en: Viernes 9 de Septiembre de 2005, 00:53 »
0
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

Ocean Soul

  • Miembro activo
  • **
  • Mensajes: 38
    • Ver Perfil
Re: Analisis De Eficiencia De Algoritmos
« Respuesta #2 en: Viernes 9 de Septiembre de 2005, 01:30 »
0
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.

Lastent

  • Nuevo Miembro
  • *
  • Mensajes: 21
    • Ver Perfil
Re: Analisis De Eficiencia De Algoritmos
« Respuesta #3 en: Lunes 12 de Septiembre de 2005, 03:28 »
0
Si porfavor explica porque para K usas (1+n)/2

Amilius

  • Miembro HIPER activo
  • ****
  • Mensajes: 665
    • Ver Perfil
Re: Analisis De Eficiencia De Algoritmos
« Respuesta #4 en: Martes 13 de Septiembre de 2005, 05:16 »
0
: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  ;)