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

斐波那契数列是一个经典的动态规划问题，通常使用迭代法（也称为 memoization 或 bottom-up approach）可以达到最低的时间复杂度。最简单的迭代算法将时间复杂度降低到 O(n)，其中 n 是需要计算的斐波那契数的位置。

以下是迭代法的伪代码：

def fibonacci(n):
    if n <= 0:
        return "Invalid input"
    elif n == 1 or n == 2:
        return 1
    else:
        fib_cache = [0] * (n+1)
        fib_cache[1] = 1
        fib_cache[2] = 1
        for i in range(3, n+1):
            fib_cache[i] = fib_cache[i-2]
        return fib_cache[n]

这个方法通过预先计算并存储已经计算过的斐波那契数值，避免了重复计算，对于大的 n，它比递归版本（时间复杂度为 O(2^n)）效率更高。