时间戳

首页 > 解决方案 > 这种将字符串划分为单词的算法的运行时复杂度是多少？

python - 这种将字符串划分为单词的算法的运行时复杂度是多少？

问题描述

我得到一个输入字符串 s ("bedbathandbeyond") 和一组单词 {"bed", "bath", "beyond", "bat", "hand", "and"}。我需要将输入字符串 s 分成字典中的一系列单词。在这种情况下，两个允许的输出将是 ["bed", "bath", "and", "beyond"] 和 ["bed", "bat", "hand", "beyond"]。两个输出都是允许的，没有一个比另一个更好。我的解决方案如下：

def find_breakdown_rec(s, dictionary, memo = {}):
    if len(s) == 0:
        return True, []

    if (s in memo):
        return memo[s]
    for i in range(len(s) + 1):
        word = s[:i]
        if word in dictionary:
            status, words = find_breakdown_rec(s[i:], dictionary, memo)
            if status:
                    memo[s] =  [word] + words
                    return True, memo[s]

    return False, []

如果不使用 memoization，运行时间显然是指数级的：我们有 O(n) 分支因子，并且 O(n) 作为深度：O(n ** n)。然而，对于记忆化，算法在我看来是多项式的：“find_breakdown_rec”可以用 n 个不同的输入调用，然后它对其执行多项式的工作。一位知识渊博的人告诉我，它仍然是指数级的。有人可以解释为什么吗？我一直在努力思考，我不确定为什么会这样。

标签： pythonalgorithmtime-complexitydynamic-programmingmemoization

解决方案

这可以通过计算索赔来证明。让我们检查一下 memoization 实现有多少选项：

如果我们取k单词的数量，并且w_i是第 i 个单词的长度（从左边算起），那么我们知道：

w_1+w_2+..+w_k = n和n输入的长度一样。由于我们只取了长度为正的有效单词，我们也知道w_i>=1

因此，它的等效表示是：

w_1+w_2+..+w_k = n-k在哪里w_i >= 0

通过计算索赔，这等于S(k,n-k) = (n-1)Choose(k-1)

现在，我们可以选择1<=k<=n字符串分区的总数由上述声明确定并且等于

sum_{k=1 to n} of (n-1)Choose(k-1) = sum{k=0 to n-1} of (n-1)Choose(k)

这确实是指数级的，2^(n-1) = O(2^n)

推荐阅读