这个代码的复杂性是什么,它的嵌套for循环反复使其计数器加倍？

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!

现在,斯特林的公式告诉我们

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

所以我们发现完成的工作确实是O(N).