为什么nlogn这么难反转？ [英] Why is nlogn so hard to invert?

问题描述

可以说我有一个空间需求为nlogn的函数，我想计算出给定可用空间下该函数的最大输入大小。即我想找到n其中nlogn = c。

Lets 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.

我遵循了一种方法计算n，在R中看起来像这样：

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))
}

但是我可以不能理解为什么为什么必须迭代解决。对于我们感兴趣的范围（n> 1），该函数不是奇异的。

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.

推荐答案

没什么特别的n log n —几乎所有基本函数都没有基本逆，因此必须通过其他方法解决：二等分，牛顿法，Lagrange逆定理，级数逆转，Lambert W功能...

There's nothing special about n log n — nearly all elementary functions fail to have elementary inverses, and so have to be solved by some other means: bisection, Newton's method, Lagrange inversion theorem, series reversion, Lambert W function...

这篇关于为什么nlogn这么难反转？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！