算法之路（三）----查找斐波纳契数列中第 N 个数

算法题目

查找斐波纳契数列中第 N 个数。 所谓的斐波纳契数列是指：

• 前2个数是 0 和 1 。
• 第 i 个数是第 i-1 个数和第i-2 个数的和。

斐波纳契数列的前10个数字是： 0, 1, 1, 2, 3, 5, 8, 13, 21, 34 ...

分析

斐波那契数列满足公式f(n) = f(n-1) + f(n-2)，n > 0。这里我们的第一想法是使用递归，可是直接翻译公式出来的递归调用是这样的：

int fib(int n) {
    if (n == 1) {
        return 0;
    }
    if (n == 2){
        return 1;
    }
    
    return fib(n - 1) + fib(n - 2);
}

可是这个函数的事件复杂度恰好是最糟糕的指数级。怎么来证明它是指数级呢？

你可以先用一些测试数来测试一下这个方法: 当n = 40时，大概就需要0.5秒才能计算出来; 当n 为50时，需要等很久才能计算出实际的值。

下面来推导它的时间复杂度。 对于斐波那契数，有定理 ：当n >= 0时，Fn < (5/3)n。 首先使用归纳法来证明。对于基准情形，F1 = 0 < 5/3，F2 = 1 < 5/3。 然后假设i = 1，2，3，...，n 成立；这就是归纳假设。那么我们只需要证明出Fn+1 < (5/3)n+1 即可。 根据公式我们可以得出Fn+1 = Fn + Fn-1。 推到过程如下： Fn+1 < (5/3)n + (5/3)n-1 Fn+1 < (3/5)(5/3)n+1 + (3/5)2(5/3)n+1 Fn+1 < (24/25)(5/3)n+1 < (5/3)n+1 得证 Fn+1 < (5/3)n+1。

同样的证明过程，可以证明出当n > 4时， Fn > (3/2)n。 而T(n) = T(n-1) + T(n-2) + 3。 T(n) >= fib(n) >= (3/2)n。 因此这个函数的运行时间是以指数的速度增长。

可能有点不同的是，有的斐波那契数列是从1，1，2，3，.... 开始，所以有些微的差别。 这只是对级数做了一次平移。我们可以找一些方便证明的情况来证明。

更优解法

其实上面的递归违反了递归的合成效益法则，才导致了运行时间的指数级增长。 递归的四条基本准则： 1、基准情形。必须有总有某些基准情形，它无须递归就能解出。 2、不断推进。对于那些需要递归求解的情形，每一次递归调用都必须要使求解状况朝接近基准情形的方向推进。 3、设计法则。假设所有的递归调用都能运行。 4、合成效益法则。在求解一个问题的同一示例时，切勿在不同的递归调用中做重复性的工作。 我们可以利用一个简单的for 循环来求解第N个斐波那契数。

int fibonacci(int n) {
    if (n == 1) {
        return 0;
    }
    
    if (n == 2) {
        return 1;
    }
    
    int a = 0;
    int b = 1;
    int c = 0;
    for (int i = 3; i < n + 1; i++) {
        c = a + b;
        a = b;
        b = c;
    }
    return c;
}

使用两个变量分别保存f(n-1) 和f (n-2)，然后从基准情况开始往第 n 个数推进。 改进后的函数时间复杂度是O(n)，运行时间大概是 （3n - 1）大大减少了运行时间。