共计 7365 个字符，预计需要花费 19 分钟才能阅读完成。
在自然界中，有一串数字咱们时常能看到，它的前几项序列是：
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233…
如果用数学语言形容，它的递归模式是这样的：
$$
\begin{cases}
F_0 = 0 \\
F_1 = 1 \\
F_n = F_{n-1}+F_{n-2} &(n\geq2)
\end{cases}
$$
也就是说，除了 第 0 项 和 第 1 项，之后的数字是由这个数紧邻的前两个数字，相加失去的。
如果用几何图形示意，你可能见过这张图：
这就是 斐波那契数 ，它造成的数列就被称为 斐波那契数列。
名称源自 1170 年出世的意大利比萨数学家 列奥纳多·斐波那契：Leonardo Fibonacci。
（歪个楼：列奥纳多·迪·塞尔·皮耶罗·达·芬奇，出生于 1452 年）
求解和利用斐波那契数及数列，是古代计算机科学与传统古典艺术、古代新媒体艺术设计的热门交叉点，包含但不限于图形学、性能优化、先锋艺术、影视创作等等分支畛域。
其中最为驰名的，就是黄金螺旋分割线。所以此篇追根溯源，深刻到算法和数学的最底层面，了解斐波那契数列的计算形式。
① Fibonacci_1(n)：定义式二分递归计算
根据上述定义式，fib() 函数的伪代码形容为（默认 n 为非正数）：
$$
fib(n)=
\begin{cases}
n & (if &n\leq1)\\
fib(n-1)+fib(n-2) & (if &n\geq2)
\end{cases}
$$
// C++
int fib1(int n){return (2 > n) ? n : fib1(n - 1) + fib1(n - 2);
}显然，这种算法浅显易懂，间接依据定义式编码即可。
但弊病也很不言而喻，二分递归的模式，其计算效率十分低下。
假如，计算 fib(n) 所需的工夫为 T(n)。那么依据此算法思路，计算 fib(n-1) 则相应的须要 T(n-1) 的工夫，直到最初破费一个单位的工夫，将其累加。
故，T(n) 的递推式为：
$$
T(n)=
\begin{cases}
1 & (if &n\leq1)\\
T(n-1)+T(n-2) + 1 & (if &n\geq2)
\end{cases}
$$
仔细观察，就会发现 T(n) 与 fib(n) 长得十分像。
那么，令 S(n) = [T(n)+1]/2，
$$
\begin{aligned}
S(n)&=
[T(n)+1]/2 \\
&=
\begin{cases}
(1+1)/2 \\
[T(n-1)+T(n-2)+1+1]/2 \\
\end{cases} \\
& =
\begin{cases}
(1+1)/2 \\
\{[2*S(n-1)-1] + [2*S(n-2)-1] +1 +1 ]\}/2
\end{cases} \\
& =
\begin{cases}
(1+1)/2 \\
[2*S(n-1) + 2*S(n-2)]/2 \\
\end{cases} \\
&= \begin{cases}
1 & (if &n\leq1)\\
S(n-1)+S(n-2) & (if &n\geq2)
\end{cases} \\
\end{aligned}
$$
由此能够发现，除了起始我的项目外，S(n) 与 fib(n) 在模式上统一。
而且：
$$
\begin{cases}
S(0) = (T(0)+1)/2 = 1 = fib(1) \\
S(1) = (T(1)+1)/2 = 1 = fib(2) \\
\end{cases}
$$
也就是说，S(n)=fib(n+1)
进而：
$$
\begin{aligned}
& S(n)=fib(n+1)=(\phi^{n+1}-\hat{\phi}^{n+1})/\sqrt{5},\ \phi = (1+\sqrt{5})/2,\ \hat{\phi}=(1-\sqrt{5})/2 \\
& T(n) = 2*S(n)-1 = 2*fib(n+1)-1=O(\phi^{n+1})\approx O(2^n) \\
\end{aligned}
$$
也就是说，二分递归的算法工夫复杂度达到了恐怖的指数量级，而这个后果是远远不能被承受的（对于 φ 值是如何计算得出的稍后详解）。
如果说指数级复杂度，是给这个算法做了定性分析，那么咱们定量举个例子。
最一般的 PC 运算性能大抵为 1GHz，意味着每秒能够做 10^9 次浮点估算，也就是十亿次。
当咱们计算第 100 项斐波那契数时，大概须要 2^100 次运算，那么大略耗时为 2^100 /10^9，这是多少呢？
粗略估算，2^10 也就是 1024，约等于 10^3，也就是 1000。
那么：
$$
\begin{aligned}
& 2^{100} = (2^{10})^{10} \approx (10^3)^{10} \\
& 2^{100}/10^9 \approx (10^3)^{10}/10^9 = 10^{21} \\
\end{aligned}
$$
问题来了，10^21 秒是多少：
$$
\begin{cases}
1 \ day = 24hr * 60min*60sec = 86400 sec \approx 25*4000 = 10^5 sec \\
100 \ year \approx 100*365\ day \approx 3 * 10^4 day = 3* 10^9 sec
\end{cases}
$$
咱们能够粗略计算，依照上式，三个世纪大略为 10^10 秒。
则，10^21 秒相当于 10^21 /10^10 = 10^11 个“三个世纪”。
也就是 三千亿个世纪
也就是 三十万亿年
现有可观测宇宙的寿命，学界普遍认为在 140 亿年。能够毫不夸大的说，如果依照定义式的形式交给计算机做运算，大略咱们现存的宇宙都从新诞生了上千次了。
而这漫长的所有，只不过是为了求解 第 100 项 斐波那契数 而已。
所以，这种二分递归，层层往返计算的算法，显然是不能被承受的。
② Fibonacci_2(n)：线性递归计算
从二分递归的算法中，不难看出问题所在。
每一次计算新的值时，须要从新回到它的前一项，而后层层往回走，直到最开始的起始项。而后再从新开始从起始项始终加到以后项。
在这个过程中，有大量雷同的我的项目被无数次反复计算，这也是为什么工夫复杂度如此之高，计算资源如此被大量节约的起因。
顺着这种思路，如果说我能够让程序领有一种记忆力，将曾经计算过的我的项目保留下来，在须要的时候间接提取，而不是返到终点再重头计算一遍。这样是不是就能够节俭大量的重复劳动了？
这种开拓存储空间作为计算辅助的做法，就是十分典型的“空间换工夫”的思维。
在这个算法中，独自开拓一个长度为 n 的数组空间，程序运算到第几项，就将这一项的后果存储在空间中。
从而当须要当先项数据时，只需间接调取即可。计算第 n 项时，程序只须要从终点跑一趟，就能够累算失去以后我的项目值。这种形式也更贴近咱们人类计算这个数列的办法。
// C++
int fib2(int n, int& prev){if (0 == n){
prev = 1;
return 0;
}
else {
int prevPrev;
prev = fib2(n - 1, prevPrev);
return prevPrev + prev;
}
}这种算法的工夫复杂度为 O(n)，同时，因为辅助的存储空间与我的项目所在数列的地位（间隔 / 长度 / 坐标 …）成正比，所以，空间复杂度同样也为 O(n)。
如果这里咱们要用微机计算 第 100 项 斐波那契数，实践上只须要 100/10^9 秒的工夫，远远小于一秒钟。这种算法上的优化成果，是远高于第一种二分递归算法的。
③ Fibonacci_3(n)：迭代计算
然而，仔细观察，线性递归算法还有它的问题所在。
对于计算机来说，“空间”是一种限量的资源，数字小一点还好，如果当数据质变大，空间耗费会成为不得不面对的事实。
而在上述开拓的数组空间里，其实真正用到的，仅仅为最初两项数字。也就是斐波那契数的以后后果和前第一项（前第二项，能够用以后后果减去第一项计算失去）。
对于利用过的小我的项目后果，再往后其实程序就不会再拜访它，那么它存在的实际意义就隐没了。
如果程序能够主动销毁之前的后果，让整个辅助空间放弃在肯定的大小范畴内，同计算项的增长而动静追随，始终保留最新的两个我的项目，避免浪费。那么空间耗费，将不再与计算规模挂钩。换言之，空间资源的开销，成为常数级，也就是说，空间复杂度将来到极致的 O(1)。
顺着这种思路持续优化上来。
咱们其实不须要另外开一个程序去实时紧盯不必的计算结果并删除它，换一个角度想，咱们只有在固定的空间内重复写入新后果，笼罩旧数据，就能够实现同样的成果。
事实上，咱们只须要 两个变量 即可。
一个存储以后项，一个存储前一项。
// C++
int fib3(int n){
int f = 1, g = 0;
while (0 < n--) {g += f; f = g - f;}
return g;
}程序中，g 为最终后果，f 为前一项。
没有昂扬的数组空间开销，也没有简单的资源管理。
只须要两个变量，好像二龙戏珠回旋向上一样，从 0 始终俯冲计算到以后项即可。
算法的工夫复杂度同样仍然为 O(n)，而空间复杂度，曾经被优化到了极致的 O(1)，也有称之为【就地算法】。
能够看到，程序十分的简洁，效率也足够的优良。短短几个字符，凝固了人类顶级的智慧，不得不感叹算法的魅力。
④ Fibonacci_4(n)：通项公式求解
然而！
还没有完结！
人类谋求极致智慧的脚步是不会停下来的。
空间复杂度曾经被优化到了极致的 O(1)，那么评估算法优劣的指标剩下了另一项，也就是工夫复杂度。
到目前为止，任意项斐波那契数求解计算的工夫复杂度还仍然是 O(n)。
接下来要做的，就是将它进一步优化，直到完满的 O(1)。
你可能会困惑，依靠前 n-1 和 n-2 项的斐波那契数，无论如何都无奈跳脱从终点到第 n 项的这个遍历过程。
是的，所以如果想实现最为极致的优化。
那么，欢送来到 数学 的世界。
留神到了吗，咱们最开始，对斐波那契数的定义，是通过它的天然模式，自然而然推出来的、形象的递归公式。
活泼的形容形式诚然便于了解，然而不免有些原始。咱们接下来要做的，是通过递归形容，推导出计算任意项斐波那契数的通项公式。
也就是说，只有一个变量，和一堆系数及数学方法，不通过一一推导，间接用一个方程算出后果。
为了便于了解，咱们用高中生都会的初等数学常识推导：
目前已知：
$$
\begin{aligned}
& a_1 = 1 \\
& a_2 = 1 \\
& a_n = a_{n-1} + a_{n-2} \\
\end{aligned}
$$
设：
$$
a_n + \alpha*a_{n-1} = \beta*(a_{n-1}+\alpha*a_{n-2})
$$
即：
$$
a_n = (\beta-\alpha)*a_{n-1}+\alpha*\beta*a_{n-2}
$$
依据：
$$
\begin{cases}
a_n = a_{n-1} + a_{n-2} \\
a_n = (\beta-\alpha)*a_{n-1}+\alpha*\beta*a_{n-2} \\
\end{cases}
$$
能够求得：
$$
\begin{cases}
\beta – \alpha = 1 \\
\alpha * \beta = 1 \\
\end{cases}
=>
\begin{cases}
\beta =1 + \alpha \\
\alpha*(1+\alpha)=1 \\
\end{cases}
=>
\alpha^2+\alpha-1=0
$$
$$
\begin{aligned}
\alpha_{1,2} &= \frac{-b\pm\sqrt{b^2-4ac}} {2a} \\
&= \frac{-1\pm\sqrt{1+4}}{2} \\
& = \frac{-1\pm\sqrt{5}}{2}
\end{aligned}
$$
这里能够取负数，那么带回公式，可求得：
$$
\begin{cases}
\alpha=\frac{\sqrt{5}-1}{2} \\
\beta=\frac{\sqrt{5}+1}{2} \\
\end{cases}
$$
因为等比数列
$$
\begin{aligned}
& T_n = a_{n}+\alpha*a_{n-1} \\
& T_{n-1} = a_{n-1}+\alpha*a_{n-2} \\
& T_{n}=\beta*T_{n-1}
\end{aligned}
$$
所以：
$$
\begin{aligned}
a_{n+1}+\alpha*a_{n}&=(a_2+\alpha*a_1)*\beta^{n-1} \\
&= (1+\alpha)*\beta^{n-1} \\
&= \beta^n
\end{aligned}
$$
等式两边同时除去 β 的 n+1 次，可得：
$$
\begin{aligned}
& \frac{a_{n+1}+\alpha*a_{n}}{\beta^{n+1}}=\frac{\beta^{n}}{\beta^{n+1}} \\
& \frac{a_{n+1}}{\beta^{n+1}}+\frac{\alpha}{\beta}*\frac{a_n}{\beta^n}=\frac{1}{\beta} \\
\end{aligned}
$$
令：
$$
b_n=\frac{a_n}{\beta^n}
$$
则代入上式：
$$
b_{n+1}+\frac{\alpha}{\beta}b_n=\frac{1}{\beta}
$$
设：
$$
b_{n+1}+\lambda = – \frac{\alpha}{\beta}(b_n+\lambda)
$$
则：
$$
b_{n+1}+\frac{\alpha}{\beta}b_n=-\frac{\alpha}{\beta}\lambda-\lambda
$$
即：
$$
\frac{1}{\beta} =-\frac{\alpha}{\beta}\lambda-\lambda
$$
得：
$$
\lambda = -\frac{1}{\alpha+\beta}
$$
所以：
$$
\begin{cases}
b_n+\lambda=(-\frac{\alpha}{\beta})^{n-1}(b_1+\lambda) \\
b_1 = \frac{\alpha_1}{\beta} = \frac{1}{\beta} \\
b_n = \frac{a_n}{\beta^n} \\
\alpha = \frac{\sqrt{5}-1}{2} \\
\beta = \frac{\sqrt{5}+1}{2} \\
\end{cases}
$$
代入可得：
$$
\begin{aligned}
& \frac{a_n}{\beta^n}+\lambda = (-\frac{\alpha}{\beta})^{n-1}*(\frac{1}{\beta}+\lambda) \\
& a_n-\frac{1}{\sqrt{5}}*\beta^{n}=-1*(-\alpha)^{n-1}*\beta*(\frac{1}{\beta}-\frac{1}{\sqrt{5}}) \\
\end{aligned}
$$
进一步求解：
$$
\begin{aligned}
a_n &= -1*(-\alpha)^{n-1}*(1-\frac{\beta}{\sqrt{5}})+\frac{1}{\sqrt{5}}*\beta^n \\
& =-1*(\frac{-(\sqrt{5}-1)}{2})^{n-1}*(\frac{1}{2})*(\frac{2*\sqrt{5}}{\sqrt{5}}-\frac{\sqrt{5}+1}{\sqrt{5}})+\frac{1}{\sqrt{5}}*(\frac{\sqrt{5}+1}{2})^n \\
&= \frac{1}{\sqrt{5}}*[(\frac{1+\sqrt{5}}{2})^n-(\frac{1-\sqrt{5}}{2})^n]
\end{aligned}
$$
最终可得，斐波那契数列的通项公式为：
$$
fib(n)=(\phi^{n}-\hat{\phi}^{n})/\sqrt{5},\ \phi = (1+\sqrt{5})/2,\ \hat{\phi}=(1-\sqrt{5})/2
$$
这也就是 解法① 中提到的工夫复杂度为什么是指数级。
当然，求解通项公式的办法还有很多，这里就不赘述了，详情能够本人查问。
有了通项公式，程序就非常容易编写：
// C++
int fib4(int n)
{float var1 = (1 + sqrt(5)) / 2;
float var2 = (1 - sqrt(5)) / 2;
float var3 = sqrt(5) / 5;
return var3 * (pow(var1, n) - pow(var2, n));
}据查 C++ pow 函数可达 O(1)，那么很天然的，工夫复杂度为 O(1)，空间复杂度也为 O(1)。
即使应用疾速幂运算，工夫复杂度仍然能够降至 O(logn)
⑤ 黄金分割
咱们常常据说的黄金分割，是一种比例。
定义为：
$$
\frac{a+b}{a}=\frac{a}{b}=\phi \ (a>b>0)
$$
这个比值取小数点后三位为 1.618。
是不是感觉这个模式很面生？
德国天文学家开普勒发现，斐波那契数列的前后两项之比:
$$
\frac{1}{1}, \frac{1}{2}, \frac{2}{3}, \frac{3}{5}, \frac{5}{8}, \frac{8}{13}, \frac{13}{21}, \frac{21}{34}, …
$$
在 n 趋于无穷大的时候，后果就是黄金分割比例了。
$$
\lim_{n \rightarrow \infty}{\frac{fib_{n+1}}{fib_{n}}} = \frac{1}{2}(1+\sqrt5)=\phi \approx 1.618…
$$
黄金分割的利用十分宽泛，十分驰名的一个示意图就是上面蒙娜丽莎的这张：
斐波那契数列最早被人们察看到是在自然界中，花瓣的成长散布、向日葵花盘中葵花籽的散布、鹦鹉螺螺纹的变动，甚至银河系旋臂的走势，其实它就在咱们身边。
作为自然界神奇的体现，斐波那契数列形象形容了这一广泛而又充斥神秘魅力的景象。
之所以人们普遍认为黄金分割是美的，多半是源自它形象出的自然界的实在。
当然远远不止这些，
比方 UI 设计中界面的划分占比，页面排版的好看，logo 设计中的美感，建筑设计里的秩序。
甚至在计算机科学畛域，还有专门的【斐波那契查找】这种独特的查找算法。
这里不再多述利用场景了。
此篇为带大家深刻了解斐波那契数列背地的数理常识和计算形式，当咱们从最底层理解它的原理，外表的泛滥纷纷，也天然有了必然的分割。也为咱们的进一步翻新，提供更为扎实的实践和思路。
【此文原创，欢送转发，禁止搬运】
