斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”。

数列: 0, 1, 1, 2, 3, 5, 8, 13, … 规律: 从第三个数开始，后一个数是前两个数之和 公式: F(0) = 0，F(1) = 1, F(n) = F(n-1) + F(n-2)(n>2，n∈N*)

PHP 实现

递归

> 时间复杂度: `O(2^n)`

1
2
3
4
5
6
7

function fib($n) {
    if ($n == 0 || $n == 1) {
        return $n;
    }

    return fib($n - 1) + fib($n - 2);
}

循环

> 时间复杂度: `O(n)`, 空间复杂度: `O(1)`

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

function fib($n) {
    $f0 = 0;
    $f1 = 1;
    $f2 = 0;

    if ($n == 0 || $n == 1) {
        return $n;
    }

    for ($i = 2; $i <= $n; $i++) {
        $f2 = $f0 + $f1;
        $f0 = $f1;
        $f1 = $f2;
    }

    return $f2;
}

矩阵

参考：

算法之矩阵计算斐波那契数列