Cómo calcular n log n = c

Question

Tengo un problema de tarea para mi clase de algoritmos que me pide que calcule el tamaño máximo de un problema que puede resolverse en un número dado de operaciones usando un algoritmo O (n log n) (es decir: n log n = c). Pude obtener una respuesta al aproximarme, pero ¿hay una forma clara de obtener una respuesta exacta?

Answer 1

No existe una fórmula cerrada para esta ecuación. Básicamente, se puede transformar la ecuación:

n log n = c 
log(n^n) = c 
    n^n = exp(c) 

Entonces, esta ecuación tiene una solución de la forma:

n = exp(W(c)) 

donde W es Lambert W function (véase especialmente "Ejemplo 2"). Se demostró que W no se puede expresar usando operaciones elementales. Sin embargo, f(n)=n*log(n) es una función monótona. Puede simplemente usar bisección (aquí en Python):

import math 

def nlogn(c): 
    lower = 0.0 
    upper = 10e10 
    while True: 
     middle = (lower+upper)/2 
     if lower == middle or middle == upper: 
      return middle 
     if middle*math.log(middle, 2) > c: 
      upper = middle 
     else: 
      lower = middle 

Answer 2

la notación O sólo le da el mayor término de la ecuación. Es decir, el rendimiento de su algoritmo O (n log n) en realidad podría estar mejor representado por c = (n log n) + n + 53.

Esto significa que sin conocer la naturaleza exacta del rendimiento de su algoritmo no lo haría No se puede calcular el número exacto de operaciones requeridas para procesar una determinada cantidad de datos.

Pero es posible calcular que el número máximo de operaciones requeridas para procesar un conjunto de datos de tamaño n es mayor que un cierto número o, a la inversa, el mayor problema que se puede resolver, utilizando ese algoritmo y ese número de operaciones, es más pequeño que un cierto número.

La notación O es útil para comparar 2 algoritmos, es decir, un O (n^2) algoritmo es más rápido que un O (n^3) algoritmo etc.

ver Wikipedia para obtener más información.

some help with logs