Какова сумма суммы?

Question

Σ от i = 1 до n из (n) (n + 1) / 2

Каков верхний предел вычисления для данного n?это O (n ^ 3) O (n ^ 2)?

Пример:

n=1 , sum =1
n=2 , sum= 1+ 1+2 ,   sum = 4
n=3, sum= 1+1+2+1+2+3, sum = 10
n=4, sum = 1 + 1+2 + 1+2+3 + 1+2+3+4 = 20
n= 5, sum = 1+ 1+2 +1+2+3 +1+2+3+4 + 1+2+3+4+5 , sum = 35 
...
n=10,  sum = ..... , sum = 220 

и т. д., какова верхняя граница этого вычисления как функция от N?это:

O (n ^ 3)?

Answer 1

Полагаю, вы имеете в виду Σ _{1 ≤ i ≤ n} i ( i + 1)/ 2, поскольку Σ _{1 ≤ i ≤ n} n ( n + 1) / 2 просто n ² ( n + 1) / 2, что, я уверен, вы могли увидеть сами.

В любом случае, почему вы должны мириться с простой асимптотикой?темпы роста, когда вы можете вычислить сумму точно?

Σ _{1 ≤ i ≤ n} i ( i + 1) / 2

= ½ Σ _{1 ≤ i ≤ n} ( i ² + i )

= ½ ( n ( n + 1) (2 n +1) / 6 + n ( n + 1) / 2)

= n ³ / 6 + n ² / 2 + n / 3

OEIS называет эти номера (1, 4, 10, 20, ...) "" тетраэдрических чисел".

Answer 2

Это O (n ^ 3).

Чтобы увидеть, что это правда, вы можете представить его как треугольную пирамиду.

Answer 3

Мы можем приблизить n(n+1)/2 к n^2. Таким образом, наша сумма равна 1^2 + 2^2 + ... + n^2, а это n(n+1)(2n+1)/6, что может быть приблизительно равно n^3 Таким образом, верхняя граница составляет n^3.

Answer 4

Точная формула для суммы 1/6*n*(n+1)*(n+2), что O(n^3).

Answer 5

Вы запрашиваете сложность вычислений следующей суммы или big-O bound для суммы?

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

n*1 + (n-1)*2 + ... + 1*n

, откуда ясно, что сумма может быть вычислена в O (n).

О, и Гарет отметил, что естьвыражение в закрытой форме для суммы, которая вычисляется в постоянном времени.

Answer 6

Да, суммирование некоторого многочлена степени d по k = 1,2, ..., n дает многочлен от n степени d + 1. Поскольку k(k+1) / 2 имеет степень 2 в k, его сумма имеет степень 2 + 1 = 3 в n.