在《 暴露的编程访谈 》一书中，它说下面的程序的复杂度是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，并且
Θ(1 + log [N/(i+1)])
1 +
i >= N/2
[N/(i+1)] = 1
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)))时间。这样我们就可以写出全部工作
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)。
O(N)
