Поиск Big O структуры вложенного цикла

У меня есть цикл, который выглядит примерно так, как показано ниже. Мне интересно найти Big O для этой структуры цикла.

for i = 1 to n { // assume that n is input size
                         ...
                         for j = 1 to 2 * i {
                             ...
                             k = j;
                                 while (k >= 0) {
                                     ...
                                     k = k - 1;
                                 }
                         }
               }

Из того, что я могу собрать:

  1. Цикл Outer-most работает «n» раз
  2. Второй цикл запускает «2n» раз (при условии, что размер приращения равен 1)
  3. Внутренний цикл работает в 2 раза

Так что, если Big O of n будет O (n ^ 3), или это будет что-то другое?

Будет оценена конкретная ссылка на такие проблемы и их решения.

algorithm,big-o,

-1

Ответов: 1


0 принят

Пусть I (), M (), T () - время работы для внутреннего цикла, среднего цикла и всей программы (внешний цикл). Если мы работаем изнутри, получаем:

Inner-most loop;
I(j) = Summation (1) //from k=0 to j
I(j) = j+1  //Using basic Summation expansion formula.

Middle loop
M(i) = Summation (I(j)) //from j=1 to 2i
M(i) = Summation (j+1)  //from j=1 to j=2i with I(j)'s values
M(i) = Summation (j) + Summation (1)  //both from j=1 to j=2i

Using the expansion formula for Summation (j) from j=1 to n is '(n(n+1)/2)' and the fact that Summation (1) from j=1 to n is 'n', we get:

M(i) = 2i^2 + 3i

Outer-most loop:

T(n) = Summation (2i^2 + 3i)  //Summation from i=1 to n
T(n) = Summation (2i^2) + Summation (3i)  //both summations from i=1 to n
T(n) = 2*Summation (2i^2) + 3*Summation (i)  //both summations from i=1 to n
T(n) = (2(2n^3 + 3n^2 + n))/6) + (3(n(n+1))/2)  //using summation expansion formulas
T(n) = (4n^3 + 15n^2 + 11n)/2

Which means Big O of n be T(n^3).

Примечание. Основные формулы расширения суммирования для суммирования можно найти на первой странице этой ссылки

Спасибо за подсказку @Paul Hankin

Алгоритм, большой-о,
Похожие вопросы