Guia de Analisis

Ejercicios de Análisis Asintótico de Algoritmos.
A continuación se muestra un conjunto de ejercicios resueltos de análisis asintótico

de algoritmos.
1.- Un programador ha implementado un algoritmo que tarda, en su antiguo ordenador de

100 Mhz, una milésima de segundo en resolver un problema de tamaño n = 20. ¿Cuanto
tardaría en resolver un problema de tamaño n = 30 en los siguientes casos?
● El algoritmo es de orden O(n3)

● El algoritmo es de orden O(2n)
● El algoritmo es de orden O(n!)
¿Por que factor debería multiplicar la velocidad de su ordenador para que volviera a
tardar una milésima de segundo? Nota: 1 año = 31.557.600 segundos.
Si denominamos T(n) a la "función" que indica el tiempo empleado por el algoritmo

para resolver un problema de tamaño n, la definición de cota superior me dice que si T(n)
pertenece al conjunto de cotas superiores dadas por la función f(n), entonces para tamaños
superiores a un determinado valor, T(n) es siempre menor o igual a f(n) multiplicado por una
determinada constante:
T(n) Î O(f(n)) Û $ c, n0 : " n > n0 : T(n) £ c·f(n)
Donde c es un valor real positivo y n0 un valor entero positivo. Ya que nos dicen lo
que tarda el algoritmo para un determinado tamaño, podemos calcular el valor de la
constante c (en realidad no su valor, sino una cota inferior) para cada uno de los algoritmos
del enunciado:
● T1(n) Î O(n3) Þ T1(n) £ c1·n3 Þ c1 £ T1(n)/n3 = 0'001/203 = 0'125·10-6

● T2(n) Î O(2n) Þ T2(n) £ c2·2n Þ c2 £ T2(n)/2n = 0'001/220 = 0'954·10-9
● T3(n) Î O(n!) Þ T3(n) £ c3·n! Þ c3 £ T3(n)/n! = 0'001/20! = 0'411·10-23
Se han utilizado los subíndices 1,2 y 3 para referirse a los tiempos y las constantes
de cada uno de los tres algoritmos que se mencionan en el enunciado. Conocido el valor de
la constante, ya podemos calcular cotas superiores para el tiempo que empleará cada
algoritmo en resolver un problema de un tamaño distinto (en este caso 30):
● T1(n) £ c1·n3 Þ T1(30) £ c1·303 = 0'003375 segundos.

● T2(n) £ c2·2n Þ T2(30) £ c2·230 = 1'024 segundos.
● T3(n) £ c3·n! Þ T3(30) £ c3·30! = 109027350432 segundos » 3455 años
Para poder obtener un tiempo de 1 milisegundo con un tamaño de la entrada n = 30,

deberemos conseguir un ordenador que sea tantas veces más rápido que el anterior como
la división entre el tiempo que se tardaba en el primer caso (n = 20) y el tiempo que se tarda
en el segundo caso (n = 30), es decir T(30)/T(20):
● T1(30)/T1(20) = 0'003375/0'001 = 3'375 veces más rápido (es decir, con un

ordenador que vaya a unos 350 Mhz nos bastaría).
● T2(30)/T2(20) = 1'024/0'001 = 1024 veces más rápido.
● T3(30)/T3(20) = 109027350432/0'001 » 100 billones de veces más rápido.
Para el primer algoritmo, el objetivo de que el tiempo vuelva a ser de una milésima
de segundo es perfectamente posible con los ordenadores actuales. Para el segundo
algoritmo, sería necesario utilizar uno de los mejores superordenadores existentes en la
actualidad. Para el tercer algoritmo, sin embargo, sería necesario desarrollar una nueva
tecnología, ya que con la actual es imposible (debido a los límites que impone la física)
crear ordenadores tan rápidos.
2.-Calcular el orden de complejidad de las siguientes funciones recursivas (contar sólo las
operaciones producto):
def f1(n):
if n < 1:
return 1
else:
return f1(n - 3) * f1(n - 3)
def f2(n):
if n < 1:
return 1
else:
return f2(n / 2) * f2(n / 2)*f2(n / 2)
def f3(n):
if n < 1:
return 1
else:
x = 1
for i in range(n):
x = x * n
return x * f3(n - 1)
def f4(n):
if n < 1:
return 1
else:
x = 1
for i in range(n * n):
x = x * 2;
return x * f4(n / 2)
Solución.
def f1(n):
if n < 1:
return 1
else:
return f1(n - 3) * f1(n - 3);
Si denominamos T(n) al número de operaciones producto que se realizan en
una llamada a la función f1(n), podemos ver que en el caso base (n = 0) no se
realiza ninguna y en cualquier otro caso se realiza una (marcada en rojo) mas las
que hagan las dos llamadas recursivas f1(n-3), Por lo tanto, la relación de
recurrencia será
T(0) = 0, T(n) = 2·T(n-3)+1
Podemos ver que se ajusta al esquema T(n) = a·T(n-b)+c·nk, donde a = 2, b =

3, c = 1, k = 0. Para este esquema sabemos que:
T(n) Î Q(nk+1) si a = 1, T(n) Î Q(an/b) si a > 1.
Por lo tanto el orden de la función f1 será Q(2n/3).
def f3(n):
if n < 1:
return 1
else:
x = 1
for i in range(n):
x = x * n
return x * f3(n - 1)
En el caso base (n = 0) no se realiza ningún producto y en cualquier otro caso se

realizan n+1 productos mas los que hagan la llamada recursiva f3(n-1). Por lo tanto,
la relación de recurrencia será
T(0) = 0, T(n) = T(n-1)+n+1
Se ajusta al esquema anterior, con a = 1, b = 1, c = 1, k = 1, por lo tanto el orden de

la función f3 será Q(n2).
def f2(n):
if n < 1:
return 1
else:
return f2(n / 2) * f2(n / 2)*f2(n / 2)
En el caso base (n = 0) no se realiza ningún producto y en cualquier otro caso

se realizan 2 productos mas los que hagan las tres llamadas recursivas a f2(n/2).
Por lo tanto, la relación de recurrencia será
T(0) = 0, T(n) = 3·T(n/2)+2

La relación se ajusta al esquema T(n) = a·T(n/b)+c·nk, donde a = 3, b = 2, c =
2, k = 0. Para este esquema sabemos que:
T(n) Î Q(nk) si a < bk
T(n) Î Q(nk·lg n) si a = bk
T(n) Î Q(nlogba) si a > bk
Por lo tanto el orden de la función f2 será Q(nlog23) = Q(n1.585).
def f4(n):
if n < 1:
return 1
else:
x = 1
for i in range(n * n):
x = x * 2;
return x * f4(n / 2)
En el caso base (n = 0) no se realiza ningún producto y en cualquier otro caso

se realizan n2+2 productos mas los que hagan la llamada recursiva f4(n/2). Por lo
tanto, la relación de recurrencia será
T(0) = 0, T(n) = T(n/2)+n2+2
Se ajusta al esquema anterior, con a = 1, b = 2, c = 1, k = 2, por lo tanto el

orden de la función f4 será Q(n2).
Introducción teórica
Previo a resolver los ejercicios pondremos un poco de teoría, ya que

estos ejercicios por norma general se resuelven de la misma manera. Si se
pidiera algo distinto se explicará la teoría en el propio ejercicio
Reducción por sustracción
La ecuación de la recurrencia es la siguiente:

La resolución de la ecuación de recurrencia es:
Reducción por división.
La solución de la ecuación de recurrencia es:
3.- calcular la ecuación de recurrencia y hallar el coste del siguiente algoritmo:
Se nos pide que hallemos la ecuación de recurrencia , que pueden ser la siguiente,
siguiendo los dos bucles
Siguiendo esta ecuación de recurrencia observamos que estamos ante una recursión por
división
.
Veremos las siguientes variables:
Por tanto, siguiendo esta fórmula, nos quedará:
4.- Hallar formalmente el coste de los siguientes algoritmos siendo h(n,r,k) ∈ O(n)
Función uno: Resolvemos la reducción por división como vimos previamente:

La resolución de la ecuación de recurrencia es:
Como es habitual en estos tipos de ejercicios las variables que tenemos son:
Por tanto, estaremos en el caso tercero siendo, por tanto, el coste
Función dos: Como previamente hemos dicho será también una recursión con
reducción por división, con estos datos:
El coste será el correspondiente con el caso primero siendo estas

llamadas externas más costosas que las recursivas, como antes, por lo que determinarán el
coste total.
5.- ¿En qué orden está el tiempo de ejecución del siguiente algoritmo? Justifica tu
respuesta
def h(n,i, j):

if n > 0:
h(n - 1, i, 6 - i - j)
i = j
h(n - 1, 6 - i - j, j)
Respuesta: Tendremos la siguiente ecuación de recurrencia que resuelve este algoritmo
Como es habitual en estos tipos de ejercicios deducimos las siguientes variables:
Aplicando la recurrencia de reducción por división siguiendo esto:
Tendremos que a=2 >1 , por tanto, aplicando la tercera fórmula, el coste del algoritmo es

Guia de Analisis

Cargado por

Copyright:

Formatos disponibles

Guia de Analisis

Cargado por

Información del documento

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Guia de Analisis

Cargado por

Copyright:

Formatos disponibles

Ejercicios de Análisis Asintótico de Algoritmos.

A continuación se muestra un conjunto de ejercicios resueltos de análisis asintótico

1.- Un programador ha implementado un algoritmo que tarda, en su antiguo ordenador de

● El algoritmo es de orden O(n3)

Si denominamos T(n) a la "función" que indica el tiempo empleado por el algoritmo

T(n) Î O(f(n)) Û $ c, n0 : " n > n0 : T(n) £ c·f(n)

● T1(n) Î O(n3) Þ T1(n) £ c1·n3 Þ c1 £ T1(n)/n3 = 0'001/203 = 0'125·10-6

● T1(n) £ c1·n3 Þ T1(30) £ c1·303 = 0'003375 segundos.

Para poder obtener un tiempo de 1 milisegundo con un tamaño de la entrada n = 30,

● T1(30)/T1(20) = 0'003375/0'001 = 3'375 veces más rápido (es decir, con un

T(0) = 0, T(n) = 2·T(n-3)+1

Podemos ver que se ajusta al esquema T(n) = a·T(n-b)+c·nk, donde a = 2, b =

T(n) Î Q(nk+1) si a = 1, T(n) Î Q(an/b) si a > 1.

Por lo tanto el orden de la función f1 será Q(2n/3).

En el caso base (n = 0) no se realiza ningún producto y en cualquier otro caso se

T(0) = 0, T(n) = T(n-1)+n+1

Se ajusta al esquema anterior, con a = 1, b = 1, c = 1, k = 1, por lo tanto el orden de

En el caso base (n = 0) no se realiza ningún producto y en cualquier otro caso

T(0) = 0, T(n) = 3·T(n/2)+2

T(n) Î Q(nk) si a < bk

T(n) Î Q(nlogba) si a > bk

Por lo tanto el orden de la función f2 será Q(nlog23) = Q(n1.585).

En el caso base (n = 0) no se realiza ningún producto y en cualquier otro caso

T(0) = 0, T(n) = T(n/2)+n2+2

Se ajusta al esquema anterior, con a = 1, b = 2, c = 1, k = 2, por lo tanto el

Previo a resolver los ejercicios pondremos un poco de teoría, ya que

Reducción por sustracción

La ecuación de la recurrencia es la siguiente:

Reducción por división.

La ecuación de la recurrencia es la siguiente:

La solución de la ecuación de recurrencia es:

3.- calcular la ecuación de recurrencia y hallar el coste del siguiente algoritmo:

Por tanto, siguiendo esta fórmula, nos quedará:

Función uno: Resolvemos la reducción por división como vimos previamente:

La ecuación de la recurrencia es la siguiente:

Por tanto, estaremos en el caso tercero siendo, por tanto, el coste

El coste será el correspondiente con el caso primero siendo estas

def h(n,i, j):

Como es habitual en estos tipos de ejercicios deducimos las siguientes variables:

Aplicando la recurrencia de reducción por división siguiendo esto:

También podría gustarte