接上篇内容,翻倒远古时期用MATLAB写的Fibonacci数列第N项的计算方法,直觉上写一个递归函数就可以搞定问题,但是其计算时间复杂度是O(2^n)

当然,如果需要降低时间复杂度,应该写成循环的形式。我一开始以为自己写的就是递归函数的版本,查着资料,写着博客,猛然发现自己写的就是循环。

%古老的脚本,从第三项开始计算数列的内容
function y=Fibonacci(k)
    a=[1 1];
        for i=3:k
        a(i)=a(i-1)+a(i-2);
        end
    y=a(k);
end

如果还想偷懒,可以写成矩阵计算的样子。

function y=Fibonacci(n)
  a=[1 0];
  b=[1 1;1 0];
  y=a*b^(n)*[0;1];
end

到这里,其实还没进入我想说的内容。我为了查询Fibonacci数列的算法,搜索了一些资源,基本总结有4种方法(递归,循环,矩阵,通项),最后一种就是用通项公式进行计算。

看到第四种方法时,我懵了,Fibonacci数列还有通项公式?等我再看到通项公式的内容,才发现,这个公式在高中时期就已经学过了。对于公式的内容,自己一直没有记住过。温故知新,这次从头学了一遍通项公式的计算。

具体方法,即从上面的矩阵方法中,求的特征值和特征向量,然后带回到方程中,已知 然后可求通项1

网上还有一些初级数学的方法可以求解,但是我忘记高中时候是怎么推导的了(很可能是用差分方法),如果有机会,翻翻之前的笔记,尽量找出来。