1 votos

Tengo un problema con esta tarea

Supongamos que un algoritmo utiliza $2n^2+3^n$ operaciones de bits para resolver un problema de tamaño $n$ . Supongamos que su máquina puede realizar una operación de bits en $10^{-9}$ segundos, cuánto tarda su algoritmo en resolver un problema de tamaño dado a continuación. Tenga en cuenta que si su algoritmo tarda más de $60$ segundos, responder en minutos. Para más de $60$ minutos, responder en horas. Para más de $24$ horas, respuesta en días. Para más de $365$ días, responda en años. Para más de 100 años, responde en siglos.

(a) 10

(b) 20

(c) 50

(d) 100

(e) 1000

1voto

Oli Puntos 89

Nos ocupamos de $n=50$ . Así que tenemos que evaluar $2(50)^2+3^{50}$ . El $2(50)^2$ parte es fácil de evaluar, mediante una calculadora o, más sencillamente, en la cabeza. Obtenemos $5000$ .

En realidad, es no importa lo que obtenemos, ya que $2(50)^2$ es totalmente insignificante en comparación con $3^{50}$ .

Para evaluar $3^{50}$ podemos utilizar una calculadora. Pero como la calculadora puede atragantarse después con $3^{1000}$ Lo hacemos de otra manera.

Utilizaremos logaritmos a la base $10$ . Así que por $\log$ nos referimos a $\log$ a la base $10$ . Tenga en cuenta que $3=10^{\log 3}$ Así que $3^{50}=10^{50\log 3}$ .

La calculadora da $50\log 3\approx 23.856$ Así que $3^{50}\approx (10^{23})(10^{0.856})$ . Concluimos que $$3^{50}\approx 7.18\times 10^{23}.$$ Cada operación lleva $10^{-9}$ segundos. Así que el número de segundos utilizados es aproximadamente $7.18\times 10^{14}$ .

Dividir por $3600$ para obtener horas, entonces por $24$ para conseguir días, entonces por $365$ para obtener (aproximadamente) años, entonces por $100$ para conseguir siglos. Mucho tiempo. El objetivo del problema es hacer que tu calculadora se ejercite, y mostrarte la rapidez de la función $3^n$ crece.

Observación: En realidad, no tenemos absolutamente necesito registros para calcular $3^{1000}$ . Mi calculadora científica barata dice "E" y se niega a hacer nada si le digo que busque $3^{1000}$ . Sin embargo, no tiene ningún problema en declarar que $3^{125}\approx 4.3667\times 10^{59}$ . Pero $3^{1000}$ es el $8$ -ésima potencia de esto, que es aproximadamente $(4.3667)^8\times 10^{(8)(59)}$ .

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X