单词拆分递归解法的时间复杂度是多少？

Question

从http://www.geeksforgeeks.org/dynamic-programming-set-32-word-break-problem/中提取的代码中，递归解决方案的时间复杂度是多少？

// returns true if string can be segmented into space separated
// words, otherwise returns false
bool wordBreak(string str)
{
    int size = str.size();

    // Base case
    if (size == 0)  return true;

    // Try all prefixes of lengths from 1 to size
    for (int i=1; i<=size; i++)
    {
        // The parameter for dictionaryContains is str.substr(0, i)
        // str.substr(0, i) which is prefix (of input string) of
        // length 'i'. We first check whether current prefix is in
        // dictionary. Then we recursively check for remaining string
        // str.substr(i, size-i) which is suffix of length size-i
        if (dictionaryContains( str.substr(0, i) ) &&
            wordBreak( str.substr(i, size-i) ))
            return true;
    }

    // If we have tried all prefixes and none of them worked
    return false;
}

我认为它是n^2，因为对于n个方法调用，最坏情况下会执行(n-1)次工作(递归地迭代字符串的其余部分?)。还是指数级/ n!？

我很难确定这些递归函数的Big(O)。非常感谢任何帮助！

- snow

Answer 1

答案是指数级，准确地说是O(2^(n-2))。(2的n-2次方)

在每次调用中，你都会使用长度为1,2....n-1(在最坏情况下)的递归函数。为了完成长度为n的工作，你将递归地完成长度为n-1、n-2、..... 1的所有字符串的工作。因此，T(n)是当前调用的时间复杂度，你在内部做T(n-1),T(n-2)....T(1)的工作。

数学上：

  T(n) = T(n-1) + T(n-2) +.....T(1);
  T(1) = T(2) = 1 

如果您真的不知道如何解决这个问题，解决上述递归的更简单方法是只需替换值。

  T(1) = T(2) = 1
  T(3) = T(1) + T(2) = 1+1 =2; // 2^1
  T(4) = T(1)+ T(2) + T(3) = 1+1+2 =4; //2^2
  T(5) = T(1) + T(2) +T(3) +T(4) = 1+1+2+4 =8; //2^3

因此，如果您替换前几个值，就会清楚地看到时间复杂度为2^(n-2)

- Karthik

---

我知道最坏情况下的递归调用是如何编写的，但很难想象实际上会导致最坏情况的字符串。是否对于这个最坏情况执行，每个字符前缀都应该在字典中，例如对于s ='abcd'，a，b，c，ab，ac等，但是最后一个字符d应该不存在，以确保所有最坏情况的调用实际上都发生。 - arjunkhera

如果我们使用一个布尔数组来存储从索引开始的子字符串是否包含在dict中，那会怎样？在这种情况下，除了第一次之外，不需要进行任何操作，我认为时间复杂度将降至n^2，即子字符串的总数。如果正确，请告诉我。 - Yug Singh

我同意你的结论，但有两个要注意的地方。首先，O(2^{n-2}) 和 O(2^n) 是相同的，因为 2^{n-2} = (2^n) / 4，而大O符号会忽略前导系数。其次，你的分析忽略了使用 .substr 计算子字符串和查找字典的成本。这些事实上并不重要，但这并不是显然的。 - templatetypedef

Answer 2

简短版：此函数的最坏运行时间为Θ(2^n)，这很令人惊讶，因为它忽略了每个递归调用所做的二次工作量，只是将字符串分成片段并检查哪些前缀是单词。

长版：假设我们有一个由n个字母a和字母b组成的输入字符串（我们将其缩写为aⁿb），并创建一个包含单词a、aa、aaa、...、aⁿ的字典。

现在，递归会做什么？

首先，注意到没有递归调用会返回true，因为没有办法解释字符串末尾的b。这意味着每个递归调用都将是形如aᵏb的字符串。让我们将处理这样一个字符串所需的时间表示为T(k)。每个这样的调用都将触发k个更小的调用，一个调用对应于aᵏb的每个后缀。

然而，我们还必须考虑运行时间的其他贡献者。特别是，调用string::substr来形成长度为k的子字符串需要O(k)的时间。我们还需要考虑检查前缀是否是单词的成本。这里没有展示如何执行此操作的代码，但假设我们使用trie或哈希表，我们也可以假设检查长度为k的字符串是否为单词的成本也是O(k)。这意味着，在我们进行递归调用的每个点上，我们将做O(n)的工作——检查前缀是否为单词的某些工作量，以及形成对应于后缀的子字符串的某些工作量。

因此，我们得到

T(k) = T(0) + T(1) + T(2) + ... + T(k-1) + O(k^2)

这里，递归的第一部分对应于每个递归调用，递归的第二部分对应于制作每个子字符串的成本。（有n个子字符串，每个子字符串都需要O(n)的时间来处理）。我们的目标是解决这个递归式，为了简单起见，我们假设T(0)=1。

为了做到这一点，我们将使用“扩展和收缩”的技术。让我们把T(k)和T(k+1)的值写在一起：

T(k) = T(0) + T(1) + T(2) + ... + T(k-1) + O(k²)

T(k+1) = T(0) + T(1) + T(2) + ... + T(k-1) + T(k) + O(k²)

将第一个式子从第二个式子中减去，得到：

T(k+1) - T(k) = T(k) + O(k)

即

T(k+1) = 2T(k) + O(k)

我们是如何从两个O(k²)项的差异中得出O(k)的呢？这是因为 (k + 1)² - k² = 2k + 1 = O(k)。

这是一个更容易处理的递归式，因为每个项只依赖于前一个项。为了简化，我们假设O(k)项仅仅是k，得到递归式：

T(k+1) = 2T(k) + k

此递归式的解为T(k) = 2^k+1 - k - 1。为了证明这一点，我们可以使用一个简单的归纳论证。具体来说：

T(0) = 1 = 2 - 1 = 2⁰⁺¹ - 0 - 1

T(k+1) = 2T(k) + k = 2(2^k - k - 1) + k = 2^k+1 - 2k - 2 + k = 2^k+1 - k - 2 = 2^k+1 - (k + 1) - 1

因此，我们得到运行时间为Θ(2ⁿ)，因为我们可以忽略低阶n项。

我很惊讶地发现这一点，因为这意味着每个递归调用所做的二次工作并不影响总运行时间！在进行这种分析之前，我本来会猜测运行时间应该是类似于Θ(n · 2ⁿ)的。:-)

- templatetypedef

---

我认为你的意思是 T(0) = 1 = 2 - 1 = 2^(0+1) - 0 - 1，而不是 T(0) = 1 = 2 - 1 = 2^0 - 0 - 1。 - AnukuL

Answer 3

我认为答案应该是O(2^(n-1))。你可以在这里看到一个证明，以及一个最坏情况的例子：

https://leetcode.com/problems/word-break/discuss/169383/The-Time-Complexity-of-The-Brute-Force-Method-Should-Be-O(2n)-and-Prove-It-Below

- mcfroob

Answer 4

我认为这里复杂性的一个直观方式是，有多少种方法可以在字符串中添加空格或者在单词中断开？

对于一个四个字母的单词： 在索引0-1处断开的方式数 * 在索引1-2处断开的方式数 * 在索引2-3处断开的方式数 = 2 * 2 * 2。

2表示两个选项 => 断开或不断开

O(2^(n-1))是单词拆分的递归复杂度；）

- rresol