数据结构时间复杂度问题

Question

这两天在刷数据结构的题，有点头大，碰到一个简单的数学问题，求大佬指点..
题目中有一个数学公式,我实在不知道怎么推导的.如下:
T(n) = n + (n - 1) + (n - 2)……+ 1 = n(n + 1) / 2 = n^2 / 2 + n / 2
请问 这个式子等于n(n+1)/2是怎么推导出来的啊?虽然我随便让n等于一个数就能知道这个式子是正确的,但是我怎么也推导不出来...

Answer 1

这个其实很简单
n + (n - 1) + (n - 2)……+ 1 ；
对称两个数相加,第一个数和最后一个数相加
n+1，第二个数与倒数第二个数相加 (n-1)+2=n+1
由此就可以类推了：
一共有n个数，两两相加得 n+1,一共有n/2次
则 可得等式:(n+1)n/2

Answer 2

等差数列求和公式。

Answer 3

额。。。 这不是小学问题吗？ 高斯求和哇。。