时间复杂度分析

主定理

$$T(n)=aT\left(\frac{n}{b}\right) + O(n^d)$$

$$T(n)=\begin{cases} O(n^{\log_{b}a}) & a > b^d\\ O(n^{d}\lg n) & a = b^d\\ O(n^d) & a < b^d\\ \end{cases}$$

一阶线性递推式

$$a_n=p\cdot a_{n-1} + q \quad(p\ne 0,1)$$

生成函数

用生成函数做，令 $\{a_i\}$ 的生成函数为 $F(x)$

$$F(x)=a_0 + a_1x + a_2x^2 + \cdots$$

$$\begin{aligned} F(x)&=\sum_{i=0}^{\infty} a_ix^i\\ &=a_0 + \sum_{i=1}^{\infty} (pa_{i-1}+q)x^{i}\\ &=a_0 + px\sum_{i=1}^{\infty} a_{i-1}x^{i-1} + q\sum_{i=1}^{\infty}x^i\\ &=a_0 + pxF(x) + q\frac{x}{1-x}\\ &=\frac{a_0}{1-px}+\frac{qx}{(1-px)(1-x)}\\ &=\frac{a_0}{1-px}+\frac{\frac{q}{1-p}}{1-x}+\frac{\frac{q}{p-1}}{1-px}\\ &=\sum_{i=0}^{\infty} a_0p^ix^i+\sum_{i=0}^{\infty}\frac{q}{1-p}x^i+\sum_{i=0}^{\infty}\frac{q}{p-1}p^{i}x^i\\ &=\sum_{i=0}^{\infty} \left(\frac{q}{1-p}+\left(a_0+\frac{q}{p-1}\right)p^{i}\right)x^i\\ \end{aligned}$$

于是我们得到

$$a_n=\left(a_0+\frac{q}{p-1}\right)p^n+\frac{q}{1-p}$$

特征方程

上面的生成函数推导过于繁琐，于是我们引入特征方程来便于背公式。对于递推式 $a_n=p\cdot a_{n-1} + q$ 我们写出它的特征方程：

$$x=px+q$$

解得 $x_0=\dfrac{q}{1-p}$，然后掏出结论：

$$a_n=(a_0-x_0)p^n+x_0$$

二阶线性递推式

$$a_n=p\cdot a_{n-1}+q\cdot a_{n-2}$$

生成函数

别想了，太烦了

特征方程

根据式子列出特征方程：

$$x^2-px-q=0$$

得两根 $x_1,x_2$ ，分讨：

1. $x_1\ne x_2$ 数列 $\{a_i\}$ 通项为：

   $$a_n=Ax_1^{n}+Bx_2^{n}$$

   $A,B$ 为常数，将 $a_0,a_1,x_1,x_2$ 带入求解，即求以下方程：

   $$\left\{ \begin{array}{c} A+B=a_0\\ x_1A+x_2B=a_1 \end{array}\right.$$

2. $x_1=x_2$ 数列 $\{a_i\}$ 通项为：

   $$a_n=(A+Bn)x_1^n$$

   同样 $A,B$ 为常数可由 $x_1,a_0,a_1$ 求出。