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

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;  
}

注意：该算法有意地为每个子字符串重复匹配。请不要关注算法执行何种类型的匹配，而是关注它的复杂度。

抱歉算法中出现的拼写错误已经被修复。

- fons

---

我认为这两个例子都必须是错误的，而且它们并不相同。 - Antti Haapala -- Слава Україні

@AnttiHaapala 他们为什么是错误的和不同的？ - fons

是的，我会纠正它，我的错。 - fons

另一个简单的返回值显然是 if (text_len < pattern_len) return 0;。 - joop

在递归调用中，根据 Python 版本，C 版本中的参数 text+i, text_size-(i+1), pattern+i, pattern_size-(i+1) 是否应该改为 text+i+1, text_size-(i+1), pattern+1, pattern_size-1？第一个、第三个和第四个参数似乎不正确 O_O ... - Gassa

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)

如在O(n!)示例中所讨论的那样，如果使用记忆化，则递归树仅生成一次并在之后每次查找。

想象一下递归树的形状。

我们每层进展一个字符，有两个基本情况。当我们到达模式的末尾或者没有字符可以迭代时，递归结束。第一个基本情况是明确的，但是第二个基本情况只是由于实现而发生。

因此，递归树的深度（高度）为min[length(text), length(pattern)]。

有多少子问题？我们每层进展一个字符。如果比较了文本中的所有字符，使用高斯技巧求和S = [n(n+1)] / 2，将在所有递归层上评估的子问题总数为{length(text) * [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

如果文本长度为10，模式长度为6，并且文本长度大于模式长度，那么深度为min[length(text), length(pattern)] = 6。

PTTTTTTTTT
PTTTTTTTT
PTTTTTTT
PTTTTTT
PTTTTT
PTTTT

我们看到，长度（模式）实际上并不对复杂性分析有贡献。在长度（模式）小于长度（文本）的情况下，我们只是切掉了高斯求和的一小部分。

但是，由于文本和模式一起向前步进，每次只进行一步操作，我们最终做的工作要少得多。递归树看起来像一个正方形矩阵的对角线。

对于长度（文本）= 6 和长度（模式）= 10，以及长度（文本）= 10 和长度（模式）= 6 的情况，树形结构如下：

P
 P
  P
   P
    P
     P

因此，备忘录方法的复杂度为 O(min(length(text), length(pattern)))。

编辑：考虑到@fons的评论，如果递归从未触发会怎样？特别是在所有i中text[i]==pattern[0]都不为真的情况下。那么遍历整个text是主要因素，即使length(text)>length(pattern)。

因此，备忘录方法的实际上限是O(max(length(text), length(pattern)))。

再仔细思考一下，在length(text)>length(pattern)且递归被触发的情况下，即使pattern用完了，递归和检查pattern是否为空也只需要常数时间，因此length(text)仍然占主导地位。

这使得备忘录版本的上限为O(length(text))。

- chiaboy

---

我理解原始算法的复杂性，认为它是有道理的，但我不同意记忆化版本。例如，对于长度(text) = t，长度(pattern) = p，其中t > p，且在t中没有匹配p的情况下，复杂度为O(length(text))。 - fons

@fons，看起来你是对的。假设您的意思是“p中没有t的匹配项”，因为对于所有i，text[i] == pattern[0]永远不成立，递归实际上总是被跳过的。因此，似乎在所有情况下都使用max而不是min作为上限。 - chiaboy

在认真思考后，我对原回答进行了编辑，甚至消除了两个长度的最大值。 - chiaboy

Answer 2

额嗯...我可能错了，但就我所见，您的运行时间应该集中在这个循环上：

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

基本上让你的文本长度为n，我们不需要模式的长度。

第一次运行此循环（在父函数中），我们将有n次调用。这n个调用中，每个调用在最坏情况下会调用n-1个程序实例。然后，这n-1个实例在最坏情况下会调用n-2个实例，依此类推。

这导致一个方程式，即n*(n-1)(n-2)...*1，即n!。因此，您的最坏情况运行时间为O(n!)。相当糟糕（：

我多次运行了您的Python程序，并输入了最坏情况运行时间的输入：

In [21]: count_matches("aaaaaaa", "aaaaaaa")

Out[21]: 5040

In [22]: count_matches("aaaaaaaa", "aaaaaaaa")

Out[22]: 40320

In [23]: count_matches("aaaaaaaaa", "aaaaaaaaa")

Out[23]: 362880

最后一个输入是9个符号，9！= 362880。

为了分析算法的运行时间，您需要首先考虑导致最坏可能运行时间的输入。在您的算法中，最好和最坏情况差别很大，因此您可能需要平均情况分析，但这相当复杂。（您需要定义什么输入是平均的以及最坏情况会出现多少次。）

动态规划可以帮助减轻您的运行时间，但分析更加困难。让我们先编写一个简单的未经优化的动态规划版本：

cache = {}
def count_matches_dyn(text, pattern):
  if len(pattern) == 0: return 1

  result = 0
  for c in text:
    if (c == pattern[0]):
      # repeat the operation with the remaining string a pattern
      if ((text[1:], pattern[1:]) not in cache.keys()):
        cache[(text[1:], pattern[1:])] = count_matches_dyn(text[1:], pattern[1:])
        result += cache[(text[1:], pattern[1:])]
      else:
        result += cache[(text[1:], pattern[1:])]

  return result

在这里，我们将所有对count_matches的调用缓存到一个字典中，因此当我们使用相同的输入调用count_matches时，我们将获得结果，而不是再次调用该函数。（这被称为记忆化）。

现在让我们分析一下。主循环

  for c in text:
    if (c == pattern[0]):
      # repeat the operation with the remaining string a pattern
      if ((text[1:], pattern[1:]) not in cache.keys()):
        cache[(text[1:], pattern[1:])] = count_matches_dyn(text[1:], pattern[1:])
        result += cache[(text[1:], pattern[1:])]
      else:
        result += cache[(text[1:], pattern[1:])]

第一次调用时（我们的缓存为空），将运行n次。但是第一个递归调用将填充缓存：

cache[(text[1:], pattern[1:])] = count_matches_dyn(text[1:], pattern[1:])

同一循环中的所有其他调用成本都为(O(1)。因此，基本上顶级递归的成本将为O(n-1) + (n-1)*O(1) = O(n-1) + O(n-1) = 2*O(n-1)。您可以从更深层次的递归调用中看到，只有第一个调用（O(n-1)调用）会下降并进行许多递归调用，并且其余部分的成本是O(1)，因为它们只是字典查找。考虑到这一切，运行时是(2*O(n-1)，摊销为O(n)。

免责声明。我不确定动态编程版本的分析是否完全正确，请随意纠正我（:

免责声明2。动态编程代码包含昂贵的操作（text[1:], pattern[1:]），这些操作没有计入分析。这是故意做的，因为在任何合理的实现中，您都可以大幅降低这些调用的成本。重点是展示如何通过简单的缓存大大减少运行时间。

- XapaJIaMnu

---

大O符号并不意味着最坏情况 - 它只是一种描述函数渐近行为的方式。只是在分析算法复杂度时，最坏情况的运行时间通常是我们最感兴趣的。 - psmears

@psmears 确实，是我的错。我会修复它的。 - XapaJIaMnu

并不完全正确。text[1：]，pattern[1：]这两个操作导致实际复杂度为O（n ^ 2）。如果您一直创建它们，那将会非常慢。 - Jason Hu

@HuStmpHrrr 这是真的，但我只做了一个非常简化的缓存。在任何合理的实现中，这些字符串操作都会更加优化（在C语言中，您可以预先知道确切的大小并使用数组复制）。我相信动态规划提供的加速主要观点仍然成立。 - XapaJIaMnu

同意。我只想强调讨论算法的复杂性和在Python中实际实现是不同的。在Python中进行一些小操作可能会带来巨大的开销，而很难引起注意。 - Jason Hu

为什么会有踩？！我回复时算法不同了，作者明确指出不要修复他的算法而是分析它本身... - XapaJIaMnu

Answer 3

• 首先，让我们超越代码，明确这段代码试图解决的问题。

Python 版本似乎是将 pattern 的出现次数作为 text 的子序列。C 版本目前看起来有问题，因此我假设 Python 版本是正确的。

• 然后，回顾代码并注意一些关于如何执行解决方案的一般事情。

该函数通过加上 0 和 1 来计算答案。因此，操作次数至少是需要加起来得到答案的 1 的数量，也就是答案本身。

• 现在，让我们设计一个输入 (text, pattern)，以获得给定长度的 text 和 pattern 的最坏运行时间。

最大的答案显然是所有字母都相等的情况。

• 之后，我们使用上述简化的输入和一些数学知识直接计算答案。

当所有字母都相等时，答案本质上是从 n = len(text) 个项目（字母）中选择 k = len(pattern) 个项目的方式数，即 choose(n, k)。

• 接下来，我们选择长度为 text 和 pattern 的最坏复杂度。

举例来说：text = 'a' * 100 和 pattern = 'a' * 50，我们有答案 选择 (100, 50) = 100! / 50! / 50!。 通常情况下，对于固定长度的text，pattern的长度必须是该长度的一半，取整到最近的整数。 当查看Pascal's triangle时，这是一种直观的概念。 形式上，手动比较choose (n, k)和choose (n, k+-1)可以轻松证明这一点。

• 估计我们得到的答案。

总和choose (n, 0) + choose (n, 1) + ... + choose (n, n)是2ⁿ，直观地说，choose (n, n/2)也是相当大的一部分。

更正式地说，根据斯特林公式，它表明choose (n, n/2)与2ⁿ除以sqrt(n)同阶。

• 最后，请注意更详细的分析可能是不必要的。

当复杂度呈指数级增长时，我们通常对精确的多项式因子不太感兴趣。 例如，2¹⁰⁰ (O (2^n)) 和 100 倍的 2¹⁰⁰ (O (n * 2^n)) 操作同样难以在合理的时间内完成。 重要的是将 O (2^n) 减少到 O (2^(n/2)) 或者更好地找到一个多项式解决方案。

• 请记住，我们找到的是下限。

实际上，如果我们在顶部添加以下行，则复杂度确实将是 choose (len (text), len (pattern) 乘以某个多项式：

if len(pattern) < len(text): return 0

事实上，如果文本中剩余的字母数量小于模式的长度，则不存在匹配。

• 这是从另一个角度的观点。

否则，我们将有更多的递归分支，最终导致答案加0。

通过从另一侧观察，我们可以证明未改变代码的操作次数可以高达 len（text） 的 2 次方。

确实，当text ='a'*n 且 pattern ='a'*n 时，假设我们已经处理了 k 封信。每个字母都可以与某个字母匹配或在循环中留下，而不依赖于其他字母。因此，对于text 的每个字母，我们有两种方法可选，因此当我们处理完 text 的 n 个字母时，也就是到达我们递归函数的终止调用时，有 2^n 种可能。

- Gassa

Answer 4

时间复杂度应该提高到O（length(text) * length(pattern)）的级别，从递归的O(n!)改进。

记忆化解决方案（DP）将涉及构建文本与模式的查找表，可以从文本和模式的末尾开始逐步构建。

- sray

Answer 5

很抱歉，您的算法在模式匹配方面是不正确的。主要是因为一旦找到第一个字符匹配，它就会在剩余的文本中搜索子子字符串。 例如，对于文本“abbccc”和模式“accc”，您的算法将返回等于1的结果。

您应该考虑实现“Naive”算法进行模式匹配，这与您尝试做的非常相似，但没有递归。其复杂度为O(n*m)，其中'n'是文本长度，'m'是模式长度。 在Python中，您可以使用以下实现：

text = "aaaaabbbbcccccaaabbbcccc"
pattern = "aabb"
result = 0

    index = text.find(pattern)
    while index > -1:
        result += 1
        print index
        index = text.find(pattern, index+1)

return result

关于这个主题的书籍，我最好的推荐是Cormen的"算法导论", 它涵盖了所有关于算法和复杂性的材料。

- user4670243

---

算法故意设计成这样，它并没有错误。对于文本“abbccc”和模式“accc”，预期该算法返回结果为1。我将从问题标题中删除“模式匹配”部分，以使其更加清晰易懂。 - fons