记忆算法时间复杂度

Question

我读了这篇文章,退出了一个很好的面试问题,作者想出了一个work break问题并提出了三个解决方案.高效使用一个memoization算法和笔者表示,其最坏情况下的时间复杂度是O(n^2)因为the key insight is that SegmentString is only called on suffixes of the original input string, and that there are only O(n) suffixes.

但是,我发现很难理解它为什么O(n^2).有人可以给我一个提示或证据吗？

Work Break Problem: 
    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;
}

Answer 1

直觉

(很明显,最糟糕的情况是没有解决方案,所以我专注于那个)

由于在将值放入memoization-cache之前进行了递归调用,因此最后(最短)后缀将首先被缓存.这是因为首先使用长度为N的字符串调用该函数,然后使用长度为N-1的字符串调用自身,然后使用字符串len 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的输入上完成所需的操作数)

归纳假设 - 存在一个常数cst f(N) < c*N^2.

基本情况是微不足道的-用于长度为1的字符串,你可以找到一个常数c,使得f(1) < c*N^2 = c

感应步骤

回顾订单的事情:

步骤1:函数首先在长度为N-1的后缀上调用自身,构建包含最后N-1个后缀的答案的缓存

步骤2:该函数然后多次调用自身O(N),每次取O(1)(由于此测试:if (memoized.containsKey(input)),以及在步骤1中已经填充了缓存的事实).

所以我们得到:

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,完成了证明.