Большая сложность вложенных циклов

Меня смущает сложность следующего (операция, выполняемая внутри внутреннего цикла, выполняется в постоянное время):

Псевдокод:

for i = 1 to n
   for j = i to n
      for k = i to j
         x := x + 1;
      end for
   end for
end for;

Код:

for(i=1;i<=n;i++) {   
    for(j=i;j<=n;j++) {
        for(k=i;k<=j;k++) {
           x = x + 1;
        }
    }
}

O(n^3) ?


c nested-loops big-o complexity-theory
person user2151641    schedule 14.03.2013    source источник
comment
Не могли бы вы правильно отформатировать код? А в идеале перевести?   -  person djechlin    schedule 15.03.2013
comment
И, честно говоря, вам нужно прочитать whathaveyoutried.com. Я могу придумать дюжину идей, которые вам могут понадобиться для начала, и не думаю, что это большая честь помочь вам избежать этого.   -  person djechlin    schedule 15.03.2013

Ответы (2)


arrow_upward
1
arrow_downward

O(n^3) ???

Да, даже если вы не удосужились перевести домашнюю работу с французского.

person Community    schedule 14.03.2013
comment
как я могу получить O (n ^ 2)? - person user2151641; 15.03.2013
comment
@ user2151641 Избавившись от одной из петель? - person ; 15.03.2013
comment
как я могу рассчитать это с сигмой? - person user2151641; 15.03.2013
comment
O (n * n * n), что равно O (n ^ 3). Стоимость умножается, потому что она вложена. Если бы они были рядом, а не вложенными, это стоило бы O(3n) или O(n) стоимости. Это основные алгоритмы 101. - person Apollo SOFTWARE; 15.03.2013
comment
Вы уверены, что это O (n ^ 3)? Циклы не начинаются с 0, и не все они доходят до n? - person Nashibukasan; 15.03.2013
comment
@Nashibukasan Есть причина, по которой асимптотическая сложность называется < b>асимптотический и не идентичный... - person ; 15.03.2013
comment
@H2CO3 Спасибо! Я сам запутался. - person Nashibukasan; 15.03.2013

arrow_upward
0
arrow_downward

Это продукт O(outer loop in outer loop control) * O(inner loop in inner loop control).

person djechlin    schedule 14.03.2013