如何计算n log n = c

Question

我的算法类有一个作业问题,要求我计算一个问题的最大大小,该问题可以使用O(n log n)算法在给定数量的操作中解决(即:n log n = c).我能够通过近似得到一个答案,但有没有一个干净的方法来得到一个确切的答案？

Answer 1

这个等式没有封闭形式的公式.基本上,你可以改变方程式:

 n log n = c
log(n^n) = c
     n^n = exp(c)

然后,这个等式有一个形式的解决方案:

n = exp(W(c))

其中W是Lambert W函数(特别参见"例2").事实证明,W不能用基本操作来表达.

但是,f(n)=n*log(n)是一种单调的功能.你可以简单地使用二分(在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