嵌套循環的時間複雜度：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次。因此，循環中的時間複雜度是

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

確定，所以我不理解的時間複雜度，T（n）的即使如何確定C + 2C + 3c上。然後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符號很有用。

或者是你的問題總結來自哪裏？

希望這會有所幫助！