斐波那契数列的递推关系定义: enter image description here

根据定义可以得出代码:

enter image description here

存在大量重复计算,效率特别低

解法一、递推关系式的优化

enter image description here

使用闭包缓存 cache 对象,存储计算过的值,以空间换取时间解决效率问题,时间复杂度与空间复杂度都是 O(n)。

解法二、求解通项公式

enter image description here enter image description here

解法三、分治策略

enter image description here

这样,问题就转化为如何计算这个矩阵的 n 次方了,可以采用快速幂的方法,快速幂的代码如下:

enter image description here

注意 JS 整数的最大安全限制不能做精确计算,可以使用 C 语言做更大范围的计算,代码如下:

enter image description here

将快速幂代码中的整型变量 a 变成矩阵,数的乘法变成矩阵乘法,就是矩阵快速幂了:

enter image description here

这里使用 Sylvester 做矩阵计算,matrix 为需要做 n 次幂计算的矩阵,ans 为单位矩阵,该方法完成了下图公式的红框部分

enter image description here

最终代码如下:

enter image description here

注意:因为 JS 的最大安全整数的限制,经过测试 n 大于 79 后的值有问题。