(n)(n+1)/2のi=1からnまでのΣ
与えられた 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)?
I presume that you mean Σ1 ≤ i ≤ n i(i + 1)/2, since Σ1 ≤ i ≤ n n(n + 1)/2 is just n²(n + 1)/2, which I'm sure you could have seen for yourself.
Anyway, why should you put up with mere asymptotic growth rates when you can compute the sum exactly?
Σ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
The OEIS calls these numbers (1, 4, 10, 20, ...) the "tetrahedral numbers".
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です。
The exact formula for the sum is 1/6*n*(n+1)*(n+2), which is O(n^3).
次の合計の計算の複雑さを求めていますか、それとも合計のBig-O バウンドを求めていますか?
2 番目は O(n^3) ですが、既にお気づきのように、合計を計算するには線形量の加算と乗算のみが必要です。被加数を再グループ化し、合計を次のように書き換えることができます。
n*1 + (n-1)*2 + ... + 1*n
ここから、合計を O(n) で計算できることは明らかです。
ああ、Gareth は、定数時間で計算する和の閉じた形式の式があることを指摘しました。
はい、次数 d の多項式を k = 1,2,...,n で合計すると、次数 d+1 の n の多項式が得られます。は k で次数 2 であるため k(k+1) / 2、その和は n で次数 2 + 1 = 3 です。