模数的时间复杂度分析

Question

 sum = 0;
 for(i=1;i<2*n;i++)
    for(j=1;j<i*i;j++)
      for(k=1;k<j;k++)
        if (j % i == 1)
          sum++;

我需要用大O表示法来计算这段代码的时间复杂度.我理解如何在非常基础的层面上分析时间复杂度.我的问题是最终内循环中的条件.如何将其集成到我的分析中？

Answer 1

 sum = 0;
 for(i=1;i<2*n;i++)
    for(j=1;j<i*i;j++)
      for(k=1;k<j;k++)
        if (j % i == 1)
          sum++;

所以:

• i从去1到2n,因此这是O(n).
• j从去1到i^2,因此这是O(n^2).
• k具有相同的值j,因此它是O(n^2).

其他一切都是恒定的时间.所以最后的复杂性是O(n^5).