嵌套循環比率的複雜性1/2

Question

我想弄清楚使用大O表示法的for循環的複雜性。我之前在其他課上做過這個，但是這個比其他課更加嚴格，因爲它是基於實際的算法。代碼如下：

for(i=n ; i>1 ; i/=2) //for any size n 
{ 
    for(j = 1; j < i; j++) 
    { 
     x+=a 
    } 
} 

執行指令x + = a總共n + n/2 + n/4 + ... + 1次。

G.P.的第一個log2n項的總和。開始項n和公共比率1/2是（n（1-（1/2）log2n））/（1/2）。因此第一個代碼片段的複雜度是O（n）。

是否正確？

Answer 1

是的，你是對的。但是，你並不需要涉及該對數，這是因爲：

n + n/2 + n/4 + ... + 1 = 2*n - 1 

（這個等式是精確的n個是2的冪和微客爲2無動力）

UPDATE：證明。

讓我們把我們的總和x：

x = n + n/2 + n/4 + ... + 1 

此外，爲了簡單起見，假設n是2的冪，所以所有成員都整除的2次方無餘。

如果通過2乘x，你會看到一些很有意思：

2*x = 2*n + 2*(n/2) + 2*(n/4) + ... + 2 

或者，您也可以重寫此爲：

2*x = 2*n + x - 1 

可以簡化爲：

x = 2*n - 1