嵌套嵌套循环反复使计数器加倍的这段代码的复杂性是什么？ [英] What is the complexity of this code whose nested for loop repeatedly doubles its counter?

问题描述

在《暴露编程采访》一书中，该书说下面程序的复杂度为O（N），但我不知道这是怎么可能的。

In the book Programming Interviews Exposed it says that the complexity of the program below is O(N), but I don't understand how this is possible. Can someone explain why this is?

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 + 是必需的，因为对于 i> = N / 2 ， [N /（i + 1）] = 1 和对数为0，但循环迭代一次）。 j 取值（i + 1）* 2 ^ k 直到它至少等于 N ，并且

You need a bit of math to see that. The inner loop iterates Θ(1 + log [N/(i+1)]) times (the 1 + is necessary since for i >= N/2, [N/(i+1)] = 1 and the logarithm is 0, yet the loop iterates once). j takes the values (i+1)*2^k until it is at least as large as N, and

(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 +上限（log_2（N /（i + 1）））次。这样我们就可以写出总工作量

using mathematical division. So the update j *= 2 is called ceiling(log_2 (N/(i+1))) times and the condition is checked 1 + ceiling(log_2 (N/(i+1))) times. Thus we can write the total work

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）。

so we find the total work done is indeed O(N).

这篇关于嵌套嵌套循环反复使计数器加倍的这段代码的复杂性是什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！