Elegante manera de solucionar $n\log_2(n) \le 10^6$

Question

Estoy estudiando Tomas Cormen Algoritmos libro y resolver tareas que se enumeran después de cada capítulo.

Tengo curiosidad acerca de la tarea de 1-1. que es justo después del Capítulo #1.

La pregunta es: ¿cuál es la mejor manera de resolver: $n\lg(n) \le 10^6$, $n \in \mathbb Z$, $\lg(n) = \log_2(n)$; ?

La más simple pero más larga es la sustitución. Hay algunas elegantes formas de solucionar esto? Gracias!

Algunas explicaciones: $n$ - es lo que yo debería calcular el total de la cantidad de elementos de entrada, $10^6$ - tiempo (en microsegundos) - total algoritmo de tiempo de ejecución. Que debo averiguar nmax.

Answer 1

La primera aproximación para la inversa de a$x\;\text{lg}\; x$$x/\text{lg}\; x$. Así que comienza con el valor de $10^6/\text{lg}(10^6)$, luego de ajustar por sustitución/bisecion.

Answer 2

En primer lugar, me encontré con una potencia de 2, $n=2^p$, de tal manera que $n\log_2 n=2^p\cdot p\approx 10^6$. Desde $2^{20}\approx 10^6$, que probablemente va a ser un clic o dos por debajo de eso. Efectivamente, $16\cdot 2^{16}=2^{20}=1048576$.

Ahora me di cuenta que los $\log_2 n \approx 16$, lo $n \approx 10^6/16=62500$. Efectivamente, para que $n$, $n\log_2 n \approx 995723$.

Ahora algunos simple búsqueda o interseccion de hacer el truco: $63000$ $62750$ son demasiado grandes; $62625$, $62700$, $62725$ son demasiado pequeños; etc. El número de interseccion pasos, si el uso estricto de la reducción a la mitad del intervalo, es delimitada por $\log_2 n$. Así que usted sabe que va a llegar allí rápidamente. Finalmente me di cuenta que si $n=62746$, $n\cdot\log_2 n \approx 999998$.

Que es el mayor entero $n$; por lo $n\leq 62746$ es su respuesta.

EDIT: antes he sugerido que el método de Newton era demasiado robusto para el trabajo. Bueno, creo que estoy equivocado. Después de todo, la derivada de $f(n)=n\log_2 n$ es sólo $f'(n)=\log_2 n+\log_2 e$, y usted tiene que calcular $\log_2(n)$, de todos modos cada vez que haces una interseccion paso. Así que la derivada de la información está ahí, de uso gratuito. Si yo fuera a la codificación de un algoritmo, sí, creo que yo haría el método de Newton. Un caso similar podría hacerse para el uso de Newton, incluso para la inicial $p\cdot 2^p$ búsqueda.

Answer 3

Para mi dinero, es el mejor camino para solucionar $n\log_2n=10^6$ por el Método de Newton.

Answer 4

Si algo más pirulo que el método de Newton es querido, recomiendo la iteración de punto fijo:

x := (10^6)/log_2(x) 

Esto se hace fácilmente con una calculadora applet mediante el almacenamiento constante (10^6) * log_10(2) y después de tomar $\log_{10}(x)$, de sable, y luego multiplicando por la recordó constante.

Comenzando con evidente sobreestimar $x_0 = 10^6$, el de punto fijo recorre alternar entre bajo y sobre la filmación:

x1 = 50,171.67
x2 = 64,042.69
x3 = 62,630.17
x4 = 62,756.63
x5 = 62,745.18
x6 = 62,746.21
x7 = 62,746.12

Por lo tanto el mayor entero es $n = 62746$, como Michael ya se dijo.

Answer 5

Para resolver por $n\log_2(n)=10^6$, podemos utilizar la función de Lambert-W función. Un poco de manipulación de los rendimientos $$ \log(n)e^{\log(n)}=10^6\log(2) $$ y la de Lambert-función W, siendo el inverso de a $xe^x$, dice que $$ \log(n)=\mathrm{W}\left(10^6\log(2)\right) $$ o $$ n=\exp\left(\mathrm{W}\left(10^6\log(2)\right)\right) $$ en lo positivo de reales, la de Lambert-W función es monótona creciente, para que usted pueda obtener la deseada desigualdad.

Mathematica ofrece el resultado de $62746.1264697$ N[Exp[LambertW[10^6Log[2]]],12].

Por lo tanto, el mayor $n$$62746$.