Большой вопрос O - Алгоритмический анализ II

Question

Я задаю вопрос, в котором просим найти сложность вложенного цикла for, упрощенного с использованием записи больших О.

Вопрос:

for i <- 1 to n do
    for j <- 1 to n do
        for k <- 1 to (i+j) do
            a unit cost operation

Я ДОЛЖЕН доказать вышеизложенноеиспользуя сумму обозначений серии.Я вроде понял концепцию и дал ей трещину.Я просто хочу знать, правильно ли я это делаю или нет.

Вот мой ответ:

** Предположим, что сумма (x = i, y) - это заглавная сигма нотация с x какнижняя граница и y как верхняя граница.

=> сумма (i = 1, n) сумма (j = 1, n) сумма (k = 1, i + j) 1=> сумма (i = 1, n) сумма (j = 1, n) (i + j)=> сумма (i = 1, n) n * i => n * сумма (i = 1, n) i

подраздел в правиле для суммы арифметических рядов дает: => n * n / 2 (n + 1) => (n ^ 3 + n ^ 2) / 2

с использованием большого правила О -> max (f (x), g (x)): => max (n ^ 3 /2, n ^ 2/2) => O (n ^ 3)

Я знаю, что ответ правильный, но не уверен, что мои расчеты до этого были ....

Answer 1

С небольшой поправкой:

  sum(i=1, n) sum(j=1, n) sum(k=1, i+j) 1
= sum(i=1, n) sum(j=1, n) (i+j)
= [ sum(i=1, n) sum(j=1, n) i ] + [ sum(i=1, n) sum(j=1, n) j ]
=   sum(i = 1, n) n*i           +   sum(i=1, n) n*(n+1)/2 
=   n * sum (i = 1, n) i        +   n * n * (n+1) / 2
=   n * n * (n+1) / 2           +   n * n * (n+1) / 2
=   n * n * (n+1)
=   n^3 + n^2
=   O( max(n^3, n^2) )           <--- as you correctly say
=   O(n^3)

На самом деле, это Θ(n^3)

---

Вы также можете использовать это i+j <= 2*n:

   sum(i=1, n) sum(j=1, n) sum(k=1, i+j) 1
=  sum(i=1, n) sum(j=1, n) (i+j)
<= sum(i=1, n) sum(j=1, n) 2*n
=  2*n * sum(i=1, n) sum(j=1, n) 1
=  2 * n^3
=  O(n^3)

Answer 2

Прямо и формально (и эмпирически проверено) с c -> операция за единицу стоимости :