중첩 루프의 시간 복잡도 : cn (n + 1)/2는 어디서 오는가?

Question

는 다음 루프를 고려

for (i =1; i <= n; i++) { 
    for (j = 1; j <= i; j++) { 
     k = k + i + j; 
    } 
    } 

외부 루프는 N 회 행한다. i = 1, 2, ... 인 경우, 내부 루프는 한 번, 두 번 실행되고 번 n 번 실행됩니다. I는 시간 복잡도, T는 (N)에도 C + 2C + 3C를 결정하는 방법을 이해하지 않도록 따라서, 루프에 대한 시간 복잡도

T(n)=c+2c+3c+4c...nc 
    =cn(n+1)/2 
    =c/2(n^2)+c/2n 
    =O(n^2).. 

괜찮다. 다음에 cn (n + 1)/2? 그게 어디서 온거야?

Answer 1

합계 1 + 2 + 3 + 4 + ... + n은 n (n + 1)/2와 같으며, 이는 Gauss series입니다. 따라서

C + 2C + 3C + ... + NC

의 C = (1 + 2 + 3 + ... + N)

= CN (N + 1)/2

이 합계는 알고리즘 분석에서 많이 나타나며 big-O 표기법을 사용할 때 알아두면 유용합니다.

또는 합계가 어디에서 오는 질문입니까?

희망이 도움이됩니다.