以下算法的时间复杂度？

Question

我现在正在学习Big-O表示法,并在另一个线程中偶然发现了这个小算法:

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

根据该帖子的作者,复杂性是Θ(n),但我无法弄清楚如何.我认为while循环的复杂性是Θ(log(n)).for循环的复杂性从我的想法也将是Θ(log(n)),因为迭代次数每次都会减半.

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

编辑:该段是这个问题的最佳答案:https://stackoverflow.com/questions/9556782/find-theta-notation-of-the-following-while-loop# =

Answer 1

为简单起见，想象一下n = 2^k。x增加了多少倍？很容易看出这是几何系列

\n\n

\n

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

\n

\n\n

所以这部分是\xce\x98(n)。也i得到减半的k = log n时间，并且它对 没有渐近效应\xce\x98(n)。

\n