python - python字符串匹配时间复杂度

Question

我需要这个问题的帮助。我认为时间复杂度是 O(n)，但我朋友坚持认为这是 O(n^2)。原因之一是因为fn = fn[index+1 ::]

#filename: string_expression_matcher.cc
#string: stxpm.c
#should return



import sys
string = "string_expression_matcher.cc"
subStr = "stxpm.c"

fn = list(string)
for i in subStr:
    try:
        index = fn.index(i)
        fn = fn[index+1 ::]
    except:
        print ("can't dup")
        sys.exit()

print ("found") 

这是我的算法：

1. subStr 中的 s：
   • 循环开始于：“string_expression_matcher.cc”
   • 此步骤剩余的字符串输出为：“tring_expression_matcher.cc”
2. subStr 中的 t
   • 循环开始于：“tring_expression_matcher.cc”
   • 剩下的是：“ring_expression_matcher.cc”
3. x in subStr
   • 循环开始于：“ring_expression_matcher.cc”
   • 剩下的是：“pression_matcher.cc”
4. p in subStr
   • 循环开始于：“pression_matcher.cc”
   • 剩下的是：“ression_matcher.cc”

等等到最后一步。

鉴于：

n = len(subStr)
m = len(string)`

这个程序的时间复杂度是多少？谢谢大家，但我真的很想知道是 O(n) 还是 O(n^2)。我知道代码并不完美，但请关注时间复杂度。非常感谢

有谁知道python字符串复制是如何工作的？当我们执行 fn = fn[index+1 ::] 时会发生什么？

我问了一位杰出的工程师。他说结果是 O(m*n)。你呢？

Answer 1

您的算法（就比较次数而言）是O(n)，其中n是字符串的长度。在最坏的情况下，字符串和模式都将是相同的，然后对于您中的每个字符，subStr您将移动到string. 它相当于字符串的简单比较。

但是，您的实现可能是O(n^2)在其他操作方面，正如您在问题中提到的那样，其原因是以下行：

fn = fn[index+1 ::]

这实际上是在复制字符串（假设上面的切片是作为副本实现的）。如果您再次考虑前面的示例，对于字符串中的每个字符，您必须复制所有剩余的字符，即O(n^2). 这是因为您将首先复制n-1字符，然后n-2是 ，n-3依此类推，在最后一次迭代中，您将只复制一个字符。那么要复制的项目总数将是n-1+ n-2+ ...+ 1，作为等差数列，它等于(n-1)*((n-1)+1)/2 = (n-1)*n/2 = O(n^2)。对于其他情况，这可以概括为O(m*n)，其中m是模式的长度。

你的朋友可能想告诉你的是：你的算法是线性的，但你的实现不是。不过也很容易解决。使用@thkang 提供的解决方案或更透明的方法来消除隐藏的复杂性，例如：

try:
  si = iter(string)
  for c in subStr:
    while c != si.next():
      pass
except StopIteration:
  print "no match"
else:
  print "match"

Answer 2

很抱歉，但这既不是 O(n) 也不是 O(n+m)。它们都比 O(n^2) 好，这个算法是 O(n^2)。为什么？

1. 您迭代具有 O(n) 复杂度的源字符串
2. 在每次迭代中，您在字符串上调用“索引”，该字符串也具有 O(n) 复杂度

所以这具有由 O(n^2) 限制的最坏情况性能，实际上是朴素搜索算法的一种实现。如果您想查看 O(n)/O(mn)，我建议您查看Boyer-Moore 算法

Answer 3

如果您不想复制整个列表，请使用.index指定的起始索引。

last_index = 0
for i in subStr:
    try:
        last_index = fn.index(i, last_index) + 1
    except ValueError:
        print ("can't dup")
        sys.exit()
else:
    #string matches