math - 如何计算 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 function (尤其参见“示例 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