嵌套嵌套循环反复使计数器加倍的这段代码的复杂性是什么？

本文介绍了嵌套嵌套循环反复使计数器加倍的这段代码的复杂性是什么？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

在《暴露编程采访》一书中，该书说下面程序的复杂度为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).