記憶化
記憶化
記憶化是一種將結果儲存起來以避免重複計算的技術。
當使用記憶化來改進遞迴演算法時，由於其從主問題開始並將其分解為更小子問題的過程，因此稱為“自頂向下”方法。
記憶化用於 動態規劃。
使用記憶化查詢第 \(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 樹中，當高度像這樣儲存時，它被稱為**增強屬性**。
增強屬性是元素的屬性，不一定非要儲存，但為了提高操作效率而儲存。
節點高度當然必須在某個時候計算，但這僅在使用 回溯 時進行，並且僅在絕對需要時才進行。
