以下算法的时间复杂度？

Question

我现在正在学习大 O 表示法，在另一个线程中偶然发现了这个小算法：

i = n
while (i >= 1)
{
    for j = 1 to i  // NOTE: i instead of n here!
    {
      x = x + 1
    }
    i = i/2
}

根据post的作者，复杂度是Θ(n)，但我想不通。我认为 while 循环的复杂度是 Θ(log(n))。我想的for循环的复杂度也是Θ(log(n))，因为每次迭代次数都会减半。

那么，整个事情的复杂度不会是 Θ(log(n) * log(n))，还是我做错了什么？

编辑：该段是这个问题的最佳答案：

Answer 1

while循环每次迭代的i的值，也就是for循环有多少次迭代，分别是n,n/2,n/4, ..., 总体复杂度是这些的总和。这使得它大约为 2n，这让你得到你的 Theta(n)。

Answer 2

为简单起见，假设 n = 2^k。 x 递增了多少次？很容易得出这是 Geometric series

2^k + 2^(k - 1) + 2^(k - 2) + ... + 1 = 2^(k + 1) - 1 = 2 * n - 1

所以这部分是Θ(n)。 i 也减半 k = log n 次并且它对 Θ(n).

没有渐近效应

Time complexity of the following algorithm?