это выражение O (n ^ 2) или O (n ^ 3)?

Question

Sum [(i + 1) (n - i), {i, 0, n - 1}]

, то есть сумма (i + 1) (n-1) с оценками изя = 0 до п-1.

это O (n ^ 2) или O (n ^ 3)?а можешь объяснить как ты это нашел?спасибо.

Answer 1

Разверните и используйте выражения для замкнутой формы для суммы (i ^ k).

(i + 1)(n - i) = n * i - i * i + n - i

так что

sum[(i + 1)(n - i)] = sum(n * i) - sum(i * i) + sum(n) - sum(i)
                    = n * sum(i) - sum(i * i) + n * n - sum(i)
                    = (details elided)
                    = O(n^3).

На шаге "детализация исключена" разверните каждую сумму до ее выражения в закрытой форме и обратите внимание, что коэффициент n^3 не равен нулю (это 1 / 6).

Answer 2

Вольфрам | Альфа ест их на обед:

http://www.wolframalpha.com/input/?i=Sum%5B(i+%2B+1)+(n+-+i),+%7Bi,+0,+n+-+1%7D%5D

Answer 3

Если вы говорите о времени, необходимом для оценки суммы, то это O (1) (потому что оно может быть сведено к формуле замкнутой формы). Если вы говорите о самой формуле, то разверните ее и подставьте суммы степеней, и вы увидите, что коэффициент n ^ 3 (который имеет наивысшую степень) не равен 0.

В любом случае, O (n ^ 2) - это подмножество O (n ^ 3), поэтому ... когда вы спрашиваете, O (n ^ 2) или O (n ^ 3), простой ответ: O (n ^ 3) (если вы знаете, что ответ никогда не может быть "ни").