4.1 記憶化的定義及其主要概念
記憶化 是一種優化技術，藉此將耗費資源的函數結果保存下來，以便在之後用相同參數調用時重複使用。這樣可以減少重複計算的次數，從而提高效能。
主要概念：
1. 快取（Caching）:
將函數結果保存在某種資料結構中（例如字典或陣列），以便在使用相同參數重複調用時返回已保存的結果，而不是重新計算。
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