합계는 얼마입니까?

Question

Σ (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)?

Answer 1

나는 당신이 의미 있다고 가정 Σ _{1 ≤ 내가 ≤ N}내가 ( 내가 + 1)/2, Σ _{이후 1 ≤ 내가 ≤ N}N ( n +1)/2는 단지 n² (n +1)/2이며, 나는 당신이 스스로 볼 수 있었을 것이라고 확신합니다.

어쨌든 합계를 정확히 계산할 수있을 때 왜 단순한 점근선 증가율을 올려야합니까?

Σ _{1 ≤ I I ≤ N} ( I + 1)/2

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

,

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

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

OEIS이 번호를 호출한다 (1, 4, 10, 20, ...)가 "tetrahedral numbers ".

Answer 2

O (n^3)입니다.

사실이라고 생각하면 삼각형 피라미드로 시각화 할 수 있습니다.

Answer 3

우리는 n^2에 n(n+1)/2에 근접 할 수 있습니다. 따라서 합계는 1^2 + 2^2 + ... + n^2이며 n(n+1)(2n+1)/6이며 대략 n^3입니다. 따라서 상한선은 n^3입니다.

Answer 4

예, k = 1,2, ..., n에 대한 차수 d의 다항식을도 d + 1의 차수 n의 다항식으로 나타냅니다. k(k+1)/2은 k의 차수 2이므로, 그 합은 n의 차수 2 + 1 = 3입니다.

Answer 5

합계의 정확한 공식은 이며, 이는 O(n^3)입니다.

Answer 6

계산 복잡도는 다음과 같습니다. big-O bound 총합은?

두 번째는 이미 사람들이 알고있는 것처럼 O (n^3)이지만 은으로 계산됩니다. 합계는 더하기 및 곱셈 만 필요합니다. 당신은 피가수를 재편성하고 합이 O (n)이 계산 될 수있는 것은 분명하다 곳에서

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

으로 합계를 다시 작성할 수 있습니다.

아, 그리고 Gareth는 합계에 대한 닫힌 형식의 표현이 있으며, 일정 시간에 계산됩니다.