简单直接的思路

在斐波拉契数列找到上任意两个相邻的数 \(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}\) 进行优化

  1. \(n\) 是偶数时,可以变换为 \(T_{p,q}(\frac{n}{2})\)
  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
}