斐波那契数c++复杂度最低算法

斐波那契数列是一个非常经典的数列，其数列中的每个数都是前两个数之和。如下所示：

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

以下是复杂度最低的 C++ 算法：

int fib(int n) {
  if (n == 0 || n == 1) {
    return n;
  }
  int a = 0, b = 1, c;
  for (int i = 2; i <= n; ++i) {
    c = a + b;
    a = b;
    b = c;
  }
  return c;
}

该算法的时间复杂度为 O(n)，因为它只需要遍历一次整个数列。同时，该算法使用了常数级的空间复杂度，因为它只需要存储前两个数的值。

相关问题

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。

斐波那契数列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;
}