c - 嵌套循环的复杂性比率 1/2

Question

我正在尝试使用 Big 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 次。

具有起始项 n 和共同比率 1/2 的 GP 的第一个 log2n 项之和为 (n (1-(1/2)log2n))/(1/2)。因此，第一个代码片段的复杂度为 O(n)。

正确的？

score 3 · Accepted Answer

是的，你是对的。但是，您不需要为此涉及对数，因为：

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

（这个等式对于 n 是精确的，即 2 的幂，对于非 2 的幂稍有偏差）

更新：证明。

让我们调用我们的 sum x：

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

此外，为简单起见，假设 n 是 2 的幂，因此所有成员都可以被 2 的幂整除而没有余数。

如果你乘以x，2你会看到一些非常有趣的东西：

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

或者，您可以将其重写为：

2*x = 2*n + x - 1

可以简化为：

x = 2*n - 1

1 回答 1