为什么这个（可能更有效）动态算法被朴素的递归版本胜过？

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 库来分析这两种算法对运行一批测试所花费的时间，结果令人惊讶。动态方法仅比递归方法快几分之一秒。更令人困惑的是，在运行多次执行相同的测试后，递归方法实际上比动态方法给出了更好的运行时间。这是我用来测试运行time:

的代码

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

在我看来，对于为什么运行时间是 inconsistent/not 我所期望的只有几个解释：

我的动态算法（或我对它的分析）有问题
我的递归算法有问题
我的测试用例不足
timeit 实际上不是我想要做的合适的库

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

Answer 1

只有当有很多很多方法可以将同一个字符串分解成单词时，朴素的递归方法才会变慢。如果只有一种方式，那就是线性的。

假设 can、not 和 cannot 都是您列表中的单词，请尝试 "cannot" * n 这样的字符串。当你到达 n=40 时，你应该会很清楚地看到胜利。

为什么这个（可能更有效）动态算法被朴素的递归版本胜过？

Why is this (presumably more efficient) dynamic algorithm being outperformed by the naive recursive version?

python

algorithm

recursion

big-o

dynamic-programming