什么是这个代码，其嵌套的循环中重复加倍其计数器的复杂性？(What is the complexit

在这本书中的编程面试攻略它说，下面的程序的复杂度为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公式告诉我们

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

所以我们发现所做的总功确实是O(N)

Answer 2:

外部循环运行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)