如何计算n log n = c

我有一个我的算法类的作业问题，要求我计算一个问题的最大大小，这个问题可以用给定的操作数来解决，使用O（n log n）算法即：n log n = c）。我能够通过近似得到答案，但有没有一种干净的方法可以得到确切的答案？如何计算n log n = c

来源

2010-10-02 jlewis42

c/ProductLog [c]？ – 2010-10-02 20:39:10

这个等式没有封闭形式的公式。基本上，可以改造等式：

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

来源

2010-10-02 20:35:38 liori

O符号只会给你方程中最大的项。即您的O（n log n）算法的性能实际上可以更好地由c =（n log n）+ n + 53表示。

这意味着，如果不知道算法性能的确切性质，无法计算处理给定数量数据所需的确切操作次数。

但是可以计算出处理大小为n的数据集所需的最大操作数大于某个数，或者相反，使用该算法和该数可以解决的最大问题集的操作，小于一定数量。

的O表示法是用于比较2种算法是有用的，即，为O（n^2）算法比为O（n^3）算法等

Wikipedia看到更多的信息更快。

some help with logs

来源

2010-10-02 20:36:25

是的，计算“n Log [n] == c”的根不等于“计算问题的最大尺寸......” – 2010-10-02 20:48:23

您的解释是正确的，但对于这个特定问题，我们可以假设该算法恰好是n log n。我可能应该在问题中说明这一点。 – jlewis42 2010-10-02 20:58:49

如何计算n log n = c

回答

相关问题