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

Question

Мне нужна помощь:

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

Я понимаю, как петли i и j равны O (n ^ 4). Но, начиная с оператора if, я не знаю, что такое Big O оставшегося фрагмента кода. Если я правильно скопировал ответ в классе, O (n ^ 4) - это время выполнения всего фрагмента кода. Таким образом, время запуска, начиная с if, кажется незначительным. В общем, я все еще хотел бы понять, что это такое и почему я принял ответ за O (n ^ 5).

Answer 1

O (n ^ 4) - правильный ответ. Первые два цикла имеют O (n ^ 4) временную сложность. Для части кода, начинающейся с оператора 'if', сложность равна O (n ^ 3), так как 'i' и 'j' равны ровно n * n раз, и есть еще один цикл for, который увеличивает временную сложность до O (n ^ 3). Следовательно, O (n ^ 4) + O (n ^ 3) = O (n ^ 4)

Answer 2

Общая сложность вашего кода на самом деле O(n^4), а не O(n^5). Условие i == j будет выполняться один раз для каждого значения в диапазоне двух внешних циклов в i и j. Поскольку в каждом из этих циклов есть n^2 возможных значений, i == j произойдет n^2 раз. Каждый раз, когда это происходит, в k существует третий цикл, который будет повторяться n раз. Таким образом, каждый раз, когда происходит i == j, будет O(n) штраф. В целом, это проявляется как O(n^3) событие, которое снижает производительность O(n^4) двух внешних циклов.

Следовательно, , поведение вашего фрагмента кода по-прежнему O(n^4), несмотря на условие i == j.