算法初识——斐波那契数

小灰灰 2023-03-02 13:17 94阅读 0赞

## 复杂度 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTUxMTIzNg_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][20200729152900600.png]

## 时间复杂度 ##

估算程序指令的执行次数

## 空间复杂度 ##

估算所需占用空间

## 斐波那契数 ##

动态规划优化：优化上述方法：只需要存放前两个值即可，减小空间消耗

var fib = function(N) { 
        if(N==0)return 0;
        if(N==2||N==1)return 1;
        var prev=1,curr=1;
        for(var i=3;i<=N;i++){ 
            var sum=prev+curr;
            prev=curr;
            curr=sum;
        }
        return curr;
    };

暴力递推（不推荐）

var fib = function(N) { 
        if(N==0)return 0;
        if(N==1)return 1;
        return fib(N-1)+fib(N-2);
    };

动态规划：数组存放所有值，返回最后一个即可

var fib = function(N) { 
        var dp=[0,1,1];
        for(var i=3;i<=N;i++){ 
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[N];
    };

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80NTUxMTIzNg_size_16_color_FFFFFF_t_70]: /images/20230208/a1eae5df66bf430bbc5da5ca922212f9.png
[20200729152900600.png]: /images/20230208/8b0f34b8c4d04b728ce0cad41982fcb1.png

发表评论取消回复

表情：

评论列表（有 0 条评论，94人围观）

还没有评论，来说两句吧...

相关阅读

相关算法初识——斐波那契数

复杂度 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLm

小灰灰/ 2023年03月02日 13:17/ 0 赞/ 95 阅读

相关寻找斐波那契数

输入正整数N。输出不超过N的最大斐波那契数，及其序号。例如，若输入为：10 则输出为：8 6 include <iostream> inclu

﹏ヽ暗。殇╰゛Y/ 2023年02月21日 12:52/ 0 赞/ 14 阅读

相关 509. 斐波那契数

参考： [面试题10- I. 斐波那契数列][10- I.] [10- I.]: https://blog.csdn.net/zyx_ly/article/detai

朴灿烈づ我的快乐病毒、/ 2022年12月12日 02:18/ 0 赞/ 168 阅读

相关算法 | 斐波那契数列

系列文章目录 -------------------- 文章目录系列文章目录前言具体实现循环法

柔情只为你懂/ 2022年12月10日 08:42/ 0 赞/ 159 阅读

相关 509. 斐波那契数

斐波那契数，通常用 F(n) 表示，形成的序列称为斐波那契数列。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是： F(0) = 0，F(1) =

太过爱你忘了你带给我的痛/ 2022年10月07日 07:50/ 0 赞/ 171 阅读

相关斐波那契查找算法

对于斐波那契查找算法的学习，建议根据程序代码，找一组数据一步步测试一下，会比较容易加深理解。斐波那契查找算法类似于折半查找算法（二分查找算法）对于折半查找：其 mi

ゞ浴缸里的玫瑰/ 2022年08月05日 02:36/ 0 赞/ 248 阅读

相关算法-斐波那契数列

题目：写一个函数，输入为n，求斐波那契（Fibonacci）数列的第n项。斐波那契数列定义如下： ![这里写图片描述][SouthEast] 解题思路：斐波那

「爱情、让人受尽委屈。」/ 2022年06月10日 13:07/ 0 赞/ 216 阅读

相关斐波那契数

> 牛客网《剑指offer》时间限制：`1秒` 空间限制：`32768K` 热度指数：`199742` 解题思路一：如果像这样，将会有大量的计算是重复的，时空

╰+哭是因爲堅強的太久メ/ 2022年06月08日 02:46/ 0 赞/ 184 阅读

相关大斐波那契数

斐波那契数计算公式 : f(n)=f(n-1)+f(n-2) (n>=3) f(1)=1 f(2)=1 对于 n 比较小的情况下，下边的程序就可以实现这个功能

妖狐艹你老母/ 2022年05月26日 02:47/ 0 赞/ 209 阅读

相关 golang 斐波那契数

golang 斐波那契数 package main import "fmt" / 斐波那契数，亦称之为斐波

短命女/ 2021年11月02日 02:02/ 0 赞/ 294 阅读