如何计算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屋！