算法初识——斐波那契数

小灰灰 2023-03-02 13:17 111阅读 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 条评论，111人围观）

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

相关阅读

相关 509. 斐波那契数

509. 斐波那契数题干描述动态规划五部曲 1. 确定dp数组以及下标的含义 2. 确定递推公式 3. dp数组如

朴灿烈づ我的快乐病毒、/ 2023年10月16日 15:50/ 0 赞/ 25 阅读

相关斐波那契数

1、用java代码去计算 / @Title:斐波那契数(这个数列从第3项开始，每一项都等于前两项之和) @Author: longzhou

た入场券/ 2023年06月15日 13:29/ 0 赞/ 23 阅读

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

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

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

相关寻找斐波那契数

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

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

相关 509. 斐波那契数

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

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

相关 509. 斐波那契数

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

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

相关斐波那契查找算法

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

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

相关斐波那契数

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

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

相关大斐波那契数

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

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

相关 golang 斐波那契数

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

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