欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

斐波那契数列

程序员文章站 2022-07-16 09:39:17
...

斐波那契数列算法

1、概述

斐波那契数列可以说我们从中学就已经接触了这种数列,具体的应用问题不在这里列出来啦,这个数列是长成这样子的:

0、1、1、2、3、5、8、13…

也就是说,后一项是前两项的和,对应的函数表达式可以为:F(n) = F(n-1) + F(n-2),n >1;

下面带来这种算法的几种常见的解题:

2、算法

2.1 递归法

当一个算法可以用一个递归的函数来表达式,我们就可以直接使用编程中的递归思想来解决这种问题。直接上代码

    public static int method_one(int n){
        return n < 2 ? n : method_one(n - 1) + method_one(n - 2);
    }

这个递归算法比较简单,熟练使用三目运算符的话,一行代码就解决了。

时间复杂度:O(2^N)

空间复杂度: O(2N) = O(N)(递归带来的java栈的内存开销)

2.2 自底向上的方法

知道了要计算的那个数的位置,此时直接按照规律累加该位置前面的数列和

    public static int method_two(int n){
        return n < 2 ? n :cash(n);
    }
    public static int cash(int n){
        int[] cash = new int[n + 1];
        cash[0] = 0;
        cash[1] = 1;
        for (int i = 2; i < cash.length; i++) {
            cash[i] = cash[i-1] + cash[i-2];
        }
        return cash[n];
    }

时间复杂度:O(N)

空间复杂度:O(N)(创建数组带来的内存开销)

2.3 自顶向下的方法

这个算法我也是在leetcode上看到的,当时看到的时候以为就是一个普通的递归算法,和第一种没有什么太大的区别。但是仔细看了一遍之后感觉绕不出来。。。应该还是递归这方面的逻辑能力还不够强。这里详细的说一下。

	public static Integer[] cache = new Integer[31];

    public static int method_three(int n){
        if (n < 2){
            return n;
        }
        cache[0] = 0;
        cache[1] = 1;
        return memorize(n);
    }

    public static int memorize(int n){
        if (cache[n] != null) {
            return cache[n];
        }
        // 这里使用了两个递归
        cache[n] = memorize(n-1) + memorize(n-2);
        // 但是仔细观察可以发现,当上面的步骤完成的时候,下面的递归调用实际上返回的是cashe[n]
        // 所以下面的代码等价于
        // return cashe[n];
        return memorize(n);
    }

时间复杂度:O(N)

空间复杂度:O(N)(创建数组带来的内存开销)

我一开始看到这个算法的时候,第一印象就是那么多递归使用,时间复杂度和空间复杂度怎么只有O(N)?于是自己通过调试发现原来并没有那么简单,感觉不是自己所了解的那种递归算法的,这种情况下,最能帮助自己理解的方法就是画图。于是乎,我打开了processOn:

我们假设输入的数字是5,这个数的理想输出结果是5。按照上面的程序,从method_three方法中的return memorize开始,运行流程如下:

斐波那契数列

2.4 自底向上进行迭代

这个算法实际上和我们自己手动计算差不多,就是通过前面的一个一个的数去慢慢地累加,知道累加到需要求得的位置上的数。是最好理解的。

    public static int method_four(int n){
        if (n < 2)
            return n;
        int pre1 = 0;
        int pre2 = 1;
        int current = 0;
        for (int i = 1; i < n; i++) {	// 注意这里循环的次数要与n的位置对应
            current = pre1 + pre2;
            pre1 = pre2;
            pre2 = current;
        }
        return current;
    }

3、总结

想起一开始接触斐波那契数列的时候,因为没有好好学,当从某些地方看到这个数列的时候,只记得那个时候有一种递归的方法写起来很是简洁的——这就是因为懒吧,什么时间、空间复杂度都没有考虑,单单考虑了怎么样写得代码量是最少的。其实那个时候,连简单的递归算法都不能很快地写出了,关键在于不能找准跳出递归的条件。

相关标签: 算法刷题 算法