def lcs(X,Y,i,j):
if (i == 0 or j == 0):
return 0
elif X[i-1] == Y[j-1]:
return 1 lcs(X,Y,i-1,j-1)
else:
return max(lcs(X,Y,i,j-1),lcs(X,Y,i-1,j))
def lcs(X,Y,i,j):
if c[i][j] >= 0:
return c[i][j]
if (i == 0 or j == 0):
c[i][j] = 0
elif X[i-1] == Y[j-1]:
c[i][j] = 1 lcs(X,Y,i-1,j-1)
else:
c[i][j] = max(lcs(X,Y,i,j-1),lcs(X,Y,i-1,j))
return c[i][j]
第二個比第一個作業得更快。但我發現它們的時間復雜度與 O(N2) 相同。
uj5u.com熱心網友回復：
第一個函式的復雜度是指數級的。每個遞回呼叫都會進行 2 個新的遞回呼叫。許多值被多次計算。這是一個經典的“陷阱”，例如在為斐波那契函式撰寫代碼時經常遇到。
第二個函式是第一個函式的“記憶”版本。所有計算的值都存盤在 table 中c，以避免重新計算它們。因此，雙遞回呼叫max(lcs(X,Y,i,j-1),lcs(X,Y,i-1,j))不會破壞遞回呼叫的數量，因為大多數遞回呼叫會立即以“哦，這個值已經計算出來了，它在表中”終止。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qiye/444586.html
上一篇：替換熊貓中的反引號
下一篇：遞回回圈構建物件