面试题：Python递归与优化之记忆化搜索实现斐波那契数列

Question

斐波那契数列定义为：F(0)=0，F(1)=1，F(n)=F(n - 1)+F(n - 2)（n >= 2，n ∈ N*）。请使用Python的递归函数实现斐波那契数列的计算，同时运用记忆化搜索（Memoization）优化该递归函数，以提高计算效率，并且分析优化前后函数的时间复杂度变化。

Answer 1

# 未优化的递归函数
def fibonacci_unoptimized(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci_unoptimized(n - 1) + fibonacci_unoptimized(n - 2)

# 优化后的递归函数（记忆化搜索）
memo = {}
def fibonacci_optimized(n):
    if n in memo:
        return memo[n]
    if n == 0:
        result = 0
    elif n == 1:
        result = 1
    else:
        result = fibonacci_optimized(n - 1) + fibonacci_optimized(n - 2)
    memo[n] = result
    return result

时间复杂度分析

1. 未优化的递归函数：
   • 未优化的斐波那契数列递归函数，每个fibonacci_unoptimized(n)会调用fibonacci_unoptimized(n - 1)和fibonacci_unoptimized(n - 2)，形成一个递归树。
   • 时间复杂度近似于$O(2^n)$，因为递归树的节点数随着n的增加呈指数级增长，每个节点都需要一定的计算时间。
2. 优化后的递归函数（记忆化搜索）：
   • 优化后的函数通过memo字典来存储已经计算过的结果。
   • 每个n最多只计算一次，之后直接从字典中获取结果。所以时间复杂度为$O(n)$，因为最多需要计算n个不同的斐波那契数。