Сумма [(i + 1) (n - i), {i, 0, n - 1}]- это выражение O (n^2) или O (n^3)?
, которая представляет собой сумму (i + 1) (n-1) с ограничениями от i = 0 до n-1.
является то, что O (n^2) или O (n^3)? и не могли бы вы объяснить мне, как вы его нашли? Благодарю.
Развернуть и использовать выражения замкнутой формы для суммы (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) ,
Если вы говорите о времени, необходимом для оценки суммы, то это O (1) (потому что его можно свести к формуле замкнутой формы). Если вы говорите о самой формуле, затем разверните ее и замените суммы энергии, и вы увидите, что коэффициент n^3 (который имеет наивысшую степень) не равен 0.
В любом случае, O (n^2) является подмножеством O (n^3), поэтому при задании O (n^2) или O (n^3) легко ответить, что O (n^3) (если вы знаете, что ответ никогда не может быть «ни»).
Wolfram | Альфа ест их на обед:
http://www.wolframalpha.com/input/?i=Sum%5B(i+%2B+1)+(n+-+i),+%7Bi,+0,+n+-+1%7D%5D
Ваш вопрос непоследовательно заявил, я думаю. Является ли слагаемое `(i + 1) (n-i)` или `(i + 1) (n-1)`? – 2010-12-08 01:47:30
Возможный дубликат [мне нужно найти верхнюю границу этого: или ограниченную привязку:] (http://stackoverflow.com/questions/4382014/i-need-to-find-the-upper-bound-of-of- эта-или-тесная привязка) – Beta 2010-12-08 04:11:42