線性或者（N log n）的時間複雜度

function f(n) { 
    var cnt = 0; 

    for (var j = n; j > 0; j = Math.floor(j/5)) { 
    var k = j * 2; 

    while (k > 0) { 
     cnt++; 
     k -= 5; 
    } 
    } 

    return cnt; 
}

是時候該功能O(n)或O(n log n)和爲什麼的複雜性？
測試產生接近線性增長，但對於某些n log n算法也是如此，對嗎？線性或者（N log n）的時間複雜度

來源

2016-02-03 NMRT

測試時，一定要禁用所有運行時優化。他們可以對您的測量產生非常大的影響... – alesc

@alesc：我認爲他測量了'cnt'。 –

是在for每次循環執行的操作的鏈接形成一系列可以通過geometric series近似（這是一個近似的地板， - = 5，但可以作爲一個上限）。

進展的總和將是等於第一項乘以某個常數，以相同的方式如1 + 1/2 + 1/4 ... = 2

所以這是O （N）。

來源

2016-02-03 16:25:40

-1

你有for循環從i = 1到log（n），while循環的長度是2 * n/5^i * 1/5。讓我們來計算summ：2/5 * n *（從i = 1到log（n）：1/5^i）summ是幾何。進展，所以它是有限的。所以你有O（c * n），其中c是一個常數。

來源

2016-02-03 16:13:57 UpmostScarab

「所以這是......」這是你的解釋中巨大的，不正確的差距。 –

它是2 * sum(5^j/5) for j = 0 to log_{5}(n) = O(n)。它基本上是一個幾何級數。維基百科https://en.wikipedia.org/wiki/Geometric_progression

來源

2016-02-03 16:24:27 piotrekg2

假設複雜度的迭代COUN 爲Ç complexiti的是C = LN（N）/ LN（5）和同時爲C = K/5（K = j的* 2）所有的複雜性是

N = 5^m -> m = ln(n)/ln(5) C(n) = sum(k = 0->m)(5^k/5) * 2 C(n) = (1 - 5^m)/(1 - 5) * 2 = (n + 1)/2 O(n) = n

來源

2016-02-03 16:26:54 TheBook

你不能簡單地乘以這兩個數字。 –

我除以2，原因。 – TheBook

沒有區別。你有一個上限，但是一個鬆動。 –

線性或者（N log n）的時間複雜度

回答

相關問題