我有以下問題作為家庭作業：
撰寫一個 O(N^2) 演算法來確定字串是否可以分解為單詞串列。您可以從撰寫指數演算法開始，然后使用動態編程來提高運行時復雜性。
我開始使用的樸素指數演算法是這樣的：
def naiveWordBreak(S):
if len(S) == 0:
return True
else:
return any([(S[:i] in wordSet) and naiveWordBreak(S[i:]) for i in range(1, len(S) 1)])
然后我將其改編為以下動態演算法：
def wordBreak(S):
prefixTable = [False] * (len(S) 1)
prefixTable[0] = True
return _helper(S, prefixTable)
def _helper(S, prefixTable):
if prefixTable[len(S)]:
return prefixTable[len(S)]
else:
for i in range(1, len(S) 1):
if S[:i] in wordSet and _helper(S[i:], prefixTable):
prefixTable[i] = True
return True
從我的證明和一些測驗中我相當有信心這兩種演算法都是正確的，但是遞回方法應該是指數時間，而動態方法應該是 O(n^2)。但是，我很好奇并使用該timeit庫來分析兩種演算法運行一批測驗所需的時間，結果令人驚訝。動態方法只比遞回方法快幾分之一秒。更令人困惑的是，在多次運行相同的測驗之后，遞回方法實際上提供了比動態方法更好的運行時間。這是我用于測驗運行時的代碼：
def testRecursive():
naiveWordBreak("alistofwords")
naiveWordBreak("anotherlistofwords")
naiveWordBreak("stableapathydropon")
naiveWordBreak("retouchesreissueshockshopbedrollsunspotassailsinstilledintersectionpipitreappointx")
naiveWordBreak("xretouchesreissueshockshopbedrollsunspotassailsinstilledintersectionpipitreappoint")
naiveWordBreak("realignitingrains")
def testDynamic():
wordBreak("alistofwords")
wordBreak("anotherlistofwords")
wordBreak("stableapathydropon")
wordBreak("retouchesreissueshockshopbedrollsunspotassailsinstilledintersectionpipitreappointx")
wordBreak("xretouchesreissueshockshopbedrollsunspotassailsinstilledintersectionpipitreappoint")
wordBreak("realignitingrains")
def main():
recTime = timeit.timeit(testRecursive, number=1)
dynTime = timeit.timeit(testDynamic, number=1)
print("Performance Results:\n")
print("Time for recursive method = {}\n".format(recTime))
print("Time for dynamic method = {}\n".format(dynTime))
if dynTime < recTime:
print("Dynamic method produces better performance")
else:
print("Recursive method produces better performance")
在我看來，對于為什么運行時不一致/不是我預期的原因只有一些解釋：
- 我的動態演算法（或我的分析）有問題
- There is something wrong with my recursive algorithm
- My test cases are insufficient
timeitisn't actually an appropriate library for what I'm trying to do
Does anyone have any insights or explanations?
uj5u.com熱心網友回復：
只有當有很多很多方法可以將相同的字串分解為單詞時，樸素的遞回方法才會很慢。如果只有一種方式，那么它將是線性的。
假設can,not和cannot都是您串列中的單詞，請嘗試使用類似"cannot" * n. 當您到達 時n=40，您應該清楚地看到勝利。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/440052.html
標籤：python algorithm recursion big-o dynamic-programming
上一篇：Laravel應用程式中有Menu::render()、Assets::render()、Notify::render()嗎？