Pourquoi nlogn est-il si difficile à inverser?

Question

Disons que j'ai une fonction qui est nlogn dans les besoins d'espace, je veux travailler sur la taille maximale d'entrée pour cette fonction pour un espace disponible donné. c'est-à-dire que je veux trouver n où nlogn = c.

J'ai suivi an approach pour calculer n, qui ressemble à ceci dans R:

step = function(R, z) { log(log(R)-z)} 
guess = function(R) log(log(R)) 

inverse_nlogn = function(R, accuracy=1e-10) { 
zi_1 = 0 
z = guess(R) 
while(abs(z - zi_1)>accuracy) { 
    zi_1 = z 
    z = step(R, z) 
} 
exp(exp(z)) 
} 

Mais je ne peux pas comprendre pourquoi il doit être résolu de manière itérative. Pour la gamme qui nous intéresse (n> 1), la fonction est non singulière.

Answer 1

Il n'y a rien de spécial n log n - presque toutes les fonctions élémentaires ne parviennent pas à avoir des inverses élémentaires, et doivent donc être résolus par d'autres moyens: bissection, la méthode de Newton, théorème d'inversion de Lagrange, la réversion série, Lambert fonction W ...

Answer 2

Comme Gareth a laissé entendre la fonction Lambert W (eg here) vous fait presque là, en effet n = c/W (c)

Un google wee a trouvé this, ce qui pourrait être utile.

Answer 3

Faisant suite (être complètement explicite):

library(emdbook) 

n <- 2.5 

c <- 2.5*log(2.5) 
exp(lambertW(c)) ## 2.5 

library(gsl) 
exp(lambert_W0(c)) ## 2.5 

Il existe des différences probablement mineures de la vitesse, la précision, etc. des deux implémentations. Je n'ai pas testé/comparé de manière approfondie. (Maintenant que j'ai essayé

library(sos) 
findFn("lambert W") 

je découvre qu'il est mis en œuvre dans tous les sens: le paquet de jeux, et tout un paquet qui est appelé LambertW ...