c - 嵌套循环除以 2 的复杂度

Question

我正在尝试使用 Big O 表示法找出 for 循环的复杂性。我以前在我的其他课程中也这样做过，但是这个比其他的更严格，因为它是在实际算法上的。代码如下：

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

我已经知道第一个循环是 O(log_2(n))。至于第二个循环，我有点失落！感谢您在分析中的帮助。

score 4 · Accepted Answer

要正式解决算法的时间复杂度，您可以使用以下带有 Sigma 表示法的步骤：

在此处输入图像描述

另外，请看一下Jauhar 博士撰写的这份非常有趣的文档的最后一张幻灯片。

score 3 · Accepted Answer

3

内循环的总迭代次数为 n + n/2 + n/4 + ... + 1，约为 2n。所以复杂度是O(n)。

于 2013-05-25T10:09:34.980 回答

score 3 · Accepted Answer

复杂度应该是O(n). 它形成了一个几何级数（不完全而是近似）。

循环运行的n+ n/2 + n/4 + .... +1时间约为2n。

和O(2n) = O(n)。

3 回答 3