這段代碼的複雜性是多少？

Question

在書編程訪談暴露它說，下面的程序的複雜性是O（N），但我不明白這是如何可能的。有人可以解釋爲什麼這是嗎？

int var = 2; 
for (int i = 0; i < N; i++) { 
    for (int j = i+1; j < N; j *= 2) { 
     var += var; 
    } 
} 

Answer 1

你需要一點數學才能看出來。內循環迭代Θ(1 + log [N/(i+1)])次（1 +是必要的，因爲對於i >= N/2,[N/(i+1)] = 1和對數爲0，但該循環迭代一次）。 j所採用的值(i+1)*2^k直到它至少爲N一樣大，並且

(i+1)*2^k >= N <=> 2^k >= N/(i+1) <=> k >= log_2 (N/(i+1)) 

使用數學除法。所以更新j *= 2被稱爲ceiling(log_2 (N/(i+1)))時間和條件檢查1 + ceiling(log_2 (N/(i+1)))次。因此，我們可以寫工作總

N-1         N 
∑ (1 + log (N/(i+1)) = N + N*log N - ∑ log j 
i=0         j=1 
         = N + N*log N - log N! 

現在，Stirling's formula告訴我們

log N! = N*log N - N + O(log N) 

所以我們發現所做的總功確實是O(N)。

Answer 2

@Daniel Fischer的回答是正確的。

我想補充的是，這個算法的準確運行時間如下：

這意味着：

Answer 3

外部循環運行n倍。現在全部取決於內部循環。
內循環現在是棘手的。

讓我們遵循：

i=0 --> j=1    ---> log(n) iterations 
... 
... 
i=(n/2)-1 --> j=n/2  ---> 1 iteration. 
i=(n/2) --> j=(n/2)+1 --->1 iteration. 

---

i > (n/2)   ---> 1 iteration 
(n/2)-1 >= i > (n/4) ---> 2 iterations 
(n/4) >= i > (n/8) ---> 3 iterations 
(n/8) >= i > (n/16) ---> 4 iterations 
(n/16) >= i > (n/32) ---> 5 iterations 

(n/2)*1 + (n/4)*2 + (n/8)*3 + (n/16)*4 + ... + [n/(2^i)]*i 

    N-1         
n*∑ [i/(2^i)] =< 2*n 
    i=0 

--> O(n)