网站首页 > 技术文章 正文
由于递归存在重复计算,如果递归深度很大,会引起性能问题。
本文以斐波那契数列为例,介绍优化递归算法时间复杂度的两种基本思路:使用循环代替递归,缓存计算结果。
斐波那契数列是一个经典的数学序列,定义如下:
- F(0) = 0
- F(1) = 1
- F(n) = F(n-1) + F(n-2) (n>=2时)
斐波那契数列的前几项是:0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
递归实现
Bash
def fibonacci_recursive(n: int) -> int:
if n <= 1:
return n
return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)
循环实现
通过循环可以避免重复计算。
递归算法理论上都可以转换为循环,但不是所有递归算法都容易转换为循环。尾递归(递归调用是函数体中的最后一个操作)的转换相对简单,可以直接用循环替换;而非尾递归和复杂递归的转换则可能需要显式使用栈等数据结构来管理状态。
Bash
def fibonacci_iterative(n: int) -> int:
if n <= 1:
return n
pre, cur = 0, 1
for _ in range(2, n + 1):
# 先计算=右边的结果,并赋值给临时变量,再将临时变量赋值给=左边的变量
pre, cur = cur, pre + cur
return cur
手动缓存计算结果
手动缓存通过一个字典或列表存储已经计算过的斐波那契数,避免重复计算。
def fibonacci_cache(n: int, cache={}) -> int:
if n in cache:
return cache[n]
if n <= 1:
result = n
else:
result = fibonacci_cache(n - 1, cache) + fibonacci_cache(n - 2, cache)
cache[n] = result
return result
自动缓存计算结果
使用Python提供的functools.lru_cache 装饰器,可以自动缓计算结果。
@lru_cache(maxsize=None) # maxsize=None 表示不限制缓存大小
def fibonacci_lru_cache(n: int) -> int:
if n <= 1:
return n
return fibonacci_lru_cache(n - 1) + fibonacci_lru_cache(n - 2)
耗时统计
def measure_time_with_log(func, *args, **kwargs):
"""
测量函数执行时间并打印日志的通用函数。
:param func: 要测量的函数
:param args: 函数的位置参数
:param kwargs: 函数的关键字参数
:return: 函数的返回值
"""
start_time = time.perf_counter()
result = func(*args, **kwargs)
end_time = time.perf_counter()
elapsed_time = end_time - start_time
print("'{}' takes {:.2f} milliseconds".format(func.__name__, elapsed_time * 1000))
return result
if __name__ == '__main__':
measure_time_with_log(fibonacci_recursive, 32)
measure_time_with_log(fibonacci_iterative, 32)
measure_time_with_log(fibonacci_cache, 32)
measure_time_with_log(fibonacci_lru_cache, 32)
输出结果示例如下:
'fibonacci_recursive' takes 406.02 milliseconds
'fibonacci_iterative' takes 0.01 milliseconds
'fibonacci_cache' takes 0.02 milliseconds
'fibonacci_lru_cache' takes 0.01 milliseconds
猜你喜欢
- 2025-04-26 Python机器学习库Sklearn系列教程(21)-参数优化
- 2025-04-26 DeepSeek高赞回答:35岁被优化搞python,月入过万,看完后绝了
- 2025-04-26 Python 列表:从入门到高阶,避坑 + 性能优化全攻略
- 2025-04-26 Python跨平台GUI开发终极指南:3大框架×5项优化×教育行业实战案例
- 2025-04-26 通过优化代码来提高 Python 程序执行速度
- 2025-04-26 超参数黑盒(Black-box)优化的Python代码示例
- 2025-04-26 Python人工智能tensorflow优化器Optimizer算法汇总
- 2025-04-26 Python贝叶斯优化器Bayes_opt优化深度森林Deep Forest分类模型
- 2025-04-26 300分钟Python入门第26天 - 小明的天气预测优化
- 2025-04-26 Deepseek还真不错帮着优化了Python代码
- 274℃Python短文,Python中的嵌套条件语句(六)
- 272℃python笔记:for循环嵌套。end=""的作用,图形打印
- 270℃PythonNet:实现Python与.Net代码相互调用!
- 265℃Python实现字符串小写转大写并写入文件
- 264℃Python操作Sqlserver数据库(多库同时异步执行:增删改查)
- 124℃原来2025是完美的平方年,一起探索六种平方的算吧
- 105℃Python 和 JavaScript 终于联姻了!PythonMonkey 要火?
- 102℃Ollama v0.4.5-v0.4.7 更新集合:Ollama Python 库改进、新模型支持
- 最近发表
-
- Python错误:IndentationError (缩进错误)
- 字符串对齐的常用方法(对字符串的常用处理方法)
- Python轻松实现markdown转网页,完美支持mermaid图表、latex公式
- Python循环语句(python循环语句分为哪两种)
- 编程小白学做题:Python 的经典编程题及详解,附代码和注释(六)
- Python入门到脱坑经典案—数字金字塔
- Python输出语句print()(python语句print(type(1j))的输出结果)
- Python入门到脱坑经典案例—九九乘法表
- Python格式化:让数据输出更优雅(Python格式化输出代码)
- 一节课的时间快速掌握Python基础知识
- 标签列表
-
- python中类 (31)
- python 迭代 (34)
- python 小写 (35)
- python怎么输出 (33)
- python 日志 (35)
- python语音 (31)
- python 工程师 (34)
- python3 安装 (31)
- python音乐 (31)
- 安卓 python (32)
- python 小游戏 (32)
- python 安卓 (31)
- python聚类 (34)
- python向量 (31)
- python大全 (31)
- python次方 (33)
- python桌面 (32)
- python总结 (34)
- python浏览器 (32)
- python 请求 (32)
- python 前端 (32)
- python验证码 (33)
- python 题目 (32)
- python 文件写 (33)
- python中的用法 (32)