使用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语句为true的次数。复杂度不是简单的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从0变为j时，发生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
            }
        }
    }
}

Answer 2

复杂度不是简单的O（n ^ 6），因为if语句不是n次正确的对吗？

不，不是。

[最坏的情况是O(n^5)。由于j % i仅等于0次i，因此它小于此值。

第一个循环运行n次。第二个循环运行O(n^2)次。第三个循环最多运行O(n)次。

循环的最坏组合复杂度将是O(n) x O(n^2) x O(n)，即O(n^4)。