斐波那契数列（php实现）

描述

斐波那契数列指的是这样一个数列：1、1、2、3、5、8、13、21、34...

规则 : 有N个数，第i个数的值 N(i)= N(i-1) + N(i-2)

需求: 给出下标i ,求第i 的个数的值

例如 : 2 = 1+1
3 = 2+1
5 = 3+2
8 = 5 + 3
...

用php写

递归求解

function get($index){
    if ($index < 3 )return 1;
    return get($index-1)+get($index-2);
}
echo get(10);

指数级的时间复杂度

优化解法

$n_1 = 1;
$n_2 = $n_1;
$n_3  =$n_1 + $n_2;
$n_4 = $n_3 + $n_2;
$n_5 = $n_4 + $n_3;
.....

n1,n2 是固定的1，
n3是n1+n2，计算了1次

n4 是n3 + n2 计算了2次

n5 是 n4+ n3 计算了3次

那么第n个数就是第n-1 个数+第n-2个数，计算了n-2次.这样复杂度就变成了O(n),可以写一个for循环。我们需要保留第n-1个数的值 NUM(n-1)和第n-2个数的值NUM(n-2)。

function getF($index)
{
    if ($index < 3) return 1;
    $n_1 = 1;
    $n_2 = $n_1;
    for ($i = 0; $i < $index - 2; $i++) {
        $last = $n_1; // 保存上一次运算后 第n-2个数的值
        $n_1 = $n_2; // 本次操作结束后 第n-1个数的值
        $n_2 = $n_2 + $last; // 这里是第n-2个数的值 + 上一次 第n-1个数的值
    }
    return $n_2;
}