большой алгоритм с вложенным циклом

Question

найти большую ой характеристику

input: n  

s<-0  
for i<-1 to n^2 do  
  for j<-1 to i do  
    s<-s+i

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

Answer 1

Внешние петли i от 0 до n^2, а внутренняя петля j от 1 до i.

Таким образом, внутренний цикл имеет сложность i (внутренний цикл требует i шагов, i меняется). Обозначим время выполнения внутреннего цикла IL(i)=i.

Чтобы получить общее время выполнения, мы видим, что внутренний цикл выполняется n^2 раз с переменным «параметром» i. Таким образом, мы получаем как общее время выполнения:

 n^2           n^2
----          ----
\     IL(i) = \    i 
/             /
----          ----
 i=1           i=1

То есть вы должны суммировать все числа от 1 до n^2. Есть много основных учебников, объясняющих, как это оценить.

Результат - (n^2)(n^2+1)/2, что приводит к общей сложности O(n^4).

Answer 2

Вы правы, ответ O(n^4). Первый внутренний цикл стоит i. Тогда внешний цикл стоит sum(1->p) i = p(p-1)/2, где p=n^2. Что дает стоимость O(n^4)

Answer 3

Ваш аргумент почти правильный.

Количество итераций цикла:

1 + 2 + ... + n^2 
= (n^2+1)*(n^2)/2
= (n^4 + n^2)/2

Таким образом, ответ Θ(n^4) (как примечание стороны такжеO(n^4)).

Формально это можно доказать, выбрав три константы c1, c2 и n0, такие что:

c1*n^4 <= (n^4 + n^2)/2 <= c2*n^4 forall n >= n0

Answer 4

Вы можете просто проверить формулу базовой суммы .Ваша сумма уходит не в N, а в N ^ 2, что дает вам

n^2(n^2+1)/2

, и это действительно O (n ^ 4)

Answer 5

Поскольку максимальное значение i равно n^2, это дает нам O(n^2) * O(n^2), что равно O(n^4).