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)