斐波那契数列(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)`
function fib($n) {
    if ($n == 0 || $n == 1) {
        return $n;
    }

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

循环

> 时间复杂度: `O(n)`, 空间复杂度: `O(1)`
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;
}

矩阵

参考:

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