斐波那契算法计算 F(n) 需要多少时间

Question

我正在阅读 Skiena 的《算法设计手册》一书中的“8.1.1 通过递归计算斐波那契数”部分。

我无法理解本节下面的段落。

该算法需要多少时间来计算 F(n)？由于 Fn+1/Fn ≈ φ = (1+√5)/2 ≈ 1.61803，这意味着 Fn > 1.6^n。由于我们的递归树有 只有 0 和 1 作为叶子，加起来这么大的数字意味着我们必须有 至少 1.6n 个叶子或过程调用！这个不起眼的小程序需要指数级的时间来运行！

任何人都可以解释一下我在本段中提出的以下问题吗？

• 为什么用Fn+1/Fn来计算算法时间？
• 为什么 Fn > 1.6^n
• 我们如何获得 1.6n 个叶子或过程调用？

请以F(4)为例解释

Answer 1

这是我对我的问题的回答。 如果使用递归计算斐波那契数，计算时间为

F(N)+F(N-1)+F(N-2)+...+F(1) = F(N+2)-2 = O(F(N+2)).

比奈公式证明了

F(N) nearly equal sqrt(1/5) * φ^N

，这个公式也证明了这一点。

• F(k+1)/F(k) 几乎等于 φ。
• 如果检查 k 小，则可以证明 F(k) >= 1.6^k。

但我建议为这个算法计算斐波那契数。

1。使用动态规划
斐波那契数列可以进行动态规划计算，时间为O(N)。
这是显而易见的，因为存在关系 F(N)=F(N-1)+F(N-2)。

2。使用矩阵求幂
其实

( (1 1) (1 0) )^N = ( (F(N+2) F(N+1)) (F(N+1) F(N)) ).

如果您使用指数平方算法，您可以计算其值 O(log N)，因此您可以计算 F(N) 的 O(log(N))。

综上所述，比奈公式不好，因为它使用的是浮点值，所以会产生精度误差。
我建议使用动态规划或矩阵指数来解决这个问题。

Answer 2

对于答案的第一部分，我将从 n 切换到 m。

F(m+1)/F(m) 是用于获取 F(m) 近似值的比率，而不是时间。从 m >= 1 开始，随着 m 的增加，比率 F(m+1)/F(m) 快速收敛到 φ = (1+sqrt(5))/2 ~= 1.61803。这可以重述为 F(m+1) ~= φ F(m)。那么 F(m+2) ~= Φ F(m+1) ~= Φ (Φ F(m)) ~= Φ^2 F(m)，一般来说 F(m+k) ~= Φ^k F(m)，m >= 10 的合理近似值，如本答案末尾的表所示。然后该段落突然跳转到 F(n) > 1.6^n 的陈述，这仅适用于 n >= 72。

接下来的段落讨论了递归树，它只涉及加法，并注意到递归树的叶子节点仅返回 0 (F(0)) 或 1 (F(1))，所以你至少需要 1.6^ n 个（不是 1.6n）个叶节点（返回 1 的 1.6^n 个叶节点）来生成总和 >= 1.6^n。 （再次注意，F(n) > 1.6^n 仅适用于 n >= 72）。

对于更快的算法，卢卡斯序列方法类似于通过平方方法优化矩阵求幂。 64 位无符号整数的最大值为 fib(93) == 12200160415121876738 （在下面的代码中需要 7 次循环）。

/* lucas sequence method */
uint64_t fib(uint64_t n) {
    uint64_t a, b, p, q, aq, qq;
    a = q = 1;
    b = p = 0;
    while(1){
        if (n & 1) {
            aq = a*q;
            a = b*q + aq + a*p;
            b = b*p + aq;
        }
        n >>= 1;
        if (n == 0)
            break;
        qq = q*q;
        q = p*q*2 + qq;
        p = p*p + qq;
    }
    return b;
}

为了了解近似值 F(m+k) ~= φ^k F(m) 的精确度，使用 F(100) 作为测试用例与 m 值 (10, 20, 30, 40)。

F(100)/(φ^90 F(10)) ~= 1.0000661
F(100)/(φ^80 F(20)) ~= 1.00000000437
F(100)/(φ^70 F(30)) ~= 1.000000000000289
F(100)/(φ^60 F(40)) ~= 1.0000000000000000191

Answer 3

这是针对 python 3.0

高度优化的斐波那契函数

def fibonacci_optimized(n):
    if n <= 0:
        return 0

    def matrix_multiply(a, b):
        c = [[0, 0], [0, 0]]
        for i in range(2):
            for j in range(2):
                for k in range(2):
                    c[i][j] += a[i][k] * b[k][j]
        return c

    def matrix_power(matrix, n):
        if n == 1:
            return matrix
        if n % 2 == 0:
            matrix_half = matrix_power(matrix, n // 2)
            return matrix_multiply(matrix_half, matrix_half)
        else:
            matrix_half = matrix_power(matrix, (n - 1) // 2)
            return matrix_multiply(matrix_multiply(matrix_half, matrix_half), matrix)

    base_matrix = [[1, 1], [1, 0]]
    result_matrix = matrix_power(base_matrix, n - 1)
    return result_matrix[0][0]

示例：

导入性能计数器：

from time import perf_counter

代码：

inp = int(input("number to convert: "))
start = perf_counter()
fib = fibonacci_optimized(inp)
end = perf_counter()

print(f"fibonacci output: {fib}")
print(f"time it took: {end-start}")

输出：

number to convert: 1000
fibonacci output: 43466557686937456435688527675040625802564660517371780402481729089536555417949051890403879840079255169295922593080322634775209689623239873322471161642996440906533187938298969649928516003704476137795166849228875
time it took: 9.839999999972093e-05

在大约不到 0.3 秒的时间内，该程序能够计算 一百万个斐波那契数列，并生成涵盖 208,988 个字符的结果。