python - 这两个代码的时间复杂度是多少

Question

以下是斐波那契数列的两种不同的动态规划代码。我无法弄清楚这些的时间复杂度。两者的结果是一样的。任何帮助表示赞赏。

#Code 1
def fibo(n) :
    if mem[n] is not None:
        return mem[n]

    if n == 1 or n == 2 :
        res = 1
    else :
        res = fibo(n - 1) + fibo(n - 2)

    mem[n] = res
    return res

n = int(input("Enter position :"))
mem = [None] * (n + 1)
fibo(n)

代码 2

def fibo(n) :
    if len(mem) == n-1 :
        return mem[n-1]

    if n == 1 or n == 2 :
        res = 1
    else :
        res = fibo(n - 1) + fibo(n - 2)

    mem.append(res)
    return res

n = int(input("Enter position :"))
mem = []
fibo(n)

标签： pythonbig-odynamic-programmingfibonacci