Skip to content

風船の笔记本

离散数学基础:递推关系式

离散数学基础:递推关系式

思维导图¶

$递推关系式$

递推关系式相关概念¶

定义¶

用序列中某些前面的项 a_{i}, 0 \leq i < n 表示第 n 项 a_{n} 的等式

解¶

序列 {a_{n}} 满足一个递推关系式，则 {a_{n}} 即为该递推关系式的一个解

封闭公式解¶

\begin{aligned} 序列 {a_{n}} 的第n项可以用不含序列中任何项的通项公式表达， \\ 则该通项公式称为该递推关系式的封闭公式解 \end{aligned}

常系数线性递推关系式的一般形式¶

\begin{aligned} a_{n} = c_{1} a_{n - 1} + c_{2} a_{n - 2} + . . . + c_{k} a_{n - k} + F (n) \end{aligned}

若 F (n) = 0 则为齐次

若 F (n) \neq 0 则为非齐次

线性齐次递推关系式的解¶

特征方程¶

\begin{aligned} x^{n} = c_{1} x^{n - 1} + c_{2} x^{n - 2} + . . . + c_{k} x^{n - k} + F (n) \end{aligned}

特征方程的根¶

\begin{array}{r} r_{1}, r_{2}, . . . r_{t}, 重数分别为 m_{1}, m_{2}, . . . m_{3}, 这门课没管复根情况咱就不背了捏 \end{array}

解的形式¶

\begin{aligned} a_{n} & = (β_{1, 0} + β_{1, 1} n + . . . + β_{1, m_{1} - 1} n^{m_{1} - 1}) r_{1}^{n} \\ + (β_{2, 0} + β_{2, 1} n + . . . + β_{2, m_{2} - 1} n^{m_{2} - 1}) r_{2}^{n} \\ + . . . \\ + (β_{t, 0} + β_{t, 1} n + . . . + β_{t, m_{t} - 1} n^{m_{t} - 1}) r_{t}^{n} \\ 代入至少t个初始条件解出待定系数 β_{1}, β_{2}, . . . β_{t} 即可得到解 \end{aligned}

线性非齐次递推关系式的解¶

伴随齐次递推关系式¶

令 F (n) = 0 得到：

\begin{aligned} a_{n} = c_{1} a_{n - 1} + c_{2} a_{n - 2} + . . . + c_{k} a_{n - k} \end{aligned}

按照线性齐次递推关系式求解得到：
通解，即伴随齐次递推关系式的解

F(n)形式¶

\begin{array}{r} F (n) = (b_{t} n^{t} + b_{t - 1} n^{t - 1} + . . . + b_{1} n + b_{0}) s^{n} \end{array}

Info

这门课没管的别的情况咱就不背了捏

特解的形式¶

s 不是伴随线性齐次递推关系式的特征方程的根

\begin{array}{r} a_{n}^{(p)} = (p_{t} n^{t} + p_{t - 1} n^{t - 1} + . . . + p_{1} n + p_{0}) s^{n} \end{array}

s 是伴随线性齐次递推关系式的特征方程的 m 重根

\begin{array}{r} a_{n}^{(p)} = n^{m} (p_{t} n^{t} + p_{t - 1} n^{t - 1} + . . . + p_{1} n + p_{0}) s^{n} \end{array}

将特解代入递推关系式，对得到的关于n的多项式的等式两边比较系数，可以确定待定系数 p_{0}, p_{1}, . . . p_{t}

解的形式¶

\begin{array}{r} a_{n} = 通解 + 特解 = 通解 + a_{n}^{(p)} \end{array}

算法效率¶

分析主定理（Master Therorem）

¶

\begin{aligned} f (n) 是实递增函数，且满足递推关系式 f (n) = a f (\frac{n}{b}) + C n^{d} ，则： \\ \begin{aligned} f (n) 是 {\begin{aligned} O (n^{d}) & a < b^{d} \\ O (n^{d} l o g n) & a = b^{d} \\ O (n^{l o g_{b} a}) & a > b^{d} \end{aligned} & \begin{aligned} a, b \in Z, a \geq 1, b > 1, \\ C, d \in R, C > 0, d \geq 0 \end{aligned} \end{aligned} \end{aligned}