最近不忙，准备巩固一下基本功，看了点算法的东西。这里记录一下斐波那契数列算法，及其对于时间复杂度的优化方法。
关于斐波那契数列，传送门在此。
就是这样的数列：1, 1, 2, 3, 5, 8, 13, 21, 34, 55......
从第三项开始，每一项等于前两项之和，不多BB，往下看
一、递归（最容易想到的方法）
这个数列的第 0 项我们一般看作是 0，即：
| 数列第 n 项 | 表达式 | 条件 |
|---|---|---|
| 0 | n = 0 时 | |
| F(n) = | 1 | n = 1 时 |
| F(n - 1) + F(n - 2) | n >= 2 时 |
代码实现如下(只考虑 n 是自然数的情况):
function Fibonacci(n) {
if (n <= 1 ) {
return n;
} else {
return Fibonacci(n - 1) + Fibonacci(n - 2);
}
}
虽说能正确计算，但是其仅在 n <= 1 时，时间复杂度为 O(1)
当 n >= 2 时
F(5)
/ \
F(3) F(4)
/ \ / \
F(1) F(2) F(2) F(3)
/ \ / \ / \
通过这个树，我们能看出它的时间复杂度是 O(2^n)
话说大学时候，学校的 OJ 上做过这题，当时就是用的递归，AC 以后就没再继续深入研究过
二、利用数组（可将时间复杂度优化为 O(n) ）
function Fibonacci(n) {
if (n <= 1 ) {
return n;
} else {
var arr = [];
arr[0] = 0;
arr[1] = 1;
for (var i = 2; i <= n; i ++) {
arr[i] = arr[i - 1] + arr[i - 2];
}
return arr[n]
}
}
也是挺巧妙的一种方法，不过需要创建数组，占用了一定的内存空间，虽说现在的手机、电脑也不差这点内存，但是还是可以优化一下
三、利用中间变量（时间复杂度也是 O(n)，但可以节省空间）
同方法二思想类似，不过不使用数组
function Fibonacci(n) {
if (n <= 1 ) {
return n;
} else {
var temp0 = 0;
var temp1 = 1;
var fn = 0;
for (var i = 2; i <= n; i ++) {
fn = temp0 + temp1;
temp0 = temp1;
temp1 = fn;
}
return fn
}
}
变量位置互换的思想
四、利用矩阵（可将时间复杂度优化为 O(log n) ）
这个就属于用空间换时间了
话说这个矩阵我好像还给了大学老师，等我看会了再写上来，尴尬
五、高中数学（ O(1) ）
这个就是高中数学知识了，构造等比数列，求通项
话说这个好像也还给高中老师了，好在高中数学还不错，捡了回来
鹏哥带你们复习一下高中数学：
已知等比数列：1, 3, 9, 27, 81...... 求其第 n 项
很显然公比为 3，直接套公式，a(n) = a(1) * q^(n - 1)
即 a(n) = 3^(n - 1)
话说这个 markdown 写数学公式是真难受啊
然后在看这个斐波那契数列，看起来不是等比，这就需要我们去构造等比，眼前浮现出高中数学老师粉笔一挥，抑扬顿挫的说差后成等比的情景，怀念啊……
推导过程有点长，有空我整理下再发上来，先看通项
通项公式
function Fibonacci(n) {
var sqrt5 = Math.sqrt(5);
var ratio = 1 / sqrt5;
var base1 = (sqrt5 + 1) / 2;
var base2 = (1 - sqrt5) / 2;
var fn = ratio * (Math.pow(base1, n) + (Math.pow(base2, n)));
return Math.round(fn);
}
不过这个，浮点数你懂的，精度上要差一些。
这里只是做以讨论，没有考虑浮点数加减乘除的问题，n <= 75 时是正确的，n = 76 时就开始有偏差了，关于浮点数运算问题有空再写吧
根据情况选择对应的方法吧，数值越大，矩阵运算的时间优势体现越明显
