Почему этот код считается O (N ^ 6) в обозначении Big Oh?

Question

Я просто читал другой вопрос , и этот код заинтриговал меня:

for(i = 0; i < n; i++)
{
    for(j = 0; j < i*i; j++)
    {
        for(k = 0; k < i*j; k++)
        {
            pseudo_inner_count++;
            for(l = 0; l < 10; l++);
        }
    }
}

Я не понимаю, как это может быть O (N ^ 6). Может кто-нибудь сломать это для меня?

Answer 1

На самом деле это:

• Цикл i повторяется O (N) раз, поэтому значение i равно O (N), поэтому мы можем сказать O (I) = O (N).
• Цикл j повторяется O (I ^ 2) = O (N ^ 2) раз (если рассматривать его самостоятельно, без внешнего цикла).
• K-цикл повторяет O (I * J) = O (N * N ^ 2) = O (N ^ 3) раз.
• Цикл l просто повторяется 10 раз, так что это O (1).

Циклы являются вложенными, поэтому мы должны умножить их вместе (вы понимаете, почему?). Итого: O (N) * O (N ^ 2) * O (N ^ 3) = O (N ^ 6).

Answer 2

Это

n для первого цикла n² для второго цикла n³ для третьего цикла

Внутренний цикл O (1)

Итого O (n⁶).

Причина, по которой третий цикл равен n³, заключается в том, что когда вы думаете об этом, j достигает n², а i достигает n, поэтому i * j достигает n³.

Answer 3

Я бы сказал:

• n для первого цикла
• n² для второго цикла => всего n³
• n² для третьего цикла => всего n⁵
• еще один n-цикл => всего n⁶