斐波那契数列

发表于

简介

斐波那契数列是指当前数等于前两位数之和，例如1,1,2,3,5,8,13…… ，一般面试题会问第n位数是多少。我们很容易想到的方法就是使用递归

  1. 递归

    1
    2
    3
    4
    5
    6
    7
    8
    9
    public int fib(int N) {
            if (N == 1) {
                return 1;
            }
            if (N == 2) {
                return 1;
            }
            return fib(N - 1) + fib(N - 2);
    }

    但是如果N逐渐增大的话，消耗的内存会越来越大，时间复杂度为O(2N)，空间复杂度：O(N)。我们一般不会使用递归来算斐波那契数。

  2. 直接使用for循环

    1
    2
    3
    4
    5
    6
    7
    8
    9
    public int fib(int N) {
            int a = 0, b = 1, c = 1;
            for (int i = 2; i < N; i++) {
                a = b + c;
                c = b;
                b = a;
            }
            return b;
    }

    时间复杂度O(N)一层循环，而且只使用了三个变量，大大的减少了内存消耗。

总结

很容易看出，斐波那契数列的规律是很容易找出来，但是如果想要用代码实现这些规律的话，还是有点麻烦，至少我第一次看到这题目是懵的。所以要想学算法就先从记算法开始，把基础打牢了。剩下的无非就是if…else加for循环，关键看你是否有这么一种思想。