斐波那契数列c+++的时间复杂度

斐波那契数列是一个经典的递归问题，在C++中，如果使用简单的递归算法来计算斐波那契数列，时间复杂度会是O(2^n)，因为每个数字都需要计算两次其前两个数字。

然而，这样的实现效率非常低。为了提高效率，我们可以采用动态规划，将已经计算过的值存储在一个数组中，避免重复计算。这种记忆化搜索的方法将其时间复杂度降低到O(n)。另外，还可以使用矩阵快速幂等数学技巧进一步优化为O(log n)，但这对于新手来说可能会稍微复杂一些。

如果你直接询问如何在C++中高效地计算斐波那契数列，下面是一种常见且高效的迭代版本：

#include <iostream>
using namespace std;

int fibonacci(int n) {
    if (n <= 0) return 0;
    if (n == 1 || n == 2) return 1;

    int 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 of " << n << " is: " << fibonacci(n);
    return 0;
}