💾 memoization

今日は勉強します.

回帰と分割征服

注記

トラブルシューティングの注意事項

Memoization

分割されたサブ問題を解決するために重複ソリューションを繰り返し使用する
(ダイナミックプログラミングで使用)

の推定値を繰り返し使用するため、プログラムの実行速度は

加速する.

関数の時間的複雑度を低減し、空間的複雑度

を増加させる.

メソッド:重複する計算結果を特定の変数に格納

「get memo」を使用して計算結果

を保存

などの関数については、「呼び出し関数」を使用して

を再使用します.

# 메모이제이션 적용되지 않은 경우

def recursive_factorial(n): # 최상위 호출
    if n is 0:
        return 1
    else:
        return n * recursive_factorial(n - 1) # 함수 내부

のトップレベルのコールにおける完全なメモリ計算

recursive factorial(3)の呼び出し順序
1.factorial(3)呼び出し

factorial(3)factorial(2)呼び出し

を実行する.

注釈この注釈を利用しない場合、factorial(3)とfactorial(2)の2つの関数はfactorial(2)論理を計算する
(パラメータ数が増加するにつれて、同じ論理の計算数も増加する)

memo = {} # 계산 결과 저장할 딕셔너리

def factorial(n):
	if n == 0:
    	return 1
    elif n in memo: # 재귀 함수 계산하면서 저장됐다면
    	return memo[n]
    else:
    	result = n * factorial(n-1)
        memo[n] = result # 메모장에 계산한 n, 계산 결과 저장
        return result

このようにfactorial(5)とfactorial(4)の場合、4の値は24でmemoに保存されるので、2番目のfactorial関数呼び出しでは論理計算を必要とせずに結果を出力することができる.