PHP之斐波那契数列的N种算法

1. 斐波那契数列简介

斐波那契数列是指满足递推关系式F(n) = F(n-1) + F(n-2)，且F(0) = 0，F(1) = 1的数列。即数列的第 n 项等于前两项之和。斐波那契数列的前几项为0, 1, 1, 2, 3, 5, 8, 13, 21, ... 。

2. 直接递归法

直接递归法是一种最直观的方法，它通过递归调用自身来计算斐波那契数列。

function fibonacci($n) {
    if ($n <= 0) {
        return 0;
    } elseif ($n == 1) {
        return 1;
    } else {
        return fibonacci($n - 1) + fibonacci($n - 2);
    }
}

该方法的时间复杂度为指数级别，当$n$较大时，计算时间会非常长。

3. 记忆化递归法

记忆化递归法是对直接递归法的改进，在每次递归调用之前，先检查是否已经计算过该项。

function fibonacci($n, &$memo = []) {
    if ($n <= 0) {
        return 0;
    } elseif ($n == 1) {
        return 1;
    } elseif (isset($memo[$n])) {
        return $memo[$n];
    } else {
        $memo[$n] = fibonacci($n - 1, $memo) + fibonacci($n - 2, $memo);
        return $memo[$n];
    }
}

通过使用记忆数组 $memo 来保存已经计算过的项，避免了重复计算，大大提高了效率。

4. 迭代法

迭代法是一种不使用递归的计算方法，通过循环计算斐波那契数列。

function fibonacci($n) {
    if ($n <= 0) {
        return 0;
    } elseif ($n == 1) {
        return 1;
    } else {
        $prev1 = 0;
        $prev2 = 1;
        for ($i = 2; $i <= $n; $i++) {
            $current = $prev1 + $prev2;
            $prev1 = $prev2;
            $prev2 = $current;
        }
        return $current;
    }
}

该方法的时间复杂度为线性级别，效率较高，并且不会导致栈溢出的问题。

5. 公式法

斐波那契数列还可以使用公式法来计算，该公式为：

function fibonacci($n) {
    $sqrt5 = sqrt(5);
    $phi = (1 + $sqrt5) / 2;
    return round(pow($phi, $n) / $sqrt5);
}

公式法能够在常数时间内计算出斐波那契数列的第 n 项，但随着 n 的增大，计算结果可能会出现浮点数精度问题。

6. 矩阵法

斐波那契数列还可以使用矩阵法来计算，该方法利用了矩阵的乘法运算。

function fibonacci($n) {
    if ($n <= 0) {
        return 0;
    }
    
    $matrix = [[1, 1], [1, 0]];
    $result = matrixPower($matrix, $n - 1);
    
    return $result[0][0];
}
function matrixPower($matrix, $power) {
    $result = $matrix;
    for ($i = 2; $i <= $power; $i++) {
        $result = matrixMultiply($result, $matrix);
    }
    return $result;
}
function matrixMultiply($matrix1, $matrix2) {
    $rows1 = count($matrix1);
    $cols1 = count($matrix1[0]);
    $cols2 = count($matrix2[0]);
    
    $result = [];
    for ($i = 0; $i < $rows1; $i++) {
        for ($j = 0; $j < $cols2; $j++) {
            $sum = 0;
            for ($k = 0; $k < $cols1; $k++) {
                $sum += $matrix1[$i][$k] * $matrix2[$k][$j];
            }
            $result[$i][$j] = $sum;
        }
    }
    
    return $result;
}

矩阵法是一种高效的计算斐波那契数列的方法，时间复杂度为对数级别。

结论

通过不同的算法，我们可以计算出斐波那契数列的第 N 项。在实际应用中，根据不同的要求选择合适的算法可以提高效率。