为什么 nlogn 这么难反转？

发布于 2024-10-07 00:45:52 字数 502 浏览 6 评论 0原文

假设我有一个空间要求为 nlogn 的函数，我想计算出给定可用空间的该函数的最大输入大小。即我想找到n，其中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），该函数是非奇异的。

原文

Let's say I have a function that is nlogn in space requirements, I want to work out the maximum size of input for that function for a given available space. i.e. I want to find n where nlogn=c.

I followed an approach to calculate n, that looks like this in 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))
}

But I can't get understand why it must be solved iteratively. For the range we are interested (n>1), the function is non singular.

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

无声无音无过去 2024-10-14 00:45:52

n log n 没有什么特别之处 - 几乎所有初等函数都没有初等反函数，因此必须通过其他方法来求解：二分法、牛顿法、拉格朗日反演定理、级数反演、兰伯特W函数……

回复收藏 0 原文

一桥轻雨一伞开 2024-10-14 00:45:52

正如 Gareth 暗示的 Lambert W 函数（例如这里）让你几乎到达那里，确实 n = c/ W(c)

一个小谷歌发现了这个，这可能是有帮助。

回复收藏 0 原文

情话难免假 2024-10-14 00:45:52

跟进（完全明确）：

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 的整个包......

Following up (being completely explicit):

library(emdbook)

n <- 2.5

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

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

There are probably minor differences in speed, accuracy, etc. of the two implementations. I haven't tested/benchmarked them extensively. (Now that I tried