【剑指offer】斐波那契数列

电玩女神 2022-06-16 13:42 166阅读 0赞

## 题目描述 ##

现在要求输入一个整数n，请你输出斐波那契（Fibonacci）数列的第n项。

## ![斐波那契（Fibonacci）数列定义][Fibonacci] ##

此题易用递归来实现

public int Fibonacci(int n) {
            if (n <= 0)
                return 0;
            if (n == 1)
                return 1;
            return Fibonacci(n - 1) + Fibonacci(n - 2);
        }

但是上述的递归解法有很严重的效率问题。  
以求解 f(10) 为例，想求得 f(10) ，需要先求得 f(9) 和 f(8) 。同样，想求得 f(9) ，需要先求得 f(8) 和 f(7) …… 用树形图来表示如下：

![基于递归求斐波那契数列的第10项的调用过程][10]

不难发现，这棵树中有很多节点是重复的，而且重复的节点数会随着 n 的增大而急剧增加，这意味着计算量也会随之增大。因此递归是不合适的解法。

--------------------

更实用的解法应当将已经得到结果的中间项保存起来；或者每次都从头开始算，即：根据 f(0) 和 f(1) 算出 f(2) ，然后根据 f(1) 和 f(2) 算出 f(3) …….依次算出 f(n) 的值，时间复杂度为 O(n) 。实现代码如下：

public class TestFibonacci {
        public int Fibonacci(int n) {
            int a = 0;
            int b = 1;
            int c = 1;
            if (n <= 0)
                return 0;
            if (n == 1)
                return 1;
            for (int i = 2; i <= n; i++) {
                c = a + b;
                a = b;
                b = c;
            }
            return c;
        }
    
        public static void main(String[] args) {
            for (int i = 0; i < 40; i++) {
                System.out.println(new TestFibonacci().Fibonacci(i));
            }
        }
    }

[Fibonacci]: /images/20220616/5ce5d13e88d14d1f8e53432571dacad1.png
[10]: /images/20220616/a5392640e97e474c957e11b6254745cb.png