使用DeepSeek,优化斐波那契数函数,效果相当不错

下面这段代码定义了一个递归函数 fibonacci,用于计算第 n 个斐波那契数。

def fibonacci(n):if n <= 1:return nelse:return fibonacci(n - 1) + fibonacci(n - 2)

虽然代码逻辑正确,但其性能较差,尤其是对于较大的 n 值,其复杂度较高:

  • 时间复杂度:当前代码的时间复杂度为 O(2^n),因为每次调用 fibonacci(n) 会递归调用 fibonacci(n-1)fibonacci(n-2),导致重复计算。
  • 空间复杂度:空间复杂度为 O(n),因为递归调用栈的深度为 n
优化 1:使用动态规划(自顶向下,带备忘录)

通过缓存已经计算过的斐波那契数,避免重复计算,可以将时间复杂度优化到 O(n)

def fibonacci(n, memo={}):if n <= 1:return nif n not in memo:memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)return memo[n]
优化 2:使用动态规划(自底向上,迭代法)

通过迭代的方式计算斐波那契数,避免递归调用栈的开销,同时将空间复杂度优化到 O(1)

def fibonacci(n):if n <= 1:return na, b = 0, 1for _ in range(2, n + 1):a, b = b, a + breturn b
优化 3:使用 Python 内置的 lru_cache 装饰器

Python 的 functools 模块提供了 lru_cache 装饰器,可以自动缓存函数的结果,避免重复计算。

from functools import lru_cache@lru_cache(maxsize=None)
def fibonacci(n):if n <= 1:return nreturn fibonacci(n - 1) + fibonacci(n - 2)
优化4:使用矩阵快速幂算法(高级优化)

对于非常大的 n 值,可以使用矩阵快速幂算法将时间复杂度优化到 O(log n)。这种方法适合对性能要求极高的场景。

def matrix_mult(a, b):return [[a[0][0] * b[0][0] + a[0][1] * b[1][0], a[0][0] * b[0][1] + a[0][1] * b[1][1]],[a[1][0] * b[0][0] + a[1][1] * b[1][0], a[1][0] * b[0][1] + a[1][1] * b[1][1]],]def matrix_pow(matrix, power):result = [[1, 0], [0, 1]]  # Identity matrixwhile power > 0:if power % 2 == 1:result = matrix_mult(result, matrix)matrix = matrix_mult(matrix, matrix)power //= 2return resultdef fibonacci(n):if n <= 1:return nmatrix = [[1, 1], [1, 0]]result = matrix_pow(matrix, n - 1)return result[0][0]

推荐使用 优化建议 2(迭代法),因为它在时间复杂度和空间复杂度上都有较好的平衡,且代码简洁易读。优化后的代码如下:

def fibonacci(n):if n <= 1:return na, b = 0, 1for _ in range(2, n + 1):a, b = b, a + breturn b

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/35308.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

LeRobot源码剖析——对机器人各个动作策略的统一封装:包含ALOHA ACT、Diffusion Policy、VLA模型π0

前言 过去2年多的深入超过此前7年&#xff0c;全靠夜以继日的勤奋&#xff0c;一天当两天用&#xff0c;抠论文 抠代码 和大模型及具身同事讨论&#xff0c;是目前日常 而具身库里&#xff0c;idp3、π0、lerobot值得反复研究&#xff0c;故&#xff0c;近期我一直在抠π0及l…

ISP--Gamma Correction

文章目录 现象Gamma产生的原因CRT属性导致人眼的亮度特性 gamma校正LUT法线性插值法模拟gamma法 现象 从上往下看左侧黑色块黑得越来越严重&#xff0c;对比度也在逐渐加深。此时灰阶的高亮区获得的数据位变少&#xff0c;暗区获得的数据位变多&#xff0c;暗区细节会更多。但是…

光谱相机识别瓶子材质的技术原理和应用案例

一、技术原理 ‌光谱特征差异识别‌ 不同材质的塑料&#xff08;如PET、PP、PE等&#xff09;因化学结构差异&#xff0c;在近红外或可见光波段会呈现独特的光谱反射曲线。例如&#xff0c;高光谱相机通过分析数百个窄波段的光谱数据&#xff0c;可生成每种材质的“光谱指纹”…

某快餐店用户市场数据挖掘与可视化

1、必要库的载入 import pandas as pd import matplotlib.pyplot as plt import seaborn as sns2、加载并清洗数据 # 2.1 加载数据 df pd.read_csv(/home/mw/input/survey6263/mcdonalds.csv)# 2.2 数据清洗 # 2.2.1 检查缺失值 print(缺失值情况&#xff1a;) print(df.isn…

MySQL 衍生表(Derived Tables)

在SQL的查询语句select …. from …中&#xff0c;跟在from子句后面的通常是一张拥有定义的实体表&#xff0c;而有的时候我们会用子查询来扮演实体表的角色&#xff0c;这个在from子句中的子查询会返回一个结果集&#xff0c;这个结果集可以像普通的实体表一样查询、连接&…

Electron使用WebAssembly实现CRC-16 MAXIM校验

Electron使用WebAssembly实现CRC-16 MAXIM校验 将C/C语言代码&#xff0c;经由WebAssembly编译为库函数&#xff0c;可以在JS语言环境进行调用。这里介绍在Electron工具环境使用WebAssembly调用CRC-16 MAXIM格式校验的方式。 CRC-16 MAXIM校验函数WebAssembly源文件 C语言实…

HTB 学习笔记 【中/英】《前端 vs. 后端》P3

&#x1f4cc; 这篇文章讲了什么&#xff1f; 介绍了 前端&#xff08;客户端&#xff09; 和 后端&#xff08;服务器端&#xff09; 的区别。解释了 全栈开发&#xff08;Full Stack Development&#xff09;&#xff0c;即前端后端开发。介绍了 前端和后端常用的技术。讨论…

SpringBoot集成ElasticSearch实现支持错别字检索和关键字高亮的模糊查询

文章目录 一、背景二、环境准备1.es8集群2.Kibana3.Canal 三、集成到SpringBoot1.新增依赖2.es配置类3.建立索引4.修改查询方法 四、修改前端 一、背景 我们在开发项目的搜索引擎的时候&#xff0c;如果当数据量庞大、同时又需要支持全文检索模糊查询&#xff0c;甚至你想做到…

麒麟系统使用-安装 SQL Developer

文章目录 前言一、基础准备1.基本环境2.相关包下载 二、进行相关配置1.配置JAVA2.配置SQL Developer 总结 前言 作为我国自主研发的操作系统&#xff0c;麒麟系统在使用时需要考虑安装相应的app。尽管麒麟系统是基于linux开发&#xff0c;可由于版本的一些差异&#xff0c;麒麟…

PrimeTime:timing_report_unconstrained_paths变量

相关阅读 PrimeTimehttps://blog.csdn.net/weixin_45791458/category_12900271.html?spm1001.2014.3001.5482 PrimeTime自Q-2019.12版本起引入了timing_report_unconstrained_paths变量&#xff08;默认值为false&#xff09;&#xff0c;该变量控制是否在使用report_timing命…

洛谷 P1115 最大子段和(前缀和详解)c++

题目链接&#xff1a;P1115 最大子段和 - 洛谷 1.题目分析 2.算法原理 解法&#xff1a;利用前缀和 思考&#xff1a;如何求出以a[i]为结尾的所有子区间中最大的子段和 假设 i 等于5&#xff0c;以 a[ i ] 为结尾的区间一共是五段&#xff08;黑色线条部分&#xff09;&#…

JetBrains(全家桶: IDEA、WebStorm、GoLand、PyCharm) 2024.3+ 2025 版免费体验方案

JetBrains&#xff08;全家桶: IDEA、WebStorm、GoLand、PyCharm&#xff09; 2024.3 2025 版免费体验方案 前言 JetBrains IDE 是许多开发者的主力工具&#xff0c;但从 2024.02 版本起&#xff0c;JetBrains 调整了试用政策&#xff0c;新用户不再享有默认的 30 天免费试用…

【数据分析】数据筛选与访问行列元素3

访问元素 .loc属性可以通过传入index的值访问行数据。 .loc属性允许传入两个参数&#xff0c;分别是index的值和columns的值&#xff0c;参数间用“逗号”隔开&#xff0c;这样便可以访问数据中的元素。 1. 访问单个元素 访问单个元素比较简单&#xff0c;只需要通过它的in…

C++ std::list超详细指南:基础实践(手搓list)

目录 一.核心特性 1.双向循环链表结构 2.头文件&#xff1a;#include 3.时间复杂度 4.内存特性 二.构造函数 三.list iterator的使用 1.学习list iterator之前我们要知道iterator的区分 ​编辑 2.begin()end() 3.rbegin()rend() 四.list关键接口 1.empty() 2. size…

【免费】2004-2017年各地级市进出口总额数据

2004-2017年各地级市进出口总额数据 1、时间&#xff1a;2004-2017年 2、来源&#xff1a;城市年鉴 3、指标&#xff1a;进出口贸易总额 4、范围&#xff1a;286个地级市 5、指标说明&#xff1a;进出口总额是指一个国家在特定时期内&#xff08;通常为一年&#xff09;所…

谈谈 undefined 和 null

*** 补充 null 和 ‘’

【第15届蓝桥杯】软件赛CB组省赛

个人主页&#xff1a;Guiat 归属专栏&#xff1a;算法竞赛真题题解 文章目录 A. 握手问题&#xff08;填空题&#xff09;B. 小球反弹&#xff08;填空题&#xff09;C. 好数D. R格式E. 宝石组合F. 数字接龙G. 爬山H. 拔河 正文 总共8道题。 A. 握手问题&#xff08;填空题&…

【计算机视觉】工业表计读数(2)--表计检测

1. 简介 工业表计&#xff08;如压力表、电表、气表等&#xff09;在工控系统、能源管理等领域具有重要应用。然而&#xff0c;传统人工抄表不仅工作量大、效率低&#xff0c;而且容易产生数据误差。近年来&#xff0c;基于深度学习的目标检测方法在工业检测中展现出极大优势&…

提示词工程(Prompt Engineering)

https://www.bilibili.com/video/BV1PX9iYQEry 一、懂原理&#xff0c;要知道 为什么有的指令有效&#xff0c;有的指令无效为什么同样的指令有时有效&#xff0c;又是无效怎么提升指令有效的概率 大模型应用架构师想什么&#xff1f; 怎样能更准确&#xff1f;答&#xff1…

从Instagram到画廊:社交平台如何改变艺术家的展示方式

从Instagram到画廊&#xff1a;社交平台如何改变艺术家的展示方式 在数字时代&#xff0c;艺术家的展示方式正在经历一场革命。社交平台&#xff0c;尤其是Instagram&#xff0c;已经成为艺术家展示作品、与观众互动和建立品牌的重要渠道。本文将探讨社交平台如何改变艺术家的…