求Fibonacci数可以用一种通用的方法，得到时间复杂度为O(1)的解,下面是一个例子。这个公式涉及到求n次方问题，如果你自己写了一个n次方的函数，复杂度可能是O(n)或者O(lgn)了，在Java上，源码是用了C的类库，优化后可以认为复杂度为O(1)。
求Fibonacci数
求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$即可。
所以我们解决了在计算机上运行产生小数的这个问题。
c编程示例代码
回复删除c语言代码示例Fibonacci数