一分钟学算法-递归-斐波那契数列递归解法及优化
一分钟学一个算法题目。
今天我们要学习的是用递归算法求解斐波那契数列。
首先我们要知道什么是斐波那契数列。
斐波那契数列,又称黄金分割数列,是一个经典的数学数列,其特点是第一项,第二项为1,后面每个数字都是前两个数字之和。推导过程如视频所示,非常非常简单。
知道了斐波那契数列的定义后,我们将其代入到递归问题的分析当中。
首先确定边界条件,就是第一项和第二项为1,接着确定递归关系,后一项等于前两项的和。确定了上面这些关系,我们就可以写出下面的代码了。
def fib(x):# 边界条件if x==1 or x==2: return 1# 递归关系return fib(x-2)+fib(x-1)print(fib(1))
print(fib(2))
print(fib(3))
print(fib(4))
print(fib(5))
print(fib(6))
没错,去掉注释和空行后只有三行代码,简洁精炼是递归问题的共性,你学习过肯定深有体会。下面我们稍微解读下代码,这是一个求解斐波那契数列第n项数字的函数,函数名为fib,接受一个参数n。
如果n等于1或者2,那么就返回1,否则就返回fib(n-2)与fib(n-1)的和,怎么样,脑子转过来弯了吗?没错,就是这么简单。我们来尝试运行使用函数检验一下正确性,发现都输出了正确结果。
但是这个函数还有很大的优化空间,在哪里呢?没错,递归算法让我们使用简洁的代码解决复杂的问题。但他的时间复杂度很高,一不小心没做好边界与转换关系判断就会导致无限循环或者栈溢出。
我们以此题为例,假如我们要求解斐波那契数列的第一百项数字,那麽我们会得到这张调用关系图,同一项会被重复计算非常非常多次。所以你运行此函数可能会导致很长时间都计算不出结果。
那么,我们该如何优化呢?
我们该如何避免重复计算某一项的值呢?
我们可以在计算出每一项的时候,把计算结果存到一个字典里。这样我们在每次计算前先去字典中寻找这一项,如果有值,那么直接拿出来使用,如果没有,再计算它。
这样的话我们就可以保证每一项仅被计算一次。运行时间也将会大大缩短。按照以上思路我们对代码进行如下变化。
def fib(n):# 边界条件if n==1 or n==2: return 1if hash.get(n,0):return hash.get(n)# 递归关系ans=fib(n-2)+fib(n-1)hash[ans]=ansreturn anshash={}
在代码中我们增加了以下变化:
每次计算某一项时先去集合中查询,如果已经计算过,那么直接返回值,如果没有,则计算,并且在返回值之前先在集合中记录一下。
这样代码的算法复杂度已经优化了很多了,没有优化版本求解第70项都非常费力,现在优化后已经可以轻松算出第100项了。但要想算出第一百项还是需要很久时间。
因为其中还存在大量的分支判断。
而且此解法还远远不是最优解法,关注up主,我们下集就来讲讲更快的方法。
相关文章:

一分钟学算法-递归-斐波那契数列递归解法及优化
一分钟学一个算法题目。 今天我们要学习的是用递归算法求解斐波那契数列。 首先我们要知道什么是斐波那契数列。 斐波那契数列,又称黄金分割数列,是一个经典的数学数列,其特点是第一项,第二项为1,后面每个数字都是前…...
选择Rust,并在Ubuntu上使用Rust
在过去的 8 年里,Rust 一直是开发人员最喜欢的语言,并且越来越被各种规模的软件公司采用。然而,它的许多高级规则和抽象创造了一个陡峭的初始学习曲线,这可能会给人留下 Rust 是少数人的保留的印象,但这与事实相去甚远…...

SVM详解
公式太多了,就用图片用笔记呈现,SVM虽然算法本质一目了然,但其中用到的数学推导还是挺多的,其中拉格朗日约束关于α>0这块证明我看了很长时间,到底是因为悟性不够。对偶问题也是,用了一个简单的例子才明…...

mysql全文检索使用
数据库数据量10万左右,使用like %test%要耗费30秒左右,放弃该办法 使用mysql的全文检索 第一步:建立索引 首先修改一下设置: my.ini中ngram_token_size 1 可以通过 show variables like %token%;来查看 接下来建立索引:alter table 表名 add f…...

opencv 进阶17-使用K最近邻和比率检验过滤匹配(图像匹配)
K最近邻(K-Nearest Neighbors,简称KNN)和比率检验(Ratio Test)是在计算机视觉中用于特征匹配的常见技术。它们通常与特征描述子(例如SIFT、SURF、ORB等)一起使用,以在图像中找到相似…...

Mac Flutter web环境搭建
获取 Flutter SDK 下载以下安装包来获取最新的 stable Flutter SDK将文件解压到目标路径, 比如: cd ~/development $ unzip ~/Downloads/flutter_macos_3.13.0-stable.zip 配置 flutter 的 PATH 环境变量: export PATH"$PATH:pwd/flutter/bin" // 这个命…...

在外SSH远程连接macOS服务器
文章目录 前言1. macOS打开远程登录2. 局域网内测试ssh远程3. 公网ssh远程连接macOS3.1 macOS安装配置cpolar3.2 获取ssh隧道公网地址3.3 测试公网ssh远程连接macOS 4. 配置公网固定TCP地址4.1 保留一个固定TCP端口地址4.2 配置固定TCP端口地址 5. 使用固定TCP端口地址ssh远程 …...

Dockerfile文件详细
Dockerfile 是一个文本文件,里面包含组装新镜像时用到的基础镜像和各种指令,使用dockerfile 文件来定义镜像,然后运行镜像,启动容器。 dockerfile文件的组成部分 一个dockerfile文件包含以下部分: 基础镜像信息&…...

C语言学习系列-->看淡指针(3)
文章目录 一、字符指针变量二、数组指针变量2.1 概述2.2 数组指针初始化 三、二维数组传参本质四、函数指针五、typedef关键字六、函数指针数组 一、字符指针变量 在指针的类型中我们知道有⼀种指针类型为字符指针 char* 一般使用: #include<stdio.h>int main…...

Java抽象类详解
抽象类 抽象类的概念 在面向对象的概念中,所有的对象都是通过类来描绘的,但是反过来,并不是所有的类都是来描绘对象的,如果一个类中没有包含足够的信息来描绘一个具体的对象,这样的类就是抽象类。比如: 说…...

06-微信小程序-注册程序-场景值
06-微信小程序-注册程序 文章目录 注册小程序参数 Object object案例代码 场景值场景值作用场景值列表案例代码 注册小程序 每个小程序都需要在 app.js 中调用 App 方法注册小程序实例,绑定生命周期回调函数、错误监听和页面不存在监听函数等。 详细的参数含义和使…...

多种方法实现 Nginx 隐藏式跳转(隐式URL,即浏览器 URL 跳转后保持不变)
多种方法实现 Nginx 隐藏式跳转(隐式URL,即浏览器 URL 跳转后保持不变)。 一个新项目,后端使用 PHP 实现,前端不做路由,提供一个模板,由后端路由控制。 Route::get(pages/{name}, [\App\Http\Controllers\ResourceController::class, getResourceVersion])...

视频汇聚云平台EasyCVR视频监控管理平台进行SDN转推的操作步骤
视频汇聚/视频云存储/集中存储/视频监控管理平台EasyCVR能在复杂的网络环境中,将分散的各类视频资源进行统一汇聚、整合、集中管理,实现视频资源的鉴权管理、按需调阅、全网分发、云存储、智能分析等,视频智能分析平台EasyCVR融合性强、开放度…...

SQL 语句继续学习之记录二
三, 聚合与排序 对表进行聚合查询,即使用聚合函数对表中的列进行合计值或者平均值等合计操作。 通常,聚合函数会对null以外的对象进行合计。但是只有count 函数例外,使用count(*) 可以查出包含null在内的全部数据行数。 使用dis…...

【Python原创设计】基于Python Flask 机器学习的全国+上海气象数据采集预测可视化系统-附下载链接以及详细论文报告,原创项目其他均为抄袭
基于Python Flask 机器学习的全国上海气象数据采集预测可视化系统 一、项目简介二、开发环境三、项目技术四、功能结构五、运行截图六、功能实现七、数据库设计八、源码获取 一、项目简介 在信息科技蓬勃发展的当代,我们推出了一款基于Python Flask的全国上海气象数…...

Unity进阶–通过PhotonServer实现人物选择和多人同步–PhotonServer(四)
文章目录 Unity进阶–通过PhotonServer实现人物选择和多人同步–PhotonServer(四)服务端客户端 Unity进阶–通过PhotonServer实现人物选择和多人同步–PhotonServer(四) 服务端 服务端结构如下: UserModel using System; using System.Collections.Generic; usin…...
【Go 基础篇】Go语言获取用户终端输入:实现交互式程序的关键一步
介绍 在许多编程场景中,我们需要编写交互式程序,以便用户可以在终端中输入数据并与程序进行交互。Go语言提供了丰富的方式来获取用户终端输入,使得编写交互式程序变得简单而有趣。本篇博客将深入探讨Go语言中获取用户终端输入的各种方法&…...

学习笔记:Opencv实现拉普拉斯图像锐化算法
2023.8.19 为了在暑假内实现深度学习的进阶学习,Copy大神的代码,记录学习日常 图像锐化的百科: 图像锐化算法-sharpen_lemonHe_的博客-CSDN博客 在环境配置中要配置opencv: pip install opencv-contrib-python Code and lena.png…...

如何在前端实现WebSocket发送和接收UDP消息(多线程模式)
目录 简介:步骤1:创建WebSocket连接步骤2:创建Web Workers步骤3:发送和接收UDP消息(多线程模式)结束语: 简介: 本文将继续介绍如何在前端应用中利用WebSocket技术发送和接收UDP消息…...

【微服务】一文了解 Nacos
一文了解 Nacos Nacos 在阿里巴巴起源于 2008 2008 2008 年五彩石项目(完成微服务拆分和业务中台建设),成长于十年双十一的洪峰考验,沉淀了简单易用、稳定可靠、性能卓越的核心竞争力。 随着云计算兴起, 2018 2018 20…...

多模态2025:技术路线“神仙打架”,视频生成冲上云霄
文|魏琳华 编|王一粟 一场大会,聚集了中国多模态大模型的“半壁江山”。 智源大会2025为期两天的论坛中,汇集了学界、创业公司和大厂等三方的热门选手,关于多模态的集中讨论达到了前所未有的热度。其中,…...
SkyWalking 10.2.0 SWCK 配置过程
SkyWalking 10.2.0 & SWCK 配置过程 skywalking oap-server & ui 使用Docker安装在K8S集群以外,K8S集群中的微服务使用initContainer按命名空间将skywalking-java-agent注入到业务容器中。 SWCK有整套的解决方案,全安装在K8S群集中。 具体可参…...

React第五十七节 Router中RouterProvider使用详解及注意事项
前言 在 React Router v6.4 中,RouterProvider 是一个核心组件,用于提供基于数据路由(data routers)的新型路由方案。 它替代了传统的 <BrowserRouter>,支持更强大的数据加载和操作功能(如 loader 和…...
DockerHub与私有镜像仓库在容器化中的应用与管理
哈喽,大家好,我是左手python! Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库,用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...

第一篇:Agent2Agent (A2A) 协议——协作式人工智能的黎明
AI 领域的快速发展正在催生一个新时代,智能代理(agents)不再是孤立的个体,而是能够像一个数字团队一样协作。然而,当前 AI 生态系统的碎片化阻碍了这一愿景的实现,导致了“AI 巴别塔问题”——不同代理之间…...

Cloudflare 从 Nginx 到 Pingora:性能、效率与安全的全面升级
在互联网的快速发展中,高性能、高效率和高安全性的网络服务成为了各大互联网基础设施提供商的核心追求。Cloudflare 作为全球领先的互联网安全和基础设施公司,近期做出了一个重大技术决策:弃用长期使用的 Nginx,转而采用其内部开发…...

基于Java+VUE+MariaDB实现(Web)仿小米商城
仿小米商城 环境安装 nodejs maven JDK11 运行 mvn clean install -DskipTestscd adminmvn spring-boot:runcd ../webmvn spring-boot:runcd ../xiaomi-store-admin-vuenpm installnpm run servecd ../xiaomi-store-vuenpm installnpm run serve 注意:运行前…...

TSN交换机正在重构工业网络,PROFINET和EtherCAT会被取代吗?
在工业自动化持续演进的今天,通信网络的角色正变得愈发关键。 2025年6月6日,为期三天的华南国际工业博览会在深圳国际会展中心(宝安)圆满落幕。作为国内工业通信领域的技术型企业,光路科技(Fiberroad&…...

Cilium动手实验室: 精通之旅---13.Cilium LoadBalancer IPAM and L2 Service Announcement
Cilium动手实验室: 精通之旅---13.Cilium LoadBalancer IPAM and L2 Service Announcement 1. LAB环境2. L2公告策略2.1 部署Death Star2.2 访问服务2.3 部署L2公告策略2.4 服务宣告 3. 可视化 ARP 流量3.1 部署新服务3.2 准备可视化3.3 再次请求 4. 自动IPAM4.1 IPAM Pool4.2 …...

C++实现分布式网络通信框架RPC(2)——rpc发布端
有了上篇文章的项目的基本知识的了解,现在我们就开始构建项目。 目录 一、构建工程目录 二、本地服务发布成RPC服务 2.1理解RPC发布 2.2实现 三、Mprpc框架的基础类设计 3.1框架的初始化类 MprpcApplication 代码实现 3.2读取配置文件类 MprpcConfig 代码实现…...