【刷算法】斐波那契数列

IamDLY 发布于2019-08-22 18:09 / 612人阅读

摘要：题目现在要求输入一个整数，请你输出斐波那契数列的第项。递归操作时间复杂度太高，而且用递归会产生很多重复的操作。非递归操作这种方法就是一次遍历过去就行，计算第个数时，使用了两个变量存储第和第个数，使时间复杂度降低到

题目

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

递归操作O(2^n)

function fibonacci(n) {
    if(n < 1)
        return 0;
    if(n === 1 || n === 2)
        return 1;
    return fibonacci(n-1) + fibonacci(n-2);
}

时间复杂度O(2^n)太高，而且用递归会产生很多重复的操作。

非递归操作O(n)

function Fibonacci(n)
{
    if(n < 1)
        return 0;
    if(n === 1 || n === 2)
        return 1;
    var s1 = 1;
    var s2 = 1;
    var res = 0;
    for(var  i = 3;i <= n;i++) {
        res =  s1 + s2;
        s1 = s2;
        s2 = res;
    }
    
    return res;
}

这种方法就是一次遍历过去就行，计算第n个数时，使用了s1、s2两个变量存储第n-1和第n-2个数，使时间复杂度降低到O(n)

GPU云服务器云服务器波那契数列算法最大子数列解斐波递减数列

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/95551.html

【刷算法】我知道的所有类似斐波那契数列的问题

摘要：有一类算法问题类似斐波那契数列，而且解决办法基本差不多。不了解斐波那契套路的可以看刷算法斐波那契数列跳台阶问题题目描述一只青蛙一次可以跳上级台阶，也可以跳上级。给定整数，求年后牛的数量。分析设为年后牛的数量，则第年牛的来源有两个。有一类算法问题类似斐波那契数列，而且解决办法基本差不多。不了解斐波那契套路的可以看【刷算法】斐波那契数列跳台阶问题题目描述一只青蛙一次可以跳上1级台阶，...

NotFound 2019-08-22 18:10 评论0 收藏0
算法记录 >> 斐波那契数列

摘要：今天去面试笔试题斐波那契数列实现，虽然很简单。回来想想既然算法这么重要那就从这个开始来记录自己的算法库吧。在数学上，斐波纳契数列以如下被以递归的方法定义，，。斐波拉契算法规律很简单，，观察下数列值就很容易总结出来了。一、写在前面算法这块对于大多数程序员（包括我）来说可能都是一个薄弱的地方，如何弥补尼？每个人都知道那就是学习、特别是算法没有任何捷径可走。在这记录平时自己工作和生...

robin 2019-08-16 17:52 评论0 收藏0
太原面经分享：如何用js实现返回斐波那契数列的第n个值的函数

摘要：那其实这个问题还可以换个问法实现一个函数，输入一个数字能返回斐波那契数列的第个值。文章预告更多的前端面试分享我都会第一时间更新在我的公众号闰土大叔里面，欢迎关注面试攒经验，lets go！值此高考来临之际，闲不住的我又双叒叕出发去面试攒经验了，去了公司交待一番流程后，面试官甩给了我一张A4纸，上面写着一道js算法笔试题（一开始我并不知道这是在考察js算法），上面写着1、1、2、3、...

Galence 2019-08-26 12:01 评论0 收藏0
动态规划问题（1）——斐波那契数列

摘要：动态规划有时被称为递归的相反的技术。动态规划方案通常使用一个数组来建立一张表，用于存放被分解成众多子问题的解。今天我们先从我们最熟的斐波那契数列数列开始。斐波那契数列在很多地方都会用上，我是从一个台阶问题发现的，同时知道了动态规划的解法。前段时间一直写了几个算法题目，发现有个很牛逼的算法，动态规划，虽然有的解题思路和动态规划很像，但是当时不知道其中的原理和一些通用性，接下来的几天，通...

Eminjannn 2019-08-21 11:24 评论0 收藏0
数据结构与算法:常见排序算法

摘要：这是一个简单的递归函数，你可以使用它来生成数列中指定序号的数值这个函数的问题在于它的执行效率非常低有太多值在递归调用中被重新计算。本章内容衔接上一章　数据结构与算法：二分查找内容提要两种基本数据结构：数组常见操作: 数组降维、数组去重链表递归：递归是很多算法都使用的一种编程方法　　- 如何将问题分成基线条件和递归条件　　- 分而治之策略解决棘手问题 ...

wuyumin 2019-07-30 15:33 评论0 收藏0