嵌套循環漸近分析

Question

需要幫助找出這個例子出來的傢伙。 示例說明了0（n）運行時間。 我看到outter循環是O（logn） 我無法弄清楚如何描述與n有關的內部循環。 非常感謝幫助。

for (int i = 1; i <= N; i = i*2) // log n 
    for (int j = 0; j < i; j++) // less than n i don't know how to describe the growth 
     sum++; 

回答:: 0（n）的

Answer 1

分析聚合中代碼片段的運行時可能是最容易的。在外循環的第一次迭代中，內循環將運行1次。在外循環的第二次迭代中，內循環將運行2次。在外循環的第三次迭代中，內循環將運行4次。更一般地說，在外部循環的第k次迭代中，內部循環將運行2次^k次。一旦我變得大於N，外循環就會停止，這發生在N次迭代之後。

如果我們總結了所做的總功，我們會看到它的

1 + 2 + 4 + 8 + ... + 2 ^日誌ň = 2 ^{日誌 N + 1} - 1 = 2 - 1

（這使用的事實，1 + 2 + 4 + 8 + ... + 2 ^ķ = 2 ^{K + 1} - 1）。因此，整個代碼段（即包括兩個循環）所做的全部工作是O（n）。

Answer 2

內環是O（n）的時間，因爲它會經過每個元素一次。如果我是1000，1000次，如果我是10000，10000次等。