4.1 记忆化的定义及其基本概念
记忆化，也叫“Memoization”，是一种优化技术，通过保存昂贵函数的结果，以便在后续使用相同参数调用时可以重用。这减少了重复计算的次数，从而提高了性能。
基本概念:
1. 缓存(Cache)：
将函数结果保存在某种数据结构中（如字典或数组），以便在用相同参数再次调用时返回已保存的结果，而不是重新计算。
2. 查找表(Lookup Table)：
用于存储函数先前调用结果的数据结构。可以是哈希表（字典）或数组。
3. 递归调用：
记忆化对递归函数特别有用，在递归函数中，相同的子任务可能会以相同的参数多次执行。
优化算法的时间和空间复杂度：
时间复杂度：
对于许多递归任务，记忆化通过减少重复计算来降低时间复杂度。例如，递归计算斐波那契数列的时间复杂度是 O(2^n)，使用记忆化后变为 O(n)。
空间复杂度：
由于在缓存中存储结果，空间复杂度会增加。通常是 O(n)，对于需要记忆化的任务。
总结：
记忆化是一种强大的优化递归算法的技术，通过减少重复计算来显著提高性能。
它尤其适用于那些相同子任务多次以相同参数执行的任务。理解记忆化的概念及其实践应用，可以高效解决高计算开销的问题。
4.2 优化示例
使用记忆化优化递归算法的示例
示例 1: 斐波那契数列
递归计算斐波那契数列的算法在没有记忆化的情况下具有指数级的时间复杂度。使用记忆化显著提升性能。
def fibonacci(n, memo=None):
if memo is None:
memo = {}
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
return memo[n]
# 使用示例:
print(fibonacci(10)) # 输出: 55
重要! 注意，我们使用 memo=None 作为默认值，然后在函数内部创建一个空字典，如果没传入 memo。这样可以避免可变对象作为默认值的问题。
示例 2: 子集和问题
需要确定是否存在一个给定集合的子集，其元素之和等于给定值。
def is_subset_sum(arr, n, sum_value, memo=None):
if memo is None:
memo = {}
if (n, sum_value) in memo:
return memo[(n, sum_value)]
if sum_value == 0:
return True
if n == 0 and sum_value != 0:
return False
if arr[n - 1] > sum_value:
memo[(n, sum_value)] = is_subset_sum(arr, n - 1, sum_value, memo)
return memo[(n, sum_value)]
memo[(n, sum_value)] = is_subset_sum(arr, n - 1, sum_value, memo) or is_subset_sum(arr, n - 1, sum_value - arr[n - 1], memo)
return memo[(n, sum_value)]
# 使用示例:
arr = [3, 34, 4, 12, 5, 2]
sum_value = 9
n = len(arr)
print(is_subset_sum(arr, n, sum_value)) # 输出: True
记忆化实际上就是缓存子任务的结果。
例如，斐波那契数 F(10) == F(9) + F(8)，但为了计算 F(9)，需要计算 F(8) 和 F(7)。也就是说，我们必须计算 F(8) 两次：作为 F(9) 的第一个加数和作为 F(10) 的第二个加数。为了避免计算两次，第一次计算后需要缓存它。
GO TO FULL VERSION