Сложность следующего алгоритма

Question

Я пытаюсь найти сложность следующего алгоритма:

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

Answer 1

Так как ваше k начинается с «i» и идет до «j», сложность времени в худшем случае равна O (n ² ).Давайте возьмем пример и посмотрим.Для i = 4 j изменяется от 1 до 4, и k выполняется только один раз для каждого значения j (за исключением j = 4, которое выполняется ровно 2 раза). Поэтому для каждого значения j внутренний цикл выполняется в O (1ВремяВнешние две петли занимают время O (n ² ).Кроме того, учитывая, что ваш (// код) внутри самого внутреннего цикла выполняется за O (1) раз.Следовательно, временная сложность для этого алгоритма составляет O (n ² ) .