斐波那契数列

F(n)={0,n=01,n=1F(n−1)+F(n−2),n>1F(n)=\begin{cases} 0, &n=0 \\ 1,&n=1 \\ F(n-1)+F(n-2),&n>1 \end{cases}

这是斐波那契数列, 一个从小学学到现在的数列, 最近复习数据结构又接触到了这个数列, 感觉挺有意思的

这里我们如果用递归的方式的计算一下它的复杂度

1
2
3
4
5
int f(n) {
	if (n == 0) return 0;
	if (n == 1) return 1;
	return f(n - 1) + f(n - 2);
}

很容易写出来这个递推公式 F(n)=F(n−1)+F(n−2)F(n)=F(n-1)+F(n-2)

比较直观的是稍微分解一下可以看出他是由 1 与 2 以不同方式的结合, 每多一种方式就会多一个分叉节点, 每个分叉节点相当于一次操作

直接将 nn 分 tt 和 n−tn-t 两部分, 为我们就可以得出一个计算式

Sn=∑t=0n(n+t2)!t!(n−t)!=∑k=0n/2(n−kk)S_{n=}\sum^n_{t=0} \frac{\left( \frac{n+t}{2} \right)!}{t!(n-t)!}=\sum^{n/2}_{k=0}\dbinom{n-k}{k}

由于

(n−kk)=(n−k−1k)+(n−k−1k−1)\dbinom{n-k}{k}=\dbinom{n-k-1}{k}+\dbinom{n-k-1}{k-1}

Sn=Sn−1+Sn−2,S0=1,S1=1S_{n}=S_{n-1}+S_{n-2}, \quad S_{0} = 1, \quad S_{1}=1

我们发现 SnS_{n} 也是一个斐波那契数列, 而且刚好

Sn=F(n+1)S_{n}=F(n+1)

这里就注意到一个有意思的点了, 也就是复杂度是斐波那契数列的下一项的数值, 将 F(n)F(n) 直接进行分解(这里就懒得画了)观察后根据二叉树的基本性质分叉节点数量也就是操作数量差不多就是叶节点数量, 叶节点只有 F(0),F(1)F(0),F(1) , 我们可以注意到 F(n)F(n) 的值就是所有 F(1)F(1) 的数量(废话), 而所有 F(0)F(0) 的数量就是 F(n+1)−F(n)=F(n−1)F(n+1)-F(n)=F(n-1)

然后稍微再往后推一项我们就可以发现, 所有原来的 F(0)F(0) 就变成了 F(1)F(1), 而所有原来的 F(1)F(1) 又生成了新的 F(1)F(1) 以及 F(0)F(0)

那么这有什么特殊的地方呢, 我们都知道斐波那契数列是兔子繁殖的模型, 而这里就很直观了, 也就是 F(0)F(0) 其实是幼年兔子, 经过一个时间节点会变成成年兔子, 也就是 F(1)F(1), 原本的成年兔子经过这一段时间就会生产一个幼年兔子, 所以经过这一个时间节点后就会变成 F(1)F(1) 本身, 以及生产出来的 F(0)F(0), 这就是繁殖模型

所以斐波那契数列本质上就是底层的不断繁衍的结果上的求和, 那么这个底层逻辑有什么用呢, 我们可以得到一个特殊的映射

(F0,F1)↦(F1,F0+F1)(F_{0}, F_{1}) \mapsto (F_{1},F_{0}+F_{1})

用向量形式表示就是

vn=(anbn)an=F0,bn=Fnv_{n}=\begin{pmatrix} a_{n} \\ b_{n} \end{pmatrix} \quad a_{n}=F_{0}, \quad b_{n}=F_{n}

vn+1=(0111)vnv_{n+1}=\begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}v_{n}

学过线代的都知道, 这个矩阵含义就是 F0=an+1=Fn,Fn+1=bn+1=F0+FnF_{0}=a_{n+1}=F_{n}, F_{n+1}=b_{n+1}=F_{0}+F_{n}, 也就从这两个基础数量上推出了斐波那契数列这两个基础值的迭代关系, 这个矩阵

M=(0111)M=\begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix}

就是斐波那契 Q 矩阵, 我们也可以计算出他的特征值 φ=1±52\varphi = \frac{1\pm\sqrt{ 5 }}{2} , 然后按照正常线代的一系列操作, 将其对角化并取 n 次幂就可以得到

Q=S(φ100φ2)S−1,Qn−1=S(φ1n−100φ2n−1)S−1Q=S \begin{pmatrix} \varphi_{1} & 0 \\ 0 & \varphi_{2} \end{pmatrix} S^{-1},\quad Q^{n-1}=S \begin{pmatrix} \varphi_{1}^{n-1} & 0 \\ 0 & \varphi_{2}^{n-1} \end{pmatrix} S^{-1}

作用于 v1v_{1} 即可得到

Fn=φ1n−φ2n5F_{n}=\frac{\varphi_{1}^n-\varphi_{2}^n}{\sqrt{ 5 }}

所以按照复杂度的定义就取 Fn∼φ1nF_{n}\sim \varphi_{1}^n, 也就是 Fn∼1.618nF_{n}\sim 1.618^n, 黄金分割比诶~~

后记: 当然还有其他复杂度更低的算法去计算斐波那契数列, 但这挺好玩的不是, 而且不就是数列极限吗, 刚好来试试这道题

an=pan−1+qan−2, a1>0, a2>0 p,q>0, 求lim⁡n→∞ln⁡anna_{n}=pa_{n-1}+qa_{n-2},\ a_{1}>0,\ a_{2}>0\ p,q>0, \ 求 \lim_{ n \to \infty } \frac{\ln a_{n}}{n}