c - 嵌套循环的复杂度比例为1/2

This question already has answers here:

Closed 6 years ago.

Complexity for nested loops dividing by 2
（3个答案）
我试图用一个大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）。
对的？

最佳答案

是的，你是对的。但是，不需要使用对数，因为：

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

（这个方程对于n是2的幂，而对于非2的幂，这个方程是精确的）
更新：证据。
我们把总数称为：

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

另外，为了简单起见，假设n是2的幂，所以所有成员都可以被2的幂除，没有余数。
如果你把x乘以x，你会看到一些非常有趣的东西：

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

或者，可以将其重写为：

2*x = 2*n + x - 1

可以简化为：

x = 2*n - 1

关于c - 嵌套循环的复杂度比例为1/2 ，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/16887989/