算法课笔记2

数学预备知识

典型求和公式

1.$\sum_{i=1}^{n} i=n(n+1)/2=\Theta(n^2)$

2.$\sum_{i=1}^{n} (a+bi)=na+bn(n+1)/2=\Theta(n^2)$

3.$\sum_{i=1}^{n} i^2 = \frac{n(n+1)(2n+1)}{6} =\Theta(n^3)$

4.$\sum_{i=1}^{n} i^k = \Theta (n^k +1)$

5.$\sum_{i=1}^{n} a^i = \frac{1-a^{n+1}}{1-a}=\Theta (a^n) ,(a \neq 1)$

特别的：

6.$\sum_{i=1}^{n} a^i = 1/(1-a) , (|a| < 1)$

7.$\sum_{i=1}^{\infty} a^i = \Theta (1) , (|a| < 1)$

8.$\sum_{i=1}^{n} ia^i = \Theta (na^n) ,(a \neq 1)$

积分图像求边界

条形图是$\sum$,曲线是$\int$

如果f(x)是单调递减的，则：

$$\int_{m}^{n+1} f(x) dx \leq \sum_{j=m}^{n}f(j) \leq \int_{m-1}^n f(x)dx$$

如果f(x)是单调递增的，则：

$$\int_{m-1}^{n} f(x) dx \leq \sum_{j=m}^{n}f(j) \leq \int_{m}^{n+1} f(x)dx$$