以下算法的時間複雜度？

Question

我學習大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增加了多少次？它容易追隨這是Geometric series

2^K + 2 ^（K - 1）+ 2 ^（K - 2）+ ... + 1 = 2 ^（K + 1） - 1 = 2 * n - 1

所以這部分是Θ(n)。 i得分減半k = log n次，它對Θ(n)沒有漸近效應。

Answer 2

的i爲while循環，這也是多少次迭代的for循環具有的每個迭代的值，爲N，n/2，n/4，...，總體複雜度是這些的總和。這使它在大約2n，這讓你的Theta（n）。