依賴嵌套for循環的時間複雜度？

你能解釋一下如何找到時間複雜度嗎？依賴嵌套for循環的時間複雜度？

sum=0; 
for(k=1;k<=n;k*=2) 
    for(j=1;j<=k;j++) 
    sum++;

所以，我知道外環有時間O（LOGN）的複雜性，但由於內循環迭代依賴於外環的值時，該算法的複雜性不O（nlogn ）。

這本書說它是O（n）。

我真的不明白它是如何爲O（n）...有人可以請解釋一下...... 我會非常感激，如果ü可以進入者均基於細節：d

的數學解決方案將有助於我更好地瞭解...

來源

2014-02-06 user2228135

雞蛋裏挑骨頭：循環*是*爲O（n log n）的，但* not * Theta（n log n）。我不知道是否所有的大學都作出了區分，雖然... –

外環執行的日誌（和Base2）N times.so它是O（日誌（和Base2） N）。

內循環爲外循環的每次迭代執行k次。現在在外循環的每次迭代中，k增加到k * 2。

內循環迭代= 1 + 2 + 4 + 8 + ... + 2 ^（日誌（和Base2）N）
= 2^0 + 2^1 + 2^2 +的所以總數.. 。+ 2 ^日誌（和Base2）N (geometric series)
= 2 ^（（日誌（BASE2）的n + 1）-1 /（2-1）
= 2n-1個。
= O（n）的
所以內部循環爲O（n）因此總的時間複雜度= O（n），如O（n + log（base2）n）= O（n）

更新：它也是O（nlogn）因爲nlogn >> n的n值很大，但它不是漸近緊的。你可以說它是o（nlogn）[小o]。

來源

2014-02-06 13:25:43 tanmoy

只看到多少次內循環運行：

1 + 2 + 4 + 8 + 16 +...+ n

注意，如果n = 32，那麼這個sum = 31 + 32. ~ 2n。
這是因爲除最後一項之外的所有術語的總和幾乎等於最後一項。

因此整體複雜度= O(n)。

編輯：

的幾何級數求和（http://www.mathsisfun.com/algebra/sequences-sums-geometric.html）是順序的：

(2^(logn) - 1)/(2-1) = n-1.

來源

2014-02-06 11:32:01

對不起，但我似乎不明白... O（logn）如何得到elminated？也許一些數學解決方案可以幫助我更好地理解...... – user2228135

@ user2228135如果您研究這個系列，它會以幾何形式增加。您可以通過標準公式找到該幾何系列的總和。 –

是的，幾何系列。例如，如果n = 4，那麼結果是二進制的「111」，其比1小於1000，即2n。（注意：我會從你的答案中刪除這種粗糙的解釋） –

我相信你應該繼續像下面正式獲得增長的複雜的算法的順序，使用數學（西格瑪符號）：

enter image description here

來源

2014-04-02 01:11:11

依賴嵌套for循環的時間複雜度？

回答

相關問題