Что такое Big-O вложенного цикла, где внешний цикл равен n ^ 2

for(int i = 1; i < n **2; i++) 
{    
   for(int j = 1; j < i; j++)    
   {
     s = s;    
   } 
}

Поскольку большой O внешнего цикла равен O (n ^ 2), будет ли он по-прежнему умножаться на внутренний цикл, делая общее обозначение Big O равным n (n ^ 2) -> O (n ^ 3)?


nested-loops big-o
person ryandonohue    schedule 28.09.2015    source источник
comment
Если вы измените условие внутреннего цикла на j < n, у вас будет алгоритм O (n ^ 3).   -  person user2023861    schedule 28.09.2015

Ответы (1)


arrow_upward
1
arrow_downward

Во внешнем цикле я могу принимать значения от 1 до n^2. Затем для каждого из этих значений внутренний цикл переходит от 1 к i. Количество операций, выполняемых для i=1, равно 1, i=2 равно 2, ..., i = n^2 равно n^2.

Таким образом, общее количество операций равно сумме i от 1 до n^2 числа i. Это хорошо известная серия, имеет замкнутую форму (n ^ 2) (n ^ 2 + 1)/2, то есть O (n ^ 4)

person Chad S.    schedule 28.09.2015
comment
Хорошо, поэтому я продолжаю, пока вы не сделаете две функции, умноженные вместе на два. Почему вы делите на два в этом случае? - person ryandonohue; 28.09.2015
comment
@ryandonohue Чед суммирует все числа от 1 до n^2. Формула для суммирования таких чисел: n(n+1)/2. cseweb.ucsd.edu/groups/tatami/kumo/exs/sum Вот откуда взялось деление на два. - person user2023861; 28.09.2015
comment
Я отредактировал, чтобы включить ссылку на соответствующую серию, но вы также можете подумать об этом сами. Если вы возьмете первую половину ряда (1, 2, 3,...) и добавите ее ко второй половине (n^2, n^2-1, n^2-2,...), что вы в итоге получается (n^2/2)(n^2+1), что является другим способом записи (n^2)(n^2+1)/2 - person Chad S.; 28.09.2015