如何计算n log n = c [英] How to calculate n log n = c
问题描述
我的算法课有一个作业问题,要求我计算使用O(n log n)算法在给定数量的运算中可以解决的最大问题大小(即:n log n = c) .我可以通过近似得到答案,但是有一种干净的方法来获得确切的答案吗?
I have a homework problem for my algorithms class asking me to calculate the maximum size of a problem that can be solved in a given number of operations using an O(n log n) algorithm (ie: n log n = c). I was able to get an answer by approximating, but is there a clean way to get an exact answer?
推荐答案
该方程式没有封闭形式的公式.基本上,您可以变换方程式:
There is no closed-form formula for this equation. Basically, you can transform the equation:
n log n = c
log(n^n) = c
n^n = exp(c)
然后,该方程式的形式为:
Then, this equation has a solution of the form:
n = exp(W(c))
其中W是 Lambert W函数(尤其是参见示例2").事实证明,W
不能用基本运算来表示.
where W is Lambert W function (see especially "Example 2"). It was proved that W
cannot be expressed using elementary operations.
但是,f(n)=n*log(n)
是单调函数.您可以简单地使用bisection(在python中):
However, f(n)=n*log(n)
is a monotonic function. You can simply use bisection (here in python):
import math
def nlogn(c):
lower = 0.0
upper = 10e10
while True:
middle = (lower+upper)/2
if lower == middle or middle == upper:
return middle
if middle*math.log(middle, 2) > c:
upper = middle
else:
lower = middle
这篇关于如何计算n log n = c的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!