时间复杂度为1的求解fibonacci数方法@ 编程狗的博客

求Fibonacci数可以用一种通用的方法，得到时间复杂度为O(1)的解,下面是一个例子。这个公式涉及到求n次方问题，如果你自己写了一个n次方的函数，复杂度可能是O(n)或者O(lgn)了，在Java上，源码是用了C的类库，优化后可以认为复杂度为O(1)。

求Fibonacci数可以用一种通用的方法，得到时间复杂度为

$O(1)$ 的解,下面是一个例子。已知Fibonacci数表示如下：

$\begin{equation}\label{fib} f(n) = \begin{cases} 0 & \quad n =0\\ 1 & \quad n =1\\ f(n-1)+f(n-2) & \quad n >1\\ \end{cases} \end{equation}$ 现在设

$f(n)=a^n$ ,则有

$a^n=a^{n-1} +a^{n-2}$ ,所以：

$\begin{equation}\label{aaa} a^2-a-1=0 \end{equation}$ 其解为：

$\begin{equation} a=\begin{cases} \frac{1-\sqrt{5}}{2}\\ \frac{1+\sqrt{5}}{2}\\ \end{cases} \end{equation}$ 那么

$f(n)$ 的解包含a的根。则有：

$\begin{equation} f(n)= A\cdot(\frac{1-\sqrt{5}}{2})^n + B\cdot(\frac{1+\sqrt{5}}{2})^n \end{equation}$ 又

$f(0) = 0$ ,

$f(1)=1$ ,则有

$\begin{equation} \begin{cases} 0 = A+B\\ 1 = A\cdot(\frac{1-\sqrt{5}}{2}) + B\cdot(\frac{1+\sqrt{5}}{2})\\ \end{cases} \end{equation}$ 可以解得：

$\begin{equation} \begin{cases} A=-\sqrt{5}\\ B=\sqrt{5}\\ \end{cases} \end{equation}$ 所以

$\begin{equation} f(n)=\frac{1}{\sqrt{5}}\big( (\frac{1+\sqrt{5}}{2})^n - (\frac{1-\sqrt{5}}{2})^n ) \end{equation}$

只能说Fibonacci数是一个非常奇特的数，这是一个可以用无理数表示整数的例子。但是无理数在计算机上运行的时候，运算过程中可能产生小数，导致最终结果不是整数。这个问题很好解决，先证明如下定理：

$\begin{equation} f(n) = [\frac{(\frac{1+\sqrt{5}}{2})^n}{\sqrt{5}}] + C_n \end{equation}$ 其中：当

$a\geq0时$ ，使用

$[a]$ 代表

$a$ 的整数部分；当

$n$ 是偶数的时候，令

$C_n=0$ ,当

$n$ 是奇数的时候，令

$C_n=1$ .我们观察到

$\begin{equation} p(n)=\frac{(\frac{1-\sqrt{5}}{2})^n}{\sqrt{5}} \end{equation}$ 是一个单调递减的函数，有

$\begin{equation} 0 \verb|<| p(n) \verb|<| 1\end{equation}$ 所以我们只计算

$f(n)$ 的整数部分，

$\begin{equation} q(n)=\frac{(\frac{1+\sqrt{5}}{2})^n}{\sqrt{5}} \end{equation}$ 根据情况是否补

$1$ 即可。所以我们解决了在计算机上运行产生小数的这个问题。

编程狗的博客