algorithm - 什么是总和？

Question

Σ 从 i=1 到 n of(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)(2n + 1)/6 + n(n + 1)/2)

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

OEIS将这些数字(1、4、10、20、...)称为“tetrahedral numbers”。