二阶数列特征方程
Aybss
·
·
个人记录
二阶数列特征方程
作用：解决二阶线性递推式通项公式,求解第n项数列值。
时间复杂度：O(logn)
做法：给定数列中任意两项数列值和数列的二阶线性递推式，形如：
a_{n + 1} = c_{1}a_{n}+c_2a_{n - 1}
我们暂且不考虑为什么要执行接下来的操作，将其化为：
t^2 = c_1t+ c_2
合并同列项，最终化为：
t^2 - c_1t - c_2 = 0
根据一元二次方程求根公式解得：
t = \frac{c_1\pm \sqrt{c_1^2+4c_2}}{2}
这里分三种情况讨论：
第一种：t_1\ne t_2,我们将其写成：
a_n = pt_1^2 + qt_2^2
其中 p, q 是常数，我们将题目给定的两项数列值带入上面的方程，即可求解 p 与 q 的值。
第二种： t_1 = t_2,我们将其写成：
a_n = (p + qn)t^n
同样，其中 p, q 是常数，我们将题目给定的数列值带入上面的方程，即可求解。
第三种： t_1,t_2为共轭虚根，即t = r(cos\theta\pm i\cdot sin\theta),我们将其写成：
a_n = r^n(p\cos n\theta \pm q\sin n\theta)
同样的，其中 p, q 是常数，我们将题目给定的数列值带入上面的方程，即可求解。
写出数列的通式方程，再利用快速幂在O(logn)的时间复杂度算出任意一项数列值。
举个例子，给定二阶数列
那么这里
$$t^2 = 4t - 4$$
$$\Rightarrow t^2 - 4 t + 4 = 0$$
$$\Rightarrow (t - 2)^2 = 0$$
$$t_1 = t_2 = 2$$
我们发现这是情况2，于是写成：
$$a_n = (p + q \ n)t^2$$
也就是：
$$a_n = (p + q\ n)2^n$$
下面求$p, q$:
$$\begin{cases}
2(p + q) = 1\\
4(p + 2q) = 5
\end{cases}
$$
$$\Rightarrow
\begin{cases}
p = -\frac{1}{4}\\
q = \frac{3}{4}
\end{cases}
$$
那么，我们得出数列通项公式为:
$$ a_n = (-\frac{1}{4}+\frac{3}{4}\ n)\ 2^n $$
也就是:
$$a_n = (3\ n - 1)\ 2^{n - 2}$$
那么第12项就是$(3 \times12 \ -1)\times1024 = 35840
ω(n) = n -\left \lceil \frac{n}{2} \right \rceil-\left \lceil \frac{n}{4} \right \rceil-\left \lceil \frac{n}{8} \right \rceil-...-\left \lceil \frac{n}{2^{+∞}} \right \rceil