三个月算法进阶--day22

动态数组

需要记录的状态是常数级

斐波那契数列通项公式

解析解，有精度误差 $$ f(n) = \frac 1 {\sqrt5} \bigg\lbrack\bigg(\frac {1 + \sqrt5} 2\bigg) ^ n - \bigg(\frac {1 - \sqrt5} 2\bigg) ^ n\bigg\rbrack $$

矩阵快速幂

二分法，时间复杂度O(log(n)) $$ \begin{bmatrix} f(n+1) \cr f(n) \end{bmatrix} = {\begin{bmatrix} 1 & 1 \cr 1 & 0 \end{bmatrix}}^n \begin{bmatrix} f(1) \cr f(0) \end{bmatrix} $$