Tiempo de complejidad - ¿por qué hace duplicar la velocidad dada esta mejora?

Question

Hola he estado estudiando el tiempo de complejidad recientemente y estoy realmente confundido acerca de algo que me he topado.

El problema

Supongamos que podemos resolver un problema de tamaño n de la instancia en 1 hora. Si tenemos el doble de la velocidad de la máquina, cómo la magnitud del problema de ejemplo pueden ahora resolver?

La Respuesta

Complejidad: $log_2(n)$
Mejora: $n \rightarrow n^2$

Complejidad: $n$
Mejora: $n \rightarrow 2n$

Complejidad: $n^2$
Mejora: $n \rightarrow \sqrt{2}n$

Complejidad: $2^n$
Mejora: $n \rightarrow n+1$

La Pregunta

Entiendo que la mejora de la complejidad de la $n$. La duplicación de la velocidad de la máquina le da $2n$, pero lo que no veo es la razón por la que otras complejidades que tenemos que mejora concreta! por ejemplo, ¿por Qué la duplicación de la velocidad de la máquina para la complejidad de la $n^2$ nos da una mejora de $\sqrt{2}n$.

Podría alguien por favor explique lo que me falta. Gracias.

Answer 1

Este es el punto de la medida de la complejidad. Si se duplica la velocidad de la máquina, que puede pagar dos veces tantas operaciones. Si usted tiene un proceso de complejidad $n^2$, pregunte qué $m$ le dará dos veces tantas operaciones. Por lo tanto queremos $m^2=2n^2$ y resolverlo para obtener $m=\sqrt 2 n$. Semejantemente para un proceso de complejidad $\log_2 n$, pedimos lo que $m$ nos daría $\log_2m = 2 \log_2 n$ por las leyes de los logaritmos, esto se soluciona por $m=n^2$

Answer 2

Supongamos que la complejidad es $n^2$; luego, el tiempo se $t_1(n)$ necesario para resolver un problema de tamaño de $n$ $t_1(n)=an^2$ para algunos positiva constante de proporcionalidad $a$. Ahora supongamos que usted haga funcionar la máquina dos veces más rápido; que reduce el tiempo requerido en la mitad, por lo que el nuevo tiempo requerido es $t_2(n)=\frac12an^2$.

Supongamos ahora que el original de la máquina puede resolver un problema de tamaño de $n_0$ $1$ hora, por lo que $$t_1(n_0)=an_0^2=1\;;$$ clearly $a=\dfrac1{n_0^2}$. A continuación, la máquina más rápida toma

$$t_2(n)=\frac12an^2=\frac1{2n_0^2}n^2\tag{1}$$

horas para resolver un problema de tamaño de $n$. A ver lo que la mejora es, el uso de $(1)$ a averiguar cómo el gran problema que el más rápido de la máquina puede resolver en una hora por la resolución de la ecuación

$$\frac1{2n_0^2}n^2=1\tag{2}$$

para obtener $$n=\sqrt{2n_0^2}=\sqrt2~n_0\;.$$ In other words, the faster machine can solve in one hour a problem that is bigger by a factor of $\sqrt 2$ que el problema más grande que el más lento de la máquina puede resolver en una hora. La misma proporción se mantiene para cualquier otro período de tiempo.

Similares de análisis de rendimiento de los otros resultados que usted menciona.