嵌套循环比率的复杂性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