Programación General > Pascal

 Analisis De Eficiencia De Algoritmos

(1/1)

Ocean Soul:
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:
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:
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:
Si porfavor explica porque para K usas (1+n)/2

Amilius:
: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  ;)

Navegación

[0] Índice de Mensajes