Порядок роста как наихудшего времени работы в зависимости от N

Учитывая следующий фрагмент кода:

int sum = 0;
for (int i = 1; i <= N; i++)
 for (int j = 1; j <= i*i; j++)
 for (int k = 1; k <= j*j; k++)
 sum++;

Мое предположение:

  • Внешний цикл: O (N)
  • Средняя петля: O (N * N)
  • Внутренний цикл: O (N * N)

Следовательно, общее время работы должно быть O (N ^ 5), правильно?

3 ответа

Предварительное замечание

sum(k=1,p,k^2) = p(p+1)(2p+1)/6 = O(p^3)
sum(k=1,p,k^6) = O(p^7)

Вычисление сложности

  • Самый внутренний цикл работает от k=1 до j^2, поэтому он выполняет операции j^2.
  • Средний цикл работает от j=1 до i^2, и на каждом шаге мы выполняем операции j^2. Согласно моему предварительному наблюдению, подставляя p=i^2 в первое уравнение, мы можем вычислить полные операции как: i^2(i^2+1)(2*i^2+1)/6 для каждого значения i. Это число операций O((i^2)^3) = O(i^6).
  • Внешний цикл работает от i=1 до n и выполняет операции O(i^6) на каждом шаге. Итак, у нас есть операции O(n^7).

Ссылки


Я думаю, что окончательный O определенно выше, чем O(n^4) и немного выше, чем O(n^5), но поскольку это нотация Big O, мы можем сказать, что она O (n ^ 5). Последний цикл будет выполнять это количество раз:

1 + 2^4 + 3^4 + 4^4 + ... + n^4

Wolframalpha представляет его как:

Обратите внимание на расширенную версию для n>0:

Edit:

Я только понял, что в моем ответе есть пробел, потому что большинство внутренних циклов будет выполняться больше раз, чем я предполагал. Глядя на результаты этой тройной петли и зачеркивая ее, она кажется выше, чем O(n^6). Вернемся к этому.

Изменить 2: Как я уже говорил, я был неправ. Не могу объяснить это лучше, чем @fjardon в ответе .


Позволяет открыть, сколько раз будет выполняться каждый цикл.

First loop 1, 2, 3, 4, 5, ...., N
Second loop 1, 4, 9, 16, 25, ...., (N*N) // N^2
Third loop 1, 16, 81, 256, 625, ...., ( (N*N)*(N*N) ) // N^4

Итак, я считаю, что сложность должна быть N ^ 4

РЕДАКТИРОВАТЬ 1

Основываясь на комментарии, я думаю, что сложность будет представлять собой сумму серии

1, 16, 81, 256, 625, ...., ( (N*N)*(N*N) )

РЕДАКТИРОВАТЬ 2

Я думаю, что мы допустили ошибку при открытии циклов (спасибо CodeYogi). Давайте попробуем еще раз.

First loop 1, 2, 3, 4, 5, ...., N
Second loop 1, 4(1,2,3, 4), 9 (1,2,....9), 16, 25, ...., (N*N) 
Third loop 1, 30(1+4+9+16), 285(1+4+...81), and so on..........

licensed under cc by-sa 3.0 with attribution.