在递归算法中获得更快的代码

Question

我正在学习C中的递归.我的问题是:打印80个第一个Fibonacci数(使用递归)

这是本书的代码:

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

long long f[100];

long long fib(int n)
{
    if (n<2) return 1;
    if (f[n]>0) return f[n];
    f[n] = fib(n-1)+fib(n-2);       
    return f[n];
}
int main()
{
    int i;
    for (i = 0; i<= 80; i++) printf ("%lld \n", fib(i));
    system ("pause");
    return 0;
}

使用此代码,我的程序运行速度非常快,我立即获得80个Fibonacci数字.

但是,当我删除第10行时:

if (f[n] > 0) return f[n];

程序变得非常慢,打印所有80个数字大约需要20秒.有谁能解释为什么？谢谢.

Answer 1

首先,如果您使用天真的公式进行递归(即,如果您在代码中注释第10行)

F(n) = F(n-1) + F(n-2)

正如您所看到的,它不止一次地计算了许多值(因此效率很低),换句话说,当每个节点解析成2个分支时,它们具有指数时间复杂度(O(2^n))

因此,如果他保存我们的工作并在再次发生时使用它来解决同样的问题:我们可以实现线性时间复杂度(O(n))

在您的代码中,数组f是cache

但是,如果您有兴趣知道(虽然它没有被问及),您可以Fib(n)通过矩阵指数以对数时间复杂度计算或任何比这更快的线性递归关系.(O(logN))

Answer 2

该算法将先前计算的值缓存在数组中f.该数组初始化为0(因为它是静态的).你提到的测试删除检查是否有缓存值,并返回它.通过消除测试,您永远不会使用缓存值,而是每次都重新计算.这很昂贵,因为你最终会多次计算相同的值.

编辑:

我可以补充一点,如果这是一本书中的代码,你应该得到一本不同的书,因为它的风格很差.在C中,我会写一些类似于:

long long
fib( int n )
{
    static long long cache[100];    //  limit scope, and give it a good name
    assert( n >= 0 && n < sizeof(cache) / sizeof(cache[0]) );
                                    //  make sure input is legal.
    if ( cache[n] == 0 ) {
        cache[n] = n < 2 ? 1 : fib( n - 1 ) + fib( n - 2 );
    }
    return cache[n];
}

您会注意到代码实际上更简单.

当然,在C++中,我会使用std::vector缓存,所以我没有一些隐藏的硬编码限制.(就此而言,在C中,我可能会实现类似的东西,以避免硬编码限制.但我不希望在教学示例中.)