简单直接的思路
在斐波拉契数列找到上任意两个相邻的数 \(a\), \(b\) ,做如下变化
\[\left\{\begin{matrix}&a_1=b \\&b_1=a+b\end{matrix}\right. \]
得到的新 \(a_1\) , \(b_1\) ,实际上就是 \(a\) , \(b\) 沿着斐波拉契数列滑动一位的结果。
我们将这种变换记为 \(fib\) ,变化\(n\)次,记为\(fib(n)\)
当初始 \(a=0,b=1\) 时,\(fib(n)\)的 \(a\) 值,就是斐波拉契数列的第 \(n\) 位。
增加复杂度
我们设计一个新的变换方式 \(T_{p,q}\) ,此处的 \(p\) , \(q\) 为常量。
\[\left\{\begin{matrix}&a_1=a*p+b*q \\&b_1=a*q+b*p+b*q\end{matrix}\right. \]
当\(\left\{\begin{matrix}p=0 \\q=1\end{matrix}\right.\) 时。记为\(T_{0,1}\)
\[\left\{\begin{matrix}&a_1=a*0+b*1 \\ &b_1=a*1+b*0+b*1\end{matrix}\right. \Rightarrow \left\{\begin{matrix}&a_1=b\\ &b_1=a+b\end{matrix}\right. \]
显然,此时的\(T_{0,1}=fib\)
猜测
我们猜想,存在这样的情况,对于任意的\(T_{p,q}\) 都能找到新的常量\(m\), \(n\) ,满足以下要求。
\[T_{p,q}(2)=T_{m,n}(1) \]
证明
对于一组值\(a\) ,\(b\)
使用\(T_{p,q}\) 进行2次变换
\[T_{p,q}(1)\left\{\begin{matrix}&a_1=a*p+b*q \\&b_1=a*q+b*p+b*q\end{matrix}\right. \]
\[T_{p,q}(2)\left\{\begin{matrix}&a_2=a_1*p+b_1*q \\&b_2=a_1*q+b_1*p+b_1*q\end{matrix}\right. \]
简单替换之后
\[T_{p,q}(2)\left\{\begin{matrix}&a_2=(a*p+b*q)*p+(a*q+b*p+b*q)*q \\&b_2=(a*p+b*q)*q+(a*q+b*p+b*q)*p+(a*q+b*p+b*q)*q\end{matrix}\right. \]
简单整理
\[T_{p,q}(2)\left\{\begin{matrix}&a_2=ap^2+bpq+aq^2+bpq+bq^2\\ &b_2=apq+bq^2+apq+bp^2+bpq+aq^2+bpq+bq^2\end{matrix}\right. \]
使用\(T_{m,n}\) 进行1次变换
\[T_{m,n}(1)\left\{\begin{matrix}&a_1=am+bn \\&b_1=an+bm+bn\end{matrix}\right.\\ \]
已知 \(T_{P,Q}(2)=T_{M,N}(1)\) 那么
\[am+bn=ap^2+bpq+aq^2+bpq+bq^2 \]
\[an+bm+bn=apq+bq^2+apq+bp^2+bpq+aq^2+bpq+bq^2 \]
找到
\[\left\{\begin{matrix}&m=p^2+q^2\\ &n=q^2+2pq\end{matrix}\right. \]
优化
正如前面提到的,求斐波那契数列的第 \(n\) 位 \(fib\) ,需要迭代 \(n\) 次,是 \(O(n)\) 复杂度。
那么,\(T_{0,1}\) 同样也是 \(O(n)\) 复杂度。
但是,我们可以对 \(T_{0,1}\) 进行优化
- 当 \(n\) 是偶数时,可以变换为 \(T_{p,q}(\frac{n}{2})\)
- 当 \(n\) 不是偶数时,可以先迭代1次,再进行变换
最后,我们就能得到一个 \(O(logN)\) 的斐波那契函数了。
代码
func fib(n int) int {
a, b := 0, 1
for i := 0; i < n; i++ {
a, b = b, a+b
}
return a
}
func fibT(n int) int {
a, b, p, q := 0, 1, 0, 1
for n != 0 {
if n%2 != 0 {
a, b = a*p+b*q, a*q+b*p+b*q
n--
} else {
p, q = p*p+q*q, q*q+(p*q<<1)
n = n >> 1
}
}
return a
}