Fibonacci

算了，今天不想动那只笨鸟了，写点别的吧。

大名鼎鼎的斐波那契数列，定义非常简单:

先不急着写代码，我们先来求一下这个数列的通项公式。为了方便先用符号${𝑎}_{𝑛}$来表示。

先把上式写成如下形式，这样则${𝑎}_{𝑛}-𝜇{𝑎}_{𝑛-1}$是一个等比数列，我们可以求出它的通项：

所以有:

故$𝛾$和$𝜇$是以下方程的两个根:

由求根公式，求得:

取$𝛾=\frac{1+\sqrt{5}}{2},𝜇=\frac{1-\sqrt{5}}{2}$，有:

令${𝑏}_{𝑛}={𝑎}_{𝑛+1}-\frac{1-\sqrt{5}}{2}{𝑎}_{𝑛}$，则可知:

故:

两边同时除以${\left(\frac{1-\sqrt{5}}{2}\right)}^{𝑛+1}$有:

令${𝑐}_{𝑛}=\frac{{𝑎}_{𝑛}}{{\left(\frac{1-\sqrt{5}}{2}\right)}^{𝑛}}$，有:

故:

由等比数列求和公式有:

故:

可以看到Fibonacci数列大致上是按指数级别增长的，且n越大，前后两项的比值越趋近黄金分割比$\frac{\sqrt{5}-1}{2}$

回到代码，大体上来说求Fibonacci数列的方法主要用三种：递归法、循环法、我也不知道叫什么法就暂时叫它矩阵法好了（反正不是基本法，逃

三种方法有着不同的时间复杂度

递归法:

function rst = fib(n)
if n < 3
    rst = 1;
else
    rst = fib(n-1) + fib(n-2);
end

直观上来说，由于递归法的递归树最终的叶都是计算fib(1)，所以递归法的时间复杂度就是Fibonacci数列的值。即递归法的时间复杂度是指数级别的。当然我们可以用空间换时间的办法来把递归法的时间复杂度变成线性级别。也可以称为数组法= =

循环法:

function rst = fib(n)
rst = 1;
t1 = 1;
t2 = 0;
count = 0;
while count < n - 1
    rst = t1 + t2;
    t2 = t1;
    t1 = rst;
    count = count + 1;
end

循环法时间复杂度是线性的，空间复杂度是常数级别的。

有的时候我们会觉得线性时间复杂度还不够好，那怎么办呢，到了矩阵法出场的时候了，不过先别着急，先来介绍一个相关的算法:快速幂算法。

假如你要计算a的n次方，那么我们一般会循环n次，每次结果都乘a。

而快速幂算法则不一样，这个方法用递归的方式来计算，具体来说递归的每步是这样的:

1. 假如n=1，则返回a
2. 假如n为偶数，计算${𝑎}^{{\left(𝑛/2\right)}^2}$
3. 假如n为奇数，计算${𝑎}^{{\left(\left(𝑛-1\right)/2\right)}^2}\times 𝑎$

很容易知道快速幂算法的时间复杂度是对数级别的，而且这里的a并不限于是实数，可以是复数、矩阵等。而有了这个算法，就可以介绍矩阵法的做法了。

矩阵法:

来观察以下矩阵

可能观察不出什么来，但是我们可以很容易的得到以下等式:

so on

实际上，一般情况为:

可以用数学归纳法证明:

为了方便起见，我们从n=2开始证明，很显然n=2是成立的。

假设n=k时，成立

则当n=k+1时

得证

由于做一次[2x2]矩阵的乘法是常数级别时间复杂度的，所以我们可以通过矩阵+快速幂算法，来实现一个时间复杂度为对数级别的算法来求Fibonacci数列。

代码如下:

function rst = fib(n)
temp = [0,1;1,1]^n;
rst = temp(1,2);

所以你看，用了matlab世界瞬间变得简单了~

后记:所有的代码均不考虑n=0或n为负数的情况。曾经年少（15年复读那会吧）的我想过，既然通项公式已经知道了，直接求不就好了，而且我确实还写了代码。当然其实因为浮点数的精度问题，这样做肯定是免不了有问题的，而且即使如此，由于通项公式里有n次方，所以实际上到头来你最好的时间复杂度还是对数级别的，何必呢。这里我的矩阵法matlab代码里，并没有体现快速矩阵幂这一点，这是因为matlab的矩阵求幂算法肯定比我手动实现快速矩阵幂快（逃

当然还要补充的是，实际上由于Fibonacci数列的指数级增长，所以对于大多数编程语言来说，Gibonacci数列的项会比较快的突破整数or浮点数的表示范围，所以，这个问题一般实际上意义不大的。另外Fibonacci数列有很多有趣的性质，这里就不再展开讨论了。