r - 为什么 nlogn 很难反转？

Question

假设我有一个空间要求为 nlogn 的函数，我想计算出该函数在给定可用空间下的最大输入大小。即我想在 nlogn=c 处找到 n。

我关注了an approach计算 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 没有什么特别之处——几乎所有初等函数都没有初等逆函数，因此必须通过其他方法求解:二分法、牛顿法, 拉格朗日反演定理, 级数求逆, Lambert W函数...