c++ - 嵌套循环的时间复杂度：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, ...，内部循环执行 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 表示法时很有用。

或者你的问题是总和来自哪里？

希望这可以帮助！