数据结构分析算法频度

Question

分析算法的时间复杂度，请问这个计算式怎么理解啊，划线部分是怎么来的呢

Answer 1

这是1/2*((0+1+2+...+n)^2+0+1+2+...+n)
根据高斯求和公式 a+(a+1)+(a+2)+(a+3)+...+b=(a+b)*(b - a + 1)/2 （比如说1+2+...+100 = (1+100)*100/2=5050）
所以就是1/2*((n*(n+1)/2)^2+(n*(n+1)/2))
然后化简就是那个式子，就是后面的。