loops - 嵌套循环的复杂性

Question

我正在尝试使用 Big O 表示法计算 for 循环的复杂性。我之前在我的其他类(class)中也这样做过，但是这个比其他类(class)更严格，因为它是在实际算法上。代码如下:

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

和

for(i=1 ; i<=n;i++,x=1) //for any size n
{
    for(j = 1; j <= i; j++)
    {
      for(k = 1; k <= j; x+=a,k*=a)
      {

      }
    }
}

我发现第一个循环的复杂度为 O(n)，因为它要遍历列表 n 次。至于第二个循环我有点迷茫!
感谢您对分析的帮助。每个循环都在自己的空间中，它们不在一起。

Answer 1

考虑第一个代码片段，

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) .

现在考虑第二个代码片段，

for(i=1 ; i<=n; i++,x=1)
{
    for(j = 1; j <= i; j++)
    {
      for(k = 1; k <= j; x+=a,k*=a)
      {

      }
    }
}

两个外循环一起调用最内循环一共 n(n+1)/2次。最里面的循环最多执行 log<sub>a</sub>n次。因此，第二个代码片段的总时间复杂度为 O(n2logan) .