数学公式
1.从1加到n的和的公式
S=n(n+1)/2。
因为S=1+2+3+…+n，并且，S=n+(n-1)+(n-2)+…+1，把这两个等式左右分别相加可以得到：2S=(n+1)+(n+1)+(n+1)+…+(n+1)，其中等式右边一共是
n个（n+1)相加是很容易数出来的，所以得到 2S=n(n+1)，于是S=n(n+1)/2。
2.等差数列和公式：Sn=n(a1+an)/2=na1+n(n-1)/2 d
3.等比数列求和公式：当q≠1时 ，Sn=a1(1-q^n)/(1-q)=(a1-anq)/(1-q)
当q=1时Sn=na1
(a1为首项，an为第n项，d为公差，q 为等比)
4.等差数列 前n项和公式为：
Sn=na1+n(n-1)d/2或Sn=n(a1+an)/2(2)
从等差数列的定义、通项公式，前n项和公式还可推出：
a1+an=a2+an-1=a3+an-2=…=ak+an-k+1，k∈{1,2,…,n}
若m，n，p，q∈N*，且m+n=p+q，则有
am+an=ap+aq
Sm-1=(2n-1)an，S2n+1=(2n+1)an+1
Sk，S2k-Sk，S3k-S2k，…，Snk-S(n-1)k…或等差数列，等等。
5.Fib
0,1,1,2,3,5,8,13,21,…
F(n) = F(n-1) + F(n-2);
- 二分查找 时间复杂度O(logn) 公式 T(n) = T(n/2) + O(1)
二叉树遍历 时间复杂度O(n) 公式 T(n) = 2T(n/2) + O(1)
排好序的二维矩阵二分查找 时间复杂度O(n) 公式 T(n) = 2T(n/2) + O(logn)
归并排序 时间复杂度O(nlogn) 公式 T(n) = 2T(n/2) + O(n)
