ANALISIS DE ALGORITMOS

RICARDO MUÑOZ

 

Un programa de computadora, aun cuando se derive de un algoritmo correcto, puede ser inútil para cierto tipo de entrada ya sea porque el tiempo necesario para correrlo o el espacio requerido para almacenar los datos, las variables del programa, etcétera, son demasiado grandes. El análisis de un algoritmo se refiere al proceso de derivar estimaciones del tiempo y el espacio necesarios para ejecutarlo.

• Es común que nos interese menos el tiempo exacto, en el mejor y peor caso, requerido para ejecutar un algoritmo que la manera en que aumenta el tiempo del mejor y peor caso cuando se incrementa el tamaño de la entrada. Por ejemplo, suponga que en el peor caso el tiempo para ejecutar un algoritmo es

• t (n) = 60n2 + 5n + 1

• para una entrada de tamaño n. Para n grande, el término 60n2 es aproximadamente igual que t(n) (vea la tabla 4.3.2). En este sentido, t(n) crece como lo hace 60n2.

• Si t(n) mide el tiempo en el peor caso para una entrada de tamaño n en segundos, entonces

• T(n) =n2+5/60n+1/60

• mide el tiempo en el peor caso para la entrada de tamaño n en minutos. Ahora, este cambio de unidades no afecta cómo aumenta el tiempo en el peor caso cuando crece el tamaño de la entrada, sino sólo las unidades en que se mide ese tiempo para una entrada de tamaño n. Entonces, cuando se describe el incremento en el tiempo del mejor o el peor caso con- forme aumenta el tamaño de la entrada, no sólo se busca el término dominante [por ejemplo, 60n2 en la fórmula de t(n)], sino también se pueden ignorar los coeficientes constantes. Con esas suposiciones, t(n) crece como lo hace n2 cuando n se incrementa.

DEFINICIÓN 4.3.2

• Se dice que t(n) es del orden n2 y se escribe

• t (n) = (n2 ),

• Sean f y g dos funciones con dominio {1, 2, 3, . . .}.

• Se escribe

• f (n) = O (g(n))

• y se dice que f (n) es del orden a lo más g (n), o f (n) es O mayúscula de g (n) si existe una constante positiva C1 tal que

• | f (n)| ≤ C1 |g(n)|

• para todos los enteros positivos n, excepto un número finito de ellos.

• Se escribe

• f (n) = (g(n))

• y se dice que f(n) es del orden al menos g (n) o f (n) es omega de g (n) si existe una constante positiva C2 tal que

• | f (n)| ≥ C2 |g(n)|

• para todos los enteros positivos n, excepto un número finito de ellos.

• Se escribe

• f (n) = (g(n))

• y se dice que f(n) es del orden g (n) o f (n) es theta de g (n) si f (n) = O(g (n)) y f (n) =

• (g(n)).

DEFINICION 4.3.11

• Si un algoritmo requiere t(n) unidades de tiempo en el mejor caso para una entrada de tamaño n y

• t (n) = O (g(n)),

• se dice que el tiempo en el mejor caso requerido por el algoritmo es de orden a lo más g(n)

• o que el tiempo en el mejor caso requerido por el algoritmo es O(g(n)).

• Si un algoritmo requiere t(n) unidades de tiempo para terminar en el peor caso para una entrada de tamaño n y

• t (n) = O (g(n)),

• se dice que el tiempo en el peor caso requerido por el algoritmo es de orden a lo más g(n)

• o que el tiempo en el peor caso requerido por el algoritmo es O(g(n)).

• Si un algoritmo requiere t(n) unidades de tiempo para terminar en el caso promedio para una entrada de tamaño n y

• t (n) = O (g(n)),

• se dice que el tiempo en el caso promedio requerido por el algoritmo es de orden a lo más g(n) o que el tiempo en el caso promedio requerido por el algoritmo es O(g(n)).

• Al reemplazar O por y “a lo más” por “al menos” en la definición 4.3.11, se obtiene la definición de qué quiere decir que en el mejor caso, el peor caso o el caso promedio el tiempo de un algoritmo sea del orden de al menos g(n). Si el tiempo requerido por el algoritmo en el mejor caso es O(g(n)) y (g(n)), se dice que el tiempo requerido por el algoritmo en el mejor caso es (g(n)). Una definición análoga se aplica al tiempo de un algoritmo en el peor caso y el caso promedio.

EJEMPLO 4.3.12

• Suponga que se sabe que un algoritmo toma

• 60n2 + 5n + 1

• unidades de tiempo para terminar en el peor caso para entradas de tamaño n. Se demostró en el ejemplo 4.3.3 que

• 60n2 + 5n + 1 = (n2 ).

• Así, el tiempo en el peor caso requerido por este algoritmo es (n2).

• do{

• System.out. Println(“Ingrese un numero”);

• num=In.leerInt();

• }while((num<0)&& (num>20))