记忆化
记忆化
记忆化是一种将结果存储起来以避免重复计算的技术。
当使用记忆化来改进递归算法时，由于其从主问题开始并将其分解为更小子问题的过程，因此称为“自顶向下”方法。
记忆化用于 动态规划。
使用记忆化查找第 \(n\) 个斐波那契数
第 \(n\) 个斐波那契数可以使用递归来查找。阅读 本页面 了解其具体做法。
此实现的弊端在于，当尝试查找更高的斐波那契数时，计算次数和递归调用次数会“爆炸性”增长，因为相同的计算会一遍又一遍地重复。
示例
使用递归查找第 6 个斐波那契数
def F(n):
print('Computing F('+str(n)+')')
if n <= 1:
return n
else:
return F(n - 1) + F(n - 2)
print('F(6) = ',F(6))从上面的示例运行结果可以看出，即使只是查找第 6 个斐波那契数，也有 25 次计算，其中许多计算是重复的。
但是，使用记忆化可以更有效地通过递归查找第 \(n\) 个斐波那契数。
我们通过创建一个数组 memo 来存储斐波那契数，以便可以通过 memo[n] 找到第 \(n\) 个斐波那契数。只有当斐波那契数不存在于 memo 数组中时，我们才会进行计算。
示例
使用递归查找第 6 个斐波那契数，但使用记忆化来避免不必要的递归调用
def F(n):
if memo[n] != None: # Already computed
return memo[n]
else: # Computation needed
print('Computing F('+str(n)+')')
if n <= 1:
memo[n] = n
else:
memo[n] = F(n - 1) + F(n - 2)
return memo[n]
memo = [None]*7
print('F(6) = ',F(6))
print('memo = ',memo)从上面的示例运行结果可以看出，记忆化对于减少计算次数非常有帮助。
计算次数从初始代码的 25 次减少到使用记忆化的最后一个示例中的 7 次，而且随着我们想要查找的斐波那契数的高度增加，使用记忆化的好处也会快速增加。
查找第 30 个斐波那契数在初始代码中需要 2,692,537 次计算，但在使用记忆化实现的算法中，仅需要 31 次计算！
通过运行下面的代码可以得到这个结果。
示例
查看查找第 30 个斐波那契数时，使用记忆化和不使用记忆化的计算次数差异
computation_count = 0
def F(n):
global computation_count
computation_count += 1
if n <= 1:
return n
else:
return F(n - 1) + F(n - 2)
computation_count_mem = 0
def F_mem(n):
if memo[n] != None: # Already computed
return memo[n]
else: # Computation needed
global computation_count_mem
computation_count_mem += 1
if n <= 1:
memo[n] = n
else:
memo[n] = F_mem(n - 1) + F_mem(n - 2)
return memo[n]
print('F(30) = ',F(30))
print(f'Number of computations: {computation_count}')
print('\nUsing memoization:')
memo = [None]*31
print('F(30) = ',F_mem(30))
print(f'Number of computations with memoiztion: {computation_count_mem}')AVL 树中的记忆化
有关 AVL 树的更多详细信息，请参阅 本页面。
AVL 树是一种自平衡二叉树。
每次向 AVL 树插入或删除节点时，都必须计算所有祖先节点的平衡因子，利用左右子树的高度来判断是否需要进行旋转以恢复平衡。
为了避免计算每个节点的树高（一直递归到叶子节点）来计算平衡因子，每个节点都存储了其子树的高度。
示例
class TreeNode:
def __init__(self, data):
self.data = data
self.left = None
self.right = None
self.height = 1这意味着，要查找节点的平衡因子，只需用已存储的右子节点高度减去已存储的左子节点高度即可，无需其他计算。
在 AVL 树中存储节点高度是一种记忆化的形式，因为值被存储起来以避免重新计算。在 AVL 树中，当高度像这样存储时，它被称为**增强属性**。
增强属性是元素的属性，不一定非要存储，但为了提高操作效率而存储。
节点高度当然必须在某个时候计算，但这仅在使用 回溯 时进行，并且仅在绝对需要时才进行。
