Время выполнения вложенных циклов (Big O)

Question

Каково время работы этого алгоритма:

for i=1 to n^2
    for j=1 to i
        // some constant time operation

Я хочу сказать O (n ^ 4), но не могу быть уверен.Как вы это выясните?

Answer 1

n ^ 4 правильно.Внутренний цикл занимает в среднем (n ^ 2) / 2 времени для запуска, потому что i линейно возрастает до n ^ 2, и он запускается (n ^ 2) раз.

Answer 2

Операция с постоянным временем выполняется:

  1 + 2 + 3 + ... + n^2        (n^2 adders)

раза, что меньше:

  n^2 + n^2 + ... + n^2        (n^2 adders)
= n^2 * n^2
= n^4

Итак, это очевидно O(n^4)

---

Чтобы доказать, что это Θ(n^4), вы можете использовать liitle math:

   1 + 2 + 3 + ... + n^2   
 = n^2 * (n^2 + 1) / 2
 = n^4 / 2 + n^2 / 2
>= n^4 / 2

Answer 3

Вы правы, это N^4.

Выполните подстановку M = N^2.Теперь ваши циклы изменяются на:

for i in 0..M
    for j in 0..i

Это ваш знакомый O(M^2), следовательно, результат будет O((N^2)^2) = O(N^4) после обратной замены.

Answer 4

Используя сигма-нотацию, вы получите методический порядок роста:

Answer 5

С вложенными циклами Big Oh мультипликативное время выполнения. Таким образом, Большой О внешнего цикла (N ^ 2) умножается на Большой О внутреннего (N ^ 2). Следовательно, Большой О есть (N ^ 2 * N ^ 2), и если вы помните, как добавлять показатели аналогичной базы, вы получите N ^ (2 + 2) или N ^ 4.

Answer 6

n^5 = outer * inner
outer = n^2
inner = n^2 + n^2-1 + n^2-2 +...1