總和是多少？

Σ從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）？

來源

2010-12-05 sam

通過積分2級多項式（即`n²`）近似得到`n³`。 – Dario 2010-12-05 20:07:54

我假定你指Σ_1≤我≤Ñ我（我 + 1）/ 2，由於Σ_1≤我≤ÑÑ （ n + 1）/ 2只是n²（ n + 1）/ 2，我相信你可以親眼看到它。

無論如何，當你可以精確計算總和時，爲什麼你應該忍受僅僅漸近增長率？

Σ_1≤我≤Ñ我（我 + 1）/ 2

=½Σ_1≤我≤Ñ（i 2 + i）

=½（Ñ（Ñ + 1）（2 Ñ + 1）/ 6 + Ñ（Ñ + 1）/ 2）

= Ñ³/ 6 + ñ²/2 + ñ/3

的OEIS調用這些數字（1，4，10，20，...）中的「tetrahedral numbers「。

來源

2010-12-05 20:17:59

它是O（n^3）。

要看到這是真的，你可以把它想象成一個三角形金字塔。

alt text

來源

2010-12-05 20:04:33

我們可以近似n(n+1)/2到n^2。所以我們的總和是1^2 + 2^2 + ... + n^2，那就是n(n+1)(2n+1)/6，可以近似爲n^3。所以上限是n^3。

來源

2010-12-05 20:06:02

是，對k = 1,2，...，n上的次數爲d的多項式求和，得到次數爲n + 1的多項式。由於k(k+1)/2在k中的次數爲2，所以其總和在n中的次數爲2 + 1 = 3。

來源

2010-12-05 20:06:29

總和的確切公式爲1/6*n*(n+1)*(n+2)，即O(n^3)。

來源

2010-12-05 20:18:18 NPE

您是否要求的計算複雜度爲以下總和，還是爲big-O bound求和？

第二個是O（n^3），就像人們已經注意到的，但是對於計算總和你只需要線性數量的加法和乘法。您可以重新組合加數，並將其總和重寫爲

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

從哪裏可以清楚地知道可以在O（n）中計算總和。

噢，Gareth指出，這是總和的閉式表達式，它在常量時間內計算。

來源

2010-12-05 20:59:23 ulidtko

總和是多少？

回答

相關問題