c++怎么求斐波那契数列时间复杂度最小

在C++中，计算斐波那契数列的时间复杂度可以通过动态规划或矩阵快速幂的方法降低。以下是使用矩阵快速幂优化算法的时间复杂度最低的版本：

首先，我们需要定义一个2x2的矩阵乘法函数和将矩阵n次方的递归函数，因为斐波那契数列可以用这种形式表示：

#include <vector>

// 定义矩阵乘法
std::vector<std::vector<int>> matrixMultiply(std::vector<std::vector<int>>& a, std::vector<std::vector<int>>& b) {
    int m = a.size(), n = b[0].size(), p = b.size();
    std::vector<std::vector<int>> res(m, std::vector<int>(p, 0));
    for (int i = 0; i < m; ++i)
        for (int j = 0; j < p; ++j)
            for (int k = 0; k < n; ++k)
                res[i][j] += a[i][k] * b[k][j];
    return res;
}

// 定义矩阵n次方
std::vector<std::vector<int>> matrixPower(std::vector<std::vector<int>>& base, int n) {
    if (n == 1) return base;
    if (n % 2 == 0) return matrixMultiply(matrixPower(base, n / 2), base);
    else return matrixMultiply(base, matrixPower(base, n - 1));
}

// 获取第n项斐波那契数
int fibonacci(int n) {
    if (n <= 0) return 0;
    std::vector<std::vector<int>> fibMatrix = {{1, 1}, {1, 0}};
    return matrixPower(fibMatrix, n - 1)[0][0];
}

这个版本的时间复杂度是O(log n)，因为它利用了矩阵乘法的性质。每次计算都把指数对半分，直到n变为1。