记忆化
记忆化
记忆化是一种技术，用于存储结果以避免多次进行相同的计算。
当记忆化用于改进递归算法时，它被称为“自顶向下”方法，因为它从主问题开始并将其分解成更小的子问题。
记忆化用于 动态规划 中。
使用记忆化查找第 \(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))如您从运行上面的示例中看到的那样，有 25 次计算，即使只是为了找到第 6 个斐波那契数，相同的计算也会进行很多次。
但是，使用记忆化可以更有效地帮助使用递归查找第 \(n\) 个斐波那契数。
我们通过创建一个数组 memo 来保存斐波那契数来使用记忆化，因此可以将斐波那契数 n 找到为元素 memo[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 树中，当高度以这种方式存储时，它被称为**增强属性**。
增强属性是元素的一种属性，该属性不必存储，但存储是为了使操作更有效。
当然，节点高度必须在某个时刻被计算出来，但这只在绝对需要的时候使用 回溯 来完成。
