Почему nlogn так трудно инвертировать?

Question

Допустим, у меня есть функция, которая не используется в требованиях к пространству, я хочу определить максимальный размер ввода для этой функции для данного доступного пространства. т.е. я хочу найти где nlogn = c.

Я следовал подходу , чтобы вычислить n, которое выглядит так в 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))
}

Но я не могу понять , почему это должно решаться итеративно. Для интересующего нас диапазона (n> 1) функция неособа.

Answer 1

В n log n нет ничего особенного - почти все элементарные функции не могут иметь элементарных инверсий и поэтому должны решаться другими способами: деление пополам, метод Ньютона, лагранж теорема об обращении, обращение рядов, функция Ламберта W ...

Answer 2

Как Гарет намекнул, что функция Ламберта W ( например, здесь ) приводит вас почти туда, действительно n = c / W (c)

Крошечный Google нашел это , что может быть полезно.

Answer 3

Последующее (будучи полностью явным):

library(emdbook)

n <- 2.5

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

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

Вероятно, существуют незначительные различия в скорости, точности и т. Д. В двух реализациях.Я не тестировал и не тестировал их.(Теперь, когда я попробовал

library(sos)
findFn("lambert W")

, я обнаружил, что он реализован повсеместно: игровой пакет и целый пакет, который называется LambertW ...