首页婓波那契数列怎么降低时间复杂度

婓波那契数列怎么降低时间复杂度

时间: 2025-05-21 07:32:52 浏览: 17

### 动态规划与记忆化递归优化斐波那契数列 #### 记忆化递归为了减少重复计算，可以通过引入缓存机制存储已经计算过的子问题的结果。这种方法称为记忆化递归。它能够显著降低时间复杂度至 $O(n)$[^1]。以下是基于 C++ 的记忆化递归实现： ```cpp #include <iostream> #include <vector> using namespace std; int fibonacci(int n, vector<int>& memo) { if (n <= 2) return 1; if (memo[n] != -1) return memo[n]; // 使用已有的结果 memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo); return memo[n]; } int main() { int n; cin >> n; vector<int> memo(n + 1, -1); // 初始化备忘录数组 cout << fibonacci(n, memo) << endl; return 0; } ``` 此代码利用了一个 `vector` 数组保存中间状态，从而避免了指数级增长的递归调用[^3]。 #### 动态规划动态规划是一种自底向上的方法，通过构建一张表记录所有可能的状态转移关系来解决问题。对于斐波那契序列而言，仅需维护两个连续项即可完成整个序列的生成，这使得空间复杂度降为 $O(1)$，而时间复杂度仍保持线性级别 $O(n)$[^4]。下面是 Python 中的一个简单例子展示如何应用 DP 来解决该问题: ```python def fibonacci_dp(n): if n <= 0: return 0 elif n == 1 or n == 2: return 1 prev, curr = 1, 1 for _ in range(3, n + 1): next_val = prev + curr prev = curr curr = next_val return curr print(fibonacci_dp(10)) # 输出第10个斐波那契数 ``` 这种迭代版本不仅提高了效率还减少了函数调用带来的开销[^5]。 ---

阅读全文