如何計算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

回答

相關問題