Временная сложность вложенных циклов с операторами if

Question

Как оператор if этого кода влияет на временную сложность этого кода?

Исходя из этого вопроса: Анализ времени выполнения , цикл for в операторе if будет выполняться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

Условие 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
            }
        }
    }
}

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