嵌套嵌套循环反复使计数器加倍的这段代码的复杂性是什么？
问题内容：
在《 暴露的编程访谈 》一书中，它说下面的程序的复杂度是O（N），但我不知道这怎么可能。有人可以解释为什么吗？
int var = 2;
for (int i = 0; i < N; i++) {
for (int j = i+1; j < N; j *= 2) {
var += var;
}
}
问题答案：
您需要一点数学才能看到。内部循环迭代Θ(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)。
