algorithm - 递归算法的时间复杂度分析

Question

我想知道以下算法的复杂性，最重要的是，导致推导它的逐步过程。

我怀疑它是 O(length(text)^2*length(pattern)) 但我在求解递归方程时遇到了问题。

在对递归调用进行记忆化(即动态规划)时，复杂度会如何提高？

此外，我希望能得到技术/书籍的指导，这将帮助我学习如何分析此类算法。

在 Python 中:

def count_matches(text, pattern):
  if len(pattern) == 0: return 1

  result = 0
  for i in xrange(len(text)):
    if (text[i] == pattern[0]):
      # repeat the operation with the remaining string a pattern
      result += count_matches(text[i+1:], pattern[1:])

  return result

在 C 中:

int count_matches(const char text[],    int text_size, 
                  const char pattern[], int pattern_size) {

  if (pattern_size == 0) return 1;

  int result = 0;

  for (int i = 0; i < text_size; i++) {
    if (text[i] == pattern[0])
      /* repeat the operation with the remaining string a pattern */
      result += count_matches(text+i, text_size-(i+1), 
                              pattern+i, pattern_size-(i+1));
  }

  return result;  
}

注意:该算法有意为每个子字符串重复匹配。请不要关注算法执行的匹配类型，只关注其复杂性。

对算法中的(现已修复)拼写错误表示歉意

Answer 1

我认为复杂度为 O(length(text)^3) 的直觉是不正确的。它实际上是 O(n!) 纯粹是因为实现是形式

def do_something(relevant_length):
    # base case

    for i in range(relevant_length):
        # some constant time work

        do_something(relevant_length - 1)

如 Example of O(n!)? 中所述

如果使用memoization，递归树生成一次，之后每次都查找。

画出递归树的形状。

我们每层进步一个字符。有 2 个基本案例。当我们到达模式的末尾或者如果文本中不再有任何字符可以迭代时，递归就会触底。第一个基本情况是明确的，但第二个基本情况只是在给定实现的情况下发生。

所以递归树的深度(高度)为min[length(text), length(pattern)]。

有多少个子问题？我们还使每层进步一个字符。如果比较文本中的所有字符，使用高斯技巧对 S = [n(n+1)]/2 求和，则在所有递归层中将要评估的子问题总数为 {length(text) * [长度(文本) + 1]}/2。

取 length(text) = 6 和 length(pattern) = 10，其中 length(text) < length(pattern)。深度为 min[length(text), length(pattern)] = 6。

PTTTTT
PTTTT
PTTT
PTT
PT
P

如果 length(text) = 10 且 length(pattern) = 6 会怎么样，其中 length(text) > length(pattern)。深度为 min[length(text), length(pattern)] = 6。

PTTTTTTTTT
PTTTTTTTT
PTTTTTTT
PTTTTTT
PTTTTT
PTTTT

我们看到的是长度(模式)并没有真正有助于复杂性分析。在 length(pattern) < length(text) 的情况下，我们只是砍掉了一点高斯和。

但是，因为文本和模式一对一地向前推进，我们最终做的工作要少得多。递归树看起来像方阵的对角线。

对于 length(text) = 6 和 length(pattern) = 10 以及对于 length(text) = 10 和 length(pattern) = 6，树是

P
 P
  P
   P
    P
     P

因此，内存方法的复杂度是

O( min( 长度(文本), 长度(模式) ) )

编辑:鉴于@fons 的评论，如果递归从未被触发怎么办？特别是在 text[i] == pattern[0] for all i 永远不正确的情况下。然后遍历所有文本是主导因素，即使 length(text) > length(pattern)。

所以这意味着内存方法的实际上限是

O( 最大( 长度(文本), 长度(模式) ) )

再考虑一下，在 length(text) > length(pattern) 并且触发递归的情况下，即使 pattern 已用完，也需要恒定的时间来递归并检查 pattern 现在是否为空，因此 length (文本)仍然占主导地位。

这使得内存版本的上限为 O(length(text))。