Fibonacci

algorithm

一直以为memorized的递归就是算Fibonacci数列最快的方法了，直到今天看到一个用矩阵的算法，竟然只要o(logn)o(log_n)的复杂度。特此在这里记录一下这个优美的算法。

O(2n)O(2^n)

Fi=Fi−1+Fi−2,F0=F1=1F_{i} = F_{i-1} + F_{i-2}, F_{0} = F_{1} = 1 

1
2
3
4
5
def fib(number):
    if number == 0 or number == 1:
        return 1
    else:
        return fib(number-1) + fib(number-2)

O(n)O(n)

1
2
3
4
5
6
7
8
9
10
def fib(number):
    cur = 1
    pre = 1
    if number == 0 or number == 1:
        return 1
    number -= 1
    while number:
        cur, pre = pre + cur, cur
        number -= 1
    return cur

O(lg(n))O(lg(n))

[FiFi−1]=[Fi−1+Fi−2Fi−1]=[1110]×[Fi−1Fi−2]=[1110]i−1×[F1F0] \left[\begin{matrix} F_i \\ F_{i-1} \end{matrix} \right] = \left[\begin{matrix} F_{i-1} + F_{i-2} \\ F_{i-1} \end{matrix} \right] = \left[\begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix} \right] \times \left[\begin{matrix} F_{i-1} \\ F_{i-2} \end{matrix} \right] = \left[\begin{matrix} 1 & 1 \\ 1 & 0 \end{matrix} \right]^{i-1} \times \left[\begin{matrix} F_1 \\ F_0 \end{matrix} \right] 

1
2
3
4
5
6
7
8
9
10
11
12
import numpy as np
def fib(number):
    factor = np.matrix([[1, 1], [1, 0]])
    res = np.matrix([[1, 1], [1, 0]])
    bonus = np.matrix([[1, 0], [0, 1]])
    while(number > 1):
        if number % 2:
            bonus *= factor
        res = res * res
        number = int(number / 2)
        factor *= factor
    return (res * bonus)[0,0]

Test