嵌套循环的复杂性 [英] complexity for nested loops

问题描述

我正试图找出使用Big O表示法的for循环的复杂性.我之前在其他课程中都做过，但是这个课程比其他课程更为严格，因为它在实际算法中.代码如下:

I am trying to figure out the complexity of a for loop using Big O notation. I have done this before in my other classes, but this one is more rigorous than the others because it is on the actual algorithm. The code is as follows:

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

I have arrived that the first loop is of O(n) complexity because it is going through the list n times. As for the second loop I am a little lost! Thank you for the help in the analysis. Each loop is in its own space, they are not together.

推荐答案

考虑第一个代码片段，

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.的前log ₂ n个项的总和.起始项n和公共比率1/2为，(n(1-(1/2) ^{log ₂ n} ))/(1/2).因此，第一个代码片段的复杂度为 O(n).

Sum of the first log₂n terms of a G.P. with starting term n and common ratio 1/2 is, (n (1-(1/2)^log₂n))/(1/2). Thus the complexity of the first code fragment is O(n).

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

Now consider the second code fragment,

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

The two outer loops together call the innermost loop a total of n(n+1)/2 times. The innermost loop is executed at most log<sub>a</sub>n times. Thus the total time complexity of the second code fragment is O(n²log_an).

这篇关于嵌套循环的复杂性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！