斐波那契数列在C++中可通过递归、迭代、动态规划和矩阵快速幂实现；2. 递归简洁但低效，时间复杂度O(2^n)；3. 迭代法时间复杂度O(n)，空间复杂度O(1)，推荐日常使用；4. 动态规划通过记忆化优化递归，时间复杂度O(n)，需额外空间；5. 矩阵快速幂适用于大数值，时间复杂度O(log n)，适合高性能场景。
计算斐波那契数列在C++中有多种实现方式，每种方法在效率和可读性上各有特点。斐波那契数列定义为：第0项是0，第1项是1，从第2项开始，每一项都等于前两项之和（即 F(n) = F(n-1) + F(n-2)）。下面介绍几种常见的C++实现方法。
递归实现（简单但低效）
最直观的方法是使用递归：
#includeusing namespace std; int fib(int n) { if (n <= 1) return n; return fib(n - 1) + fib(n - 2); }
int main() { int n = 10; cout << "F(" << n << ") = " << fib(n) << endl; return 0; }
这种方法代码简洁，但存在大量重复计算，时间复杂度为O(2^n)，当n较大时性能急剧下降，不推荐用于实际应用。
迭代实现（推荐）
使用循环避免重复计算，效率更高：
立即学习“C++免费学习笔记（深入）”；
#includeusing namespace std; int fib(int n) { if (n <= 1) return n;
int a = 0, b = 1, c; for (int i = 2; i zuojiankuohaophpcn= n; ++i) { c = a + b; a = b; b = c; } return b;}
int main() { int n = 10; cout
该方法时间复杂度为O(n)，空间复杂度为O(1)，适合大多数场景，是实际开发中的首选方案。
动态规划（记忆化递归）
如果仍想使用递归结构，可通过记忆化优化性能：
#include#include using namespace std; int fib_helper(int n, vector
& memo) { if (n <= 1) return n; if (memo[n] != -1) return memo[n]; memo[n] = fib_helper(n - 1, memo) + fib_helper(n - 2, memo); return memo[n]; } int fib(int n) { vector
memo(n + 1, -1); return fib_helper(n, memo); } int main() { int n = 10; cout << "F(" << n << ") = " << fib(n) << endl; return 0; }
通过保存已计算的结果，避免重复调用，时间复杂度降为O(n)，但需要额外的内存空间。
矩阵快速幂（高效处理大数值）
对于非常大的n（如n > 1e9），可以使用矩阵快速幂将时间复杂度降至O(log n)。核心思想是利用以下矩阵关系：
[ F(n+1), F(n) ] = [ F(n), F(n-1) ] × [[1,1],[1,0]]
通过快速幂算法计算矩阵的n次方，即可得到结果。虽然实现稍复杂，但在竞赛或高性能需求中很有用。
基本上就这些常见方法。日常使用推荐迭代法，平衡了效率与代码清晰度。根据具体需求选择合适的方式即可。
