Σ 从 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)?
我假设你的意思是 Σ 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
它是 O(n^3)。
要看到这是真的，您可以将其可视化为三角金字塔。
我们可以近似n(n+1)/2为n^2。所以我们的总和是1^2 + 2^2 + ... + n^2，也就是 n(n+1)(2n+1)/6，可以近似为n^3。所以上限是n^3。
求和的确切公式是1/6*n*(n+1)*(n+2)，即O(n^3)。
是的，在 k = 1,2,...,n 上对某个 d 次多项式求和，得到一个 d+1 次的 n 多项式。由于 k(k+1) / 2是 k 的 2 次，它的和是 n 的 2 + 1 = 3 次。
您是要求以下总和的计算复杂度，还是要求总和的大 O 界限？
第二个是 O(n^3)，就像人们已经注意到的那样，但是要计算总和，您只需要线性数量的加法和乘法。您可以重新组合加法并将总和重写为
n*1 + (n-1)*2 + ... + 1*n
很明显，总和可以在 O(n) 中计算。
哦，加雷斯注意到总和有一个封闭形式的表达式，它在恒定时间内计算。