请根据 n 的整数输入（例如 O(n)、O(n^2)、O(exp(n))、O(nlogn 等）分析以下 Python 函数的时间复杂度。 如何在保持迭代形式（即无循环）的同时对其进行改进？ 你改进代码的时间复杂度是多少？ (5+10+5 = 20 分) # 计算斐波那契数列的Python代码，fib(0)=1, fib(1)=1, fib(2)=2, fib(3)=3, fib(4)=5, fib(5)=8, fib(6)=13, … def fib(n): 如果 n < 2 则返回 1 否则 fib(n-1)+fib(n-2)

该函数的时间复杂度为 O(2^n)。

在保持迭代形式的情况下，可以使用动态规划来改进代码。具体来说，可以使用一个数组来记录之前计算过的斐波那契数列的值，避免重复计算。改进后的代码如下：

def fib(n):
    if n < 2:
        return 1
    else:
        dp = [0] * (n+1)
        dp[0] = dp[1] = 1
        for i in range(2, n+1):
            dp[i] = dp[i-1] + dp[i-2]
        return dp[n]

改进后的时间复杂度为 O(n)。