python - 为什么这种(​​可能更有效)动态算法的性能优于朴素递归版本？

Question

我有以下问题作为作业:

Write a O(N^2) algorithm to determine whether the string can be broken into a list of words. You can start by writing an exponential algorithm and then using dynamic programming to improve the runtime complexity.

我开始使用的朴素指数算法是这样的:

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")

在我看来，对于为什么运行时间不一致/不是我期望的只有几个解释:

• 我的动态算法(或我的分析)有问题
• 我的递归算法有问题
• 我的测试用例不足
• timeit 实际上并不是一个适合我想做的事情的库

有人有任何见解或解释吗？

Answer 1

只有当有很多很多方法将同一个字符串分解为单词时，简单的递归方法才会很慢。如果只有一种方式，那么它将是线性的。

假设 can、not 和 cannot 都是列表中的单词，请尝试使用类似 "cannot"* n 的字符串。当您到达 n=40 时，您应该可以清楚地看到胜利。