Dada una computadora rápida y lenta, ¿en qué tamaños la computadora rápida que ejecuta un algoritmo lento supera a la computadora lenta que ejecuta un algoritmo rápido?

La fuente de esta pregunta proviene de un curso de pregrado que estoy tomando, que cubre una introducción al análisis de algoritmos. Esto no es para la tarea, sino más bien una pregunta formulada en CLRS.

Tiene una máquina lenta que funciona con MIPS y una máquina rápida que funciona con MIPS. También tiene dos algoritmos de la misma clase, pero diferentes complejidades de tiempo de ejecución: un algoritmo "lento" se ejecuta en mientras que un algoritmo "rápido" se ejecuta en . $x$ $y$ $T(n) = c_1n^2$ $T(n) = c_2n \log n$

Ejecutas el algoritmo lento en la máquina rápida y el algoritmo rápido en la máquina lenta. ¿Cuál es el valor más grande de n tal que la máquina rápida que ejecuta el algoritmo lento supera a la máquina lenta que ejecuta el algoritmo rápido?

Mi solución hasta ahora:

Encuentre el conjunto de todos $n$ tal que

\frac{c_{2} n \log n}{x} > \frac{c_{1} n^{2}}{y}

$\frac{c_2n\log n}{x} > \frac{c_1n^2}{y}$ donde

n

$n$ es un número natural.

Este es mi trabajo hasta ahora:

{n : \frac{c_{2} n \log_{2} n}{x} > \frac{c_{1} n^{2}}{y}, n \in N} = {n : n < \frac{c_{2} y}{c_{1} x} \log_{2} n, n \in N}

$\{n : \frac{c_2 n \log_2 n}{x} > \frac{c_1 n^2}{y}, n \in \mathbb{N}\} = \{n : n < \frac{c_2 y}{c_1 x} \log_2 n, n \in \mathbb{N}\}$

La única solución que se me viene a la mente ahora es enchufar y cambiar todos los valores de $n$ hasta que encuentre el primer n donde

n < \frac{c_{2} y}{c_{1} x} \log (n)

$n < \frac{c_2y}{c_1x}\log(n)$

ya no se sostiene

algorithms algorithm-analysis runtime-analysis mathematical-analysis DoggoDougal
fuente

Esto es realmente más una cuestión de matemáticas que una cuestión de informática. Si reemplaza con entonces tiene una ecuación trascendental sobre los reales, que realmente no puede reducir a una solución de forma cerrada para . Una vez que encuentre una , su respuesta es redondearán al número entero más cercano. En otras palabras, "plug-n-chug" o "adivina y verifica" es tan bueno como puedes hacerlo en el caso general. Esto generalmente se manifiesta como métodos gráficos o numéricos.

n

$n$

x

$x$

x

$x$

x

$x$

x

$x$

Patrick87

Respuestas:

Considera tu última desigualdad:

$\qquad \displaystyle n < \frac{c_2y}{c_1x}\log(n)$

Ahora, con es una función cóncava . Por lo tanto, hay como máximo dos intersecciones, y solo una de ellas es interesante para usted; es decir, resolver $C\log n$ $C = \frac{c_2y}{c_1x}$

$\qquad \displaystyle n = C\log(n)$

y descubra qué algoritmo es más rápido en qué intervalo simplemente calculando los valores de función respectivos en algún punto del intervalo respectivo.

Es cierto que resolver esta igualdad explícitamente es difícil / imposible. Para algunos fijos , el álgebra computacional le da una expresión en una función bien conocida; interesante (real) intersección resulta estar en $C$

$\qquad \displaystyle n = e^{-W_{-1}(-\frac{\ln 2}{C})}$

si , con la continuación analítica de la función de registro del producto . Esta función no tiene una buena forma cerrada, pero se puede evaluar numéricamente para dado ; por ejemplo, obtienes para . $C \geq e \ln 2$ $W_k$ $C$ $\approx 116,74$ $C=17$

Rafael
fuente

Solo asegurándome: ¿interpretaste mi ecuación como el registro natural o log-base-2? Debo aclarar que cada instancia de log (n) es de base 2, y modificará la pregunta adecuadamente.

DoggoDougal

En CS, usualmente usamos , mientras que los matemáticos asumen . Por lo tanto, cuando uso es para la base , se observan excepciones. Esto es (probablemente) de donde proviene en el resultado.

\log = \log_{2}

$\log = \log_2$

\log = \ln

$\log = \ln$

\log

$\log$

2

$2$

\ln 2

$\ln 2$

Raphael