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

Question

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

基于这个问题:Runtime analysis , if 语句中的 for 循环将运行 n*n 次。但在这段代码中，j 超过了 i，因此一旦运行第二个循环，j = i^2。那么这使得第三个 for 循环的时间复杂度是多少呢？我知道第一个 for 循环运行 n 次，第二个运行 n^2 次，第三个运行 n^2 次并触发一定次数。因此，复杂度将由 n*n^2(xn^2) 给出，其中 n 是 if 语句为真的次数。复杂性不仅仅是 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

当j 是i 的倍数时，if 条件为真；当 j 从 0 到 i * 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
            }
        }
    }
}