big-o - 带模的时间复杂度分析

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