斐波拉契优化
type
status
date
slug
summary
tags
category
icon
password
简单直接的思路
在斐波拉契数列找到上任意两个相邻的数 , ，做如下变化
得到的新 , 实际上就是 , 沿着斐波拉契数列滑动一位的结果。
我们将这种变换记为 ，变化次，记为
当初始 a=0,b=1 时，的 值，就是斐波拉契数列的第 位。
增加复杂度
我们设计一个新的变换方式 ，此处的 p , q 为常量。
当 时。记为
显然，此时的
猜测
我们猜想，存在这样的情况，对于任意的 都能找到新的常量m, n ，满足以下要求。
证明
对于一组值a ,b
使用 进行2次变换
简单替换之后
简单整理
使用 进行1次变换
已知
那么
找到
优化
正如前面提到的，求斐波那契数列的第 n 位 fib ，需要迭代 n 次，是 O(n) 复杂度。
那么，同样也是 O(n) 复杂度。
但是，我们可以对 进行优化
- 当 n 是偶数时，可以变换为
- 当 n 不是偶数时，可以先迭代1次，再进行变换
最后，我们就能得到一个 O(logN) 的斐波那契函数了。
代码
Loading...