备忘录算法的时间复杂度

Question

我读了这篇文章退休一个伟大的面试问题, 作者提出了一个"单词断点"问题并给出了三个解决方案。其中高效的一个使用了记忆化算法，作者说它的最坏时间复杂度是O(n^2)，因为"关键的见解在于SegmentString仅在原始输入字符串的后缀上调用，并且只有O(n)个后缀"。

然而，我发现很难理解为什么它是O(n^2)。请问有人能给我一个提示或证明吗？

单词断点问题:

    Given an input string and a dictionary of words,
    segment the input string into a space-separated
    sequence of dictionary words if possible. For
    example, if the input string is "applepie" and
    dictionary contains a standard set of English words,
    then we would return the string "apple pie" as output.

来自淘汰一个伟大的面试问题的记忆化算法

Map<String, String> memoized;

String SegmentString(String input, Set<String> dict) {
      if (dict.contains(input)) 
          return input;
      if (memoized.containsKey(input) {
          return memoized.get(input);
      }
      int len = input.length();
      for (int i = 1; i < len; i++) {
          String prefix = input.substring(0, i);
          if (dict.contains(prefix)) {
              String suffix = input.substring(i, len);
              String segSuffix = SegmentString(suffix, dict);
              if (segSuffix != null) {
                  return prefix + " " + segSuffix;
              }
          }
      }
      memoized.put(input, null);
      return null;
}

- mitchelllc

---

解决方案并不是最优的，它只在字符串输入的结果为空时更新记忆化映射表，应该在所有情况下都进行更新！ - Pham Trung

没错。请注意，只有当前缀“prefix”在“dict”中的单词中时，“segSuffix”才会被递归调用。如果递归调用返回非“null”，则调用者立即返回，并向上堆栈返回。换句话说，一旦“segSuffix”调用返回一个非“null”的值，该算法再也不会调用“segSuffix”，因此无需将非“null”值进行记忆化处理。 - Alp

@Alp 很好，谢谢。在这种情况下，我想只需要一个布尔数组就足够了，因为我们总是可以用后缀作为整个输入字符串中的索引来引用它。 - Pham Trung

你们能帮我解释一下为什么它是“O(n^2)”吗？ - mitchelllc

Answer 1

直觉

很明显，最坏情况是没有解，所以我把重点放在了那里。由于递归调用是在将值放入记忆化缓存之前进行的，因此最后（最短的）后缀将首先被缓存。这是因为函数首先被调用时会传入一个长度为N的字符串，然后调用自己传入一个长度为N-1的字符串，然后...传入一个长度为0的字符串，该字符串已被缓存并返回，接着缓存长度为1的字符串并返回，...最终缓存并返回长度为N的字符串。

正如提示所示，只有后缀被缓存，而且只有N个后缀。这意味着在顶层函数获得其第一个递归调用的结果时（即在长度为N-1的后缀上），缓存已经填满了N-1个后缀。

现在，假设N-1个后缀已经被缓存，则for循环需要进行N-1次递归调用，每次调用需要O(1)（因为答案已经被缓存），总共需要O(N)。但是，（预）构建最后N-1个后缀的缓存需要O(N^2)（下面会解释），所以总时间复杂度为O(N)+O(N^2)=O(N^2)。

---

数学归纳法证明

这种解释可以很容易地转化为使用归纳法的正式证明。以下是主要内容：

（f(N)是函数在长度为N的输入上完成所需的操作次数）

归纳假设——存在常数c使得f(N) < c*N^2。

基本情况很显然——对于长度为1的字符串，您可以找到一个常数c，使得f(1) < c*N^2 = c。

归纳步骤

重述发生的顺序：

第一步：函数首先在长度为N-1的后缀上调用自身，构建包含最后N-1个后缀答案的缓存。

第二步：函数接下来再调用O(N)次自身，每次需要O(1)的时间（因为有这个测试：if (memoized.containsKey(input))，并且缓存已经在第一步中被填充了）。

所以我们得到：

f(N+1) = f(N) + a*N <   (by the hypothesis)
       < c*N^2 + a*N <  (for c large enough)
       < c*N^2 + 2*c*N + c =
       = c*(N+1)^2

因此，我们得到了 f(N+1) < c*(N+1)^2，这证明完成。

- shx2

Answer 2

一般而言，记忆化表的维度决定了复杂度。

对于只有一维的记忆化表（memoized[n]）-> 复杂度为O(n)， 对于只有两个维度的记忆化表（memoized[n][n]）-> 复杂度为O(n^2)等等。

原因： 在记忆化的情况下，最坏情况的复杂度是输入运行时间，其中没有一个案例（重叠子问题）被缓存（预先计算）。

现在，假设记忆化表有两个维度（memoization[n][n]）。最坏情况复杂度只能是记忆化表的维度最大值。因此，它的最坏情况只能达到O(n^2)。

因此，记忆化表的维度基本上决定了最坏情况的时间复杂度。

@shx2的答案从数学上解释了这一点。

- Aravind Prasad S

Answer 3

首先，对于给定长度为N的字符串，我们可以将其分成N*(N-1)/2个段，并检查每个段是否包含在字典中。这个成本是O(N^2)。

回到你的代码，从字符串N开始，我们将其拆分成两个较小的字符串，长度为'a'和'N - a'。对于每个子字符串（或前缀），从0到'a'结束，我们只检查一次！

对于每个长度为N - a的片段，它还会检查其每个前缀一次，并将其存储到记忆表中，因此，这一步将确保下一次当我们进行相同的移动时，在这个确切的位置拆分字符串，我们只需要返回结果，而不需要进一步的工作（假设映射将在O(1)时间内检索并返回特定字符串的结果）。这个存储和检索步骤也确保了征服和划分只做一次。

因此，在第一和第二点之后，我们得出结论，只有N*(N - 1)/2个段需要检查一次，这导致成本为O(N^2)。

注意：只有在假设 cost of both dict.contains(input) 和 memoized.containsKey(input) 都是 O(1) 的情况下，复杂度才为 O(N^2)。

- Pham Trung

---

你能解释一下为什么我们可以将其分成N*(N-1)/2个段吗？我认为应该是2^N，因为对于输入字符串中的每个字母，它可能包含在段中，也可能不包含。 - mitchelllc

@mitchelllc 要制作一个片段，我们需要一个起点和一个终点，所以在索引i处，从它开始的片段的终点是i+1，i+2，... 所以，索引0可以有n个片段，索引1有n-1个片段...而从n到1的总和公式是n*(n-1)/2。 - Pham Trung

好的，我仍然感到困惑。正如文章中的作者所解释的那样，“这将分析减少到确定可能分割数量的程度。我把它留给读者作为练习（带着这个提示），以确定这个数字是O(2^n)。”（请参见http://thenoisychannel.com/2011/08/08/retiring-a-great-interview-problem/中的“通用解决方案”部分） - mitchelllc

因为地图已经存储了所有可能性，帮助你避免重复任何步骤，而总共有O(N^2)种情况，每种情况只计算一次，所以我们得出结论。数学在这里不起作用，因为递归公式是不够的，在某些情况下，它考虑了一些先前的步骤（例如在索引1、4、5处拆分字符串，返回，然后再在索引2、4、5处拆分。两个后续拆分被重新计算），从而使公式的结果比实际高。尝试删除地图，您可以看到索引如何遍历。 - Pham Trung

@mitchelllc 在重新阅读shx2的答案后，我认为他的答案是正确的 :) 关键点是要专注于函数的第一步。 - Pham Trung

Answer 4

如果输入的长度为N，则其中包含的最大字典单词数将是N。因此，您需要检查所有不同长度1..N的组合。这是N（N-1）/ 2。

以输入字符串aaaaa为例。

有N个x'a'字符串

N-1个'aa'字符串

等等

- Pita

---

谢谢您的快速回复！您能解释一下为什么字典中包含的最大单词数量是N吗？ - mitchelllc

@mitchellc：因为每个单词至少有一个字母。 - Niklas B.