定義
斐波那契數列：
F[n]{0,n=01,n=1F[n?1]+F[n?2],elseF[n] \begin{cases} 0,n=0 \\ 1,n=1\\ F[n-1]+F[n-2],else \end{cases} F[n]??????0,n=01,n=1F[n?1]+F[n?2],else?
樸素計算法
根據遞歸式F[n]=F[n?1]+F[n?2]F[n]=F[n-1]+F[n-2]F[n]=F[n?1]+F[n?2]進行計算，時間復雜度T(n)=T(n?1)+T(n?2)=Θ(?n)T(n)=T(n-1)+T(n-2)=\Theta(\phi^n)T(n)=T(n?1)+T(n?2)=Θ(?n)，其中?=5+12\phi=\frac{\sqrt{5}+1}{2}?=25?+1?是黃金分割比例。
遞推計算法
從前往后進行遞推，復雜度為Θ(n)\Theta(n)Θ(n)
樸素平方遞歸法
F[n]=?n/5F[n]=\phi^n/\sqrt{5}F[n]=?n/5? rounded to nestest
因為浮點數的表示精度問題，這種方法無法使用。僅僅在理論上可以。
平方遞歸法
定理：
[F[n+1]F[n]F[n]F[n?1]]=[1110]n\begin{bmatrix} F[n+1] & & F[n] \\ & & \\ F[n] & & F[n-1] \end{bmatrix}= \begin{bmatrix} 1 & & 1 \\ & & \\ 1 & & 0 \end{bmatrix}^n ???F[n+1]F[n]??F[n]F[n?1]????=???11??10????n
時間復雜度Θ(logn)\Theta(logn)Θ(logn)
