loops - 嵌套循环的复杂度

Question

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

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 次。至于第二个循环，我有点失落！感谢您在分析中的帮助。每个循环都在自己的空间中，它们并不在一起。

score 2 · Accepted Answer

考虑第一个代码片段，

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几次。

具有起始项和共同比率的 GP 的第一个 log ₂ n 项的总和为( n (1-(1/2) ^log^₂ⁿ ))/(1/2)。因此，第一个代码片段的复杂度是O(n)。n1/2

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

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(n ² log _a n)。

score 1 · Accepted Answer

您可以像下面这样正式进行：

片段 1：

在此处输入图像描述

片段 2（Pochhammer、G 函数和斯特林近似）：

在此处输入图像描述

[片段 2 的更新]：

通过 Johann Blieberger 博士的“离散循环和最坏情况性能”出版物中的一些增强功能（所有情况均验证为a = 2）：

在此处输入图像描述

在哪里：

在此处输入图像描述

所以，

在此处输入图像描述

score 0 · Accepted Answer

编辑：我同意第一个代码块是O ( n )

您通过将外部循环减i2，并在内部循环中运行i时间，因此迭代次数将是小于或等于 N 但大于 0 的 2 的所有幂的总和，即 n ^{log( n)+1} - 1，所以O (n)。

第二个代码块是O (log _a (n)n ² )，假设a是一个常数。

最外面的两个循环等于所有小于或等于 n 的数字的总和，即 n(n-1)/2，因此O (n ² )。最后，内循环是 a 的幂次于 n 的上界，即O (log _a n)。

3 回答 3