#include<iostream>//f(n)=f(n-1)+f(n-2)递归-时间取代空间，慢 #include<bits/stdc++.h>using namespace std;int birth(int n){ if(n==1) return 1; if(n==2) return 1; else return birth(n-1)+birth(n-2);}int main(){ int n; cin >> n; cout << birth(n); return 0;

### 优化递归函数以降低时间复杂度 #### 动态规划方法动态规划是一种有效的优化技术，可以显著减少重复计算。通过自底向上的方式构建解决方案并保存中间结果，从而避免了指数级的时间复杂度。这种方法的时间复杂度为 \(O(n)\)，空间复杂度也为 \(O(n)\)[^1]。以下是基于动态规划的 C++ 实现： ```cpp #include <iostream> using namespace std; // 使用动态规划计算斐波那契数列 unsigned long long fibonacciDP(int n) { if (n <= 1) return n; unsigned long long fib[n + 1]; fib[0] = 0; fib[1] = 1; for (int i = 2; i <= n; ++i) { fib[i] = fib[i - 1] + fib[i - 2]; // 存储每一步的结果 } return fib[n]; } int main() { int n; cout << "Enter a number: "; cin >> n; cout << "Fibonacci(" << n << ") = " << fibonacciDP(n) << endl; return 0; } ``` #### 尾递归优化尾递归是指递归调用作为整个函数体中的最后一个操作执行的技术。编译器能够将其转换为迭代形式，从而避免堆栈溢出问题，并将时间复杂度保持在 \(O(n)\)[^1]。下面是尾递归版本的实现： ```cpp #include <iostream> using namespace std; // 尾递归实现斐波那契数列 unsigned long long tailRecursiveFib(int n, unsigned long long prev = 0, unsigned long long curr = 1) { if (n == 0) return prev; if (n == 1) return curr; return tailRecursiveFib(n - 1, curr, prev + curr); } int main() { int n; cout << "Enter a number: "; cin >> n; cout << "Fibonacci(" << n << ") = " << tailRecursiveFib(n) << endl; return 0; } ``` #### 迭代方法除了上述两种方法外，还可以采用简单的迭代算法来进一步节省内存开销。此方法仅需两个变量即可完成计算，因此其空间复杂度降为 \(O(1)\)，而时间复杂度仍为 \(O(n)\)[^4]。下面是一个典型的迭代实现： ```cpp #include <iostream> using namespace std; // 迭代实现斐波那契数列 unsigned long long fibonacciIterative(int n) { if (n <= 1) return n; unsigned long long prev = 0, curr = 1; for (int i = 2; i <= n; ++i) { unsigned long long next = prev + curr; prev = curr; curr = next; } return curr; } int main() { int n; cout << "Enter a number: "; cin >> n; cout << "Fibonacci(" << n << ") = " << fibonacciIterative(n) << endl; return 0; } ``` 以上三种方法均能有效解决传统递归带来的性能瓶颈问题。具体选择取决于实际需求以及对时间和空间效率的要求。

阅读全文

#include<iostream>//f(n)=f(n-1)+f(n-2)递归-时间取代空间，慢 #include<bits/stdc++.h>using namespace std;int birth(int n){ if(n==1) return 1; if(n==2) return 1; else return birth(n-1)+birth(n-2);}int main(){ int n; cin >> n; cout << birth(n); return 0;

相关推荐

vc++2008编译不了#include头文件

c++万能头文件(包含所有其他头文件)#include<bits/stdc++.h> 注：此cpp文件包含万能头文件以及基本框架

#include <iostream>

中小学校网络视频监控解决方案.doc

分治算法实验报告.docx

基于BACF算法的实时目标跟踪技术

这篇文章主要探讨了基于李雅普诺夫方法的深度强化学习在保证性能方面的应用 以下是文章的主要内容和结构：

[课程设计]基于plc的变频器液位控制设计.doc

操作系统试题及答案.doc

综合布线设计说明书.doc

软件工程试题与答案.doc

朝阳县鑫顺达铁选厂环保管理机构网络图.doc

应用软件管理规范.doc

网络商城策划书.doc

计算机二级C语言笔试试卷.doc

【Python编程】JSON数据处理：Python内置与第三方库实现JSON编码解码功能详解

python4delphi-master (2).zip

这篇文章主要探讨了可解释性人工智能（Explainable AI, XAI）领域的最新进展，特别是深度学习模型的解释、解释和可视化 以下是文章的主要内容总结：

自然辩证法在人工智能学科的科研选题中的指导意义.doc

大家在看

西安市行政区划（区县）

ansys后处理的教程

基于matlab的第三代SNN脉冲神经网络的仿真,含仿真操作录像

新工创项目-基于树莓派5+ROS2的智能物流小车视觉系统（源码+使用教程+模型文件）.zip

PyPDF2-1.26.0.tar.gz

最新推荐

中小学校网络视频监控解决方案.doc

cc65 Windows完整版发布：6502 C开发工具

【CLIP模型实战】：从数据预处理到代码实现的图文相似度计算完全指南

车载以太网doip协议格式

JavaScript中文帮助手册：初学者实用指南

深入理解MySQL存储引擎：InnoDB与MyISAM的终极对决

window中系统中断，cpu占用100%

C++Builder6.0缺失帮助文件的解决方案

【湖北专升本MySQL强化训练】：5大SQL语句编写技巧，迅速提升实战能力

HFSS如何设置网格化细化

这篇文章主要探讨了基于李雅普诺夫方法的深度强化学习在保证性能方面的应用以下是文章的主要内容和结构：

这篇文章主要探讨了可解释性人工智能（Explainable AI, XAI）领域的最新进展，特别是深度学习模型的解释、解释和可视化以下是文章的主要内容总结：