###数据结构和算法分析-导论

1.数学知识复习

#####1.1 指数 X^A*X^B=X^A+B

#####1.2 对数

定义1.X^A=B当且仅当log_xB=A

定理1 log_AB=log_cB/log_cA

定理2 logAB=logA+logB;

#####1.3 级数 ######最简单容易记忆的级数 \(\sum_{i=0}^N{2^i}=2^{i+1}-1\) 和 \(\sum_{i=0}^N{A^i}=\frac{A^{i+1}-1}{A-1}\) 在第二个公式中，如果0< A <1，则 \(\sum_{i=0}^N{A^i}<=\frac{1}{1-A}\) 当N趋向与$\infty$

######求和公式

假设0 < A < 1 $ \sum_{i=0}^N{A^i} $的和是S，此时S=1+A+A²+A³+……，于是：AS=A+A²+A³+……，如果我们将这个两个方程相减： \(S-AS=1\) 即 \(S=\frac{1}{1-A}\) ######算术级数 基本公式： \(\sum_{i=1}^N{A^i}=\frac{N(N+1)}{2}\approx\frac{N^2}{2}\)

由基本公式推导出来的两个公式： \(\sum_{i=1}^N{i^2}=\frac{N(N+1)(2N+1)}{6}\approx\frac{N^3}{3}\) \(\sum_{i=1}^N{i^k}\approx\frac{N^{k+1}}{k+1}\)