Hoja de Problemas de Programacion II - Solucion del problema 1

Problema 1

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?

[1] El algoritmo es de orden O(n³)
[2] El algoritmo es de orden O(2ⁿ)
[3] 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, n₀ : " n > n₀ : T(n) £ c·f(n)

Donde c es un valor real positivo y n₀ 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:

T₁(n) Î O(n³) Þ T₁(n) £ c₁·n³ Þ c₁ £ T₁(n)/n³ = 0'001/20³ = 0'125·10^-6
T₂(n) Î O(2ⁿ) Þ T₂(n) £ c₂·2ⁿ Þ c₂ £ T₂(n)/2ⁿ = 0'001/2²⁰ = 0'954·10^-9
T₃(n) Î O(n!) Þ T₃(n) £ c₃·n! Þ c₃ £ T₃(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):

T₁(n) £ c₁·n³ Þ T₁(30) £ c₁·30³ = 0'003375 segundos.
T₂(n) £ c₂·2ⁿ Þ T₂(30) £ c₂·2³⁰ = 1'024 segundos.
T₃(n) £ c₃·n! Þ T₃(30) £ c₃·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):

T₁(30)/T₁(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).
T₂(30)/T₂(20) = 1'024/0'001 = 1024 veces más rápido.
T₃(30)/T₃(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.

Regresar a la página de enunciados.