小编Ger*_*erk的帖子

我现在正在学习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# =