带有 if 语句的嵌套 for 循环的时间复杂度

Question

这段代码的 if 语句如何影响这段代码的时间复杂度？

基于这个问题：运行时分析，if 语句中的 for 循环将运行 n*n 次。但是在这段代码中，j超过了i所以一旦第二个循环运行j = i^2。那么第三个 for 循环的时间复杂度是什么？我知道第一个 for 循环运行 n 次，第二次运行n^2次数，第三次运行n^2时触发一定次数。因此，复杂性将被给予n*n^2(xn^2)了这n是，如果声明是真实的次数。复杂性不仅仅是O(n^6)因为 if 语句不是真的 n 次对吗？

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

Answer 1

在if当条件为真j是的倍数i; 这发生的i次数j从 0 到i * i，所以第三个for循环只运行i几次。整体复杂度为 O(n^4)。

for (int i = 1; i < n; i++)
{
  for (int j = 0; j < i*i; j++)       // Runs O(n) times
    {
      if (j % i == 0)                 // Runs O(n) × O(n^2) = O(n^3) times
        {
          for (int k = 0; k < j; k++) // Runs O(n) × O(n) = O(n^2) times
            {
              sum++;                  // Runs O(n^2) × O(n^2) = O(n^4) times
            }
        }
    }
}