字符串匹配 - best/worst case big-O 复杂度

Question

我有点卡在这上面，不太明白如何解决它。我看过 YouTube 等。无法理解如何回答这个问题。

def PatternMatch(text, searchspace):
    for pattern in searchspace:
          for offset in range(text.length):
              match = True
              for cmp in range(min(pattern.length,text.length-offset)):
                  if (text[offset+cmp] != pattern[cmp]):
                      match = False
                      break
              if (match) return offset
    return -1

此算法returns 文本 T 中 k > 0 个模式 P 的数组中任何模式首次出现的偏移量，如果 P 中没有模式出现在 T 中则为 -1。P 属于表格 ["string","string","striiing"]

如果我们假设该算法仅在P 中最短模式的长度小于或等于T 的长度时被调用，那么PatternMatch 的最佳和最坏情况下的big-Oh 复杂度是多少？我将如何解决这个问题？

Answer 1

根据模式和测试字符串的大小，这确实有很大差异。我假设两者的长度都是 n（为了计算简单，因为实际情况应该具有相同的时间复杂度）并且有 k 个字符串正在测试每个字符比较都需要 O(1) 时间，并且您对每个匹配的字符串执行 n 个长度为 1..n 的字符串比较（即 1..n 字符比较）。这是 (n^2+n)/2 次比较 = O(n^2)。由于有 k 个这些测试，复杂度为 O(n^2k)。

Answer 2

让我们假设 k 个长度相等的模式 m 和一个长度为 n 的文本。

最好的情况似乎很简单：如果与第一个模式的第一次比较立即成功，则在 m 个字符比较后返回答案，其中 m 是第一个模式的长度。无论如何，如果所有模式测试尽快结束“不匹配”，您可以获得更快的结果，这可以在 n-m+1 字符比较中实现，因此在总共 k(n-m+1) 比较之后。虽然不太可能，但 k(n-m+1) < m 是可能的。

最坏的情况要困难一些。我们可以想象它发生在所有模式都匹配失败时，因此需要进行k次匹配。现在得出不匹配结论的最长时间是当所有偏移量都导致失败时，同时尽可能进行字符串比较。

当您在 xxxxxxxxxxxxxxxxxxxx 中搜索类似 xxxxxxxy 的模式时会发生这种情况：必须始终完整执行字符串比较。

所以我们总共有 worst-case 个 k(n-m+1)m 个字符比较。如果长度不固定，精确分析就变得很困难。

字符串匹配 - best/worst case big-O 复杂度

string matching - best/worst case big-Oh complexity

big-o

pattern-matching

time-complexity