Analisis de algoritmos

[m@o_614]

Saludos estoy empezando a leer un libro de analisis de algoritmos y viene un codigo al que le tengo que calcular el tiempo de ejecucion, esto sumando las operaciones elementales(asiganciones,retornos,acceso a estructuras indexadas, etc..) de cada linea de codigo pero tengo duda de como calcular el tiempo de ejecucion para el mejor caso

el codigo esta en modula-2

PROCEDURE Buscar(VAR a:vector;c:INTEGER):CARDINAL;
VAR j:CARDINAL;
BEGIN
  j :=1;                                       (1)
  WHILE(a[j] >c) AND (j < n) DO   (2)
     j:=j+1;                                  (3)
  END;                                         (4)
IF a[j]=c THEN                             (5)
  RETURN j;                                  (6)
ELSE RETURN 0;                            (7)
END;                                             (8)
END Buscar;

y el libro dice

En el mejor caso para el algoritmo, se efectuara la linea 1 y de la linea 2 solo la primera mitad de la condicion, que supone 2 OE(suponemos que las expresiones se evaluan de izquierda a derecha y una expresion logica deja de ser evaluada en el momento que se conoce su valor, aunque no hayan sido evaluados todos sus terminos. Tras ellas se acaba ejecutando las lineas (5) y (7), en consecuencia T= 1+2+3=6

pero no entiendo porque en la linea 2 solo evalua la mitad de la condicion, si es un AND no se supone que tiene que evaluarla completa??

gracias de antemano

[ivancea96]

No se si es esto a lo que te refieres, pero voy:

Una AND, en el momento en que una condición es FALSE, la AND entera es FALSE.

Ahora bien, en Modula-2, no se en que orden se manejan estas cosas.
Habría que ver el código en ASM que genera.

Bueno, cabe decir que de algoritmos y tiempos de ejecución sé lo básico.

[m@o_614]

Una ultima pregunta, ahora tengo el codigo de busqueda secuencial (busca el elemento x)

i=0;
while((i<n)&&(v!=x))
    i = i+1;
if(i==n)
  enc = false;
else
 enc = true;

y me dice que saque tiempo de ejecucion del mejor y peor caso, el mejor caso pues es si x se encuentra en la primera posicion del vector y seria

T(n) = ta + (2tc + tc + ta)

donde ta es el numero de asignaciones, tc = numero de comparaciones y to  = numero de operaciones aritmeticas

pero para el peor seria que x no se encuentre en el vector y en este caso yo calcule que seria:

T(n) = ta + (n*(2tc + to + ta)) + tc + tc +ta

pero el libro me dice que la respuesta correcta es

T(n) = (2tc + 2to +2ta)*n + (2tc +2ta)

alguien sabe por que es esto??

gracias

[ivancea96]

A mi parecer sería:

Código (cpp) [Seleccionar] Expandir


i=0;                //ta

while((i<n)&&(v!=x))   //Aqui primero se compararia: 2tc
                                 //Luego, se haria el bucle: n*(to + ta + 2tc)
     i = i+1;

if(i==n)        //tc
   enc = false;
else              // Luego, solo habra una, asi que si o si será ta
  enc = true;


En total, me quedaría:

   T(n) = ta + 2tc + n*(to + ta + 2tc) + tc + ta

Si dejamos mejor la ecuación:

   T(n) = 2ta + 3tc + n*(to + ta + 2tc)

Y así es como em quedaría a mi.
Esto lo hago así con lógica, pero yo eso de tiempos nunca lo aprendí xD

No entiendo por qué pones: T(n) = ta + (n*(2tc + to + ta)) + tc + tc +ta
En el if solo hay una comparación.

[The_Mushrr00m]

Como off-topic solo sugiriria que usaran las etiquetas de code 

Digo, nadamas para que se vea bonito 

[m@o_614]

Código (c) [Seleccionar] Expandir

i=0;                //ta

while((i<n)&&(v!=x))   //desde aqui le pongo n* las dos condiciones -> n*(2tc) pero
                                   para que el ciclo while se salga se tiene que evaluar
                                    la condicion (i <n)  una vez mas y ya que sea
                                   falsa ya no tiene caso evaluar el resto de condicion (y!=x)
                                   por eso le puse un tc extra.
     i = i+1;                 // Aqui hay una asignacion y una operacion -> to + ta

if(i==n)        //tc
   enc = false;
else              // Luego, solo habra una, asi que si o si será ta
  enc = true;