嵌套循环的时间复杂度: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，即高斯级数。 因此

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

= c（1 + 2 + 3 + ... + n）

= cn（n+1）/2

这种求和在算法分析中经常出现，在使用大O表示法时很有用。

或者你的问题总和到底是从哪里来的？

希望这有帮助！