algorithm - 这段代码的复杂性是什么，它的嵌套 for 循环反复加倍它的计数器？

Question

在《Programming Interviews Exposed 》一书中，它说下面程序的复杂性是 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 +因为 for 是必需的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!

现在，斯特林公式告诉我们

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)

Answer 3

@Daniel Fischer 的回答是正确的。

我想补充一点，这个算法的确切运行时间如下：

意思是：