本文介绍了为什么nlogn这么难反转?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

可以说我有一个空间需求为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这么难反转?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!

08-23 11:16