为什么像 i=i*2 这样的代码在循环中被认为是 O(logN)？

Question

为什么因为 i=i*2，下面循环的运行时间被认为是 O(logN)？

for (int i = 1; i <= N;) {
  code with O(1);
  i = i * 2;
}

Answer 1

看1024=2¹⁰。您需要将数字 1 加倍多少次才能得到 1024？

Times    1   2   3   4    5    6    7    8     9      10
Result   2   4   8   16   32   64  128  256   512    1024

所以你必须运行你的加倍循环十次才能得到 2¹⁰ 通常，你必须运行你的加倍循环 n次得到 2ⁿ。但是n是什么？它是 log₂ 2ⁿ，所以一般来说如果 n 是 2 的某个幂，循环必须运行 log₂n次到达。

Answer 2

要在 O(logN) 中使用算法，对于任何 N 都需要（大约）log N 步。在 N=32 的示例中（其中 log 32 = 5），可以看到：

i = 1 (start)
i = 2
i = 4
i = 8
i = 16
i = 32 (5 iterations)
i = 64 (abort after 6 iterations)

一般来说，在 x 次迭代后，i=2^x 成立。要达到 i>N，您需要 x = log N + 1.

PS：在谈论复杂性时，log 基数 (2, 10, e, ...) 是不相关的。此外，如果您有 i <= N 或 i < N 则无关紧要，因为这只会将迭代次数更改一次。

Answer 3

i 从 1 开始。在每次迭代中，您将 i 乘以 2，因此在 K-th 迭代中，i 将是 2^K-1.

经过K次迭代后，2^K-1会大于（或到）N.

这意味着N≤2^K-1

这意味着 log₂(N) ≤ K-1

K-1 将是循环的迭代次数运行，并且由于 K-1 更大或等于 log(N)，你的算法是对数的。

Answer 4

你可以很简单地证明它。

索赔：对于第 t 次（0 基）迭代，i=2^t 通过归纳法证明。

基础：2^0 = 1，实际上在第一次迭代中，i=1。

步骤：对于某些t+1，i的值是2*i(t)（其中i(t)是[=10=中i的值=] 迭代）。从归纳假设我们知道 i(t)=2^t，因此 i(t+1) = 2*i(t) = 2*2^t = 2^(t+1)，并且声明成立。

现在，让我们检查一下我们的停止标准。我们迭代循环 while i <= N，根据上面的说法，这意味着我们迭代 while 2^t <= N。通过在两侧执行 log_2，我们得到 log_2(2^t) <= log_2(N)，并且由于 log_2(2^t) = t，我们得到我们在 t <= log_2(N) 时迭代 - 所以我们迭代 Theta(log_2(N)) 次。（证明到此结束）。

为什么像 i=i*2 这样的代码在循环中被认为是 O(logN)？

Why is code like i=i*2 considered O(logN) when in a loop?

big-o

logarithm

time-complexity