我的字符串搜索算法的平均和最坏时间复杂度是多少？

Question

我写了一个算法，用来找出“针”在“干草堆”中第一次出现的位置，如果找不到，就返回-1。这个算法在LeetCode上测试通过了，干草堆和针的长度范围是从1到10000。有人说O(n * m)的解法根本过不了，所以我猜这个算法的平均时间复杂度应该比那个要好一些；不过我不太确定，因为主循环的时间复杂度有点难理解。

代码如下：

def stringSearch(haystack, needle):
    s = []
    
    if len(needle) == 1:
        for i,n in enumerate(haystack):
            if n == needle:
                return i
        return -1

    for i,n in enumerate(haystack):
        if n == needle[0] and (len(haystack) - i) >= len(needle):
            s.append(i)
    
    new = []
    for i in s:
        if i + 1 < len(haystack) and haystack[i + 1] == needle[1]:
            new.append((i, i + 1, 2))
    if new and len(needle) == 2:
        return new[0][0]

    while 1:
        temp = []
        for first, start, check in new:
            if haystack[start + 1] == needle[check]:
                temp.append((first, start + 1, check + 1))
                if check + 1 >= len(needle):
                    return first
        if not temp:
            return -1
        new = temp
stringSearch("", "")

最糟糕的情况显然是干草堆是一个巨大的重复模式，而针正好跟这个模式匹配，比如“hahahahahahahah”和“haha”，或者“aaaaaaaaaaaaaaaaaaaaa”和“aa”。

Answer 1

你的算法其实是在做一种叫“广度优先搜索”的操作，也就是在之前找到的部分匹配的基础上，每次增加一个字符，然后保留那些仍然匹配的部分。所以在最坏的情况下，我们希望能有尽可能多的部分匹配，并且能进行尽可能多的迭代。

一个可能的最坏情况输入是一个大小为偶数的字符串，其中有很多个字母“a”，而要找的字符串（也就是“针”）有一半的字符都是“a”，最后一个字符是“b”。比如说，如果这个数量是10：

haystack = "aaaaaaaaaa"
needle   = "aaaab"

这个 while 1: 循环会进行 /2−2 次迭代（“减去2”是因为在这个循环开始之前，已经有两个字母匹配了）。

里面的 for first, start, check in new 循环会进行 /2+1 次迭代。

把这两部分加起来，里面的 if 语句会被执行 (/2-2)(/2+1) 次，也就是 ²/4−/2−2 次，这样的复杂度是 O(²)，所以这就是你算法的时间复杂度。

有人说 O(n * m) 的解决方案根本无法通过测试

你已经证明了他们的说法是错误的。在这里要明白，时间复杂度并不能说明一个算法处理实际（有限的！）输入需要多长时间。时间复杂度主要是关于算法在输入规模无限增大时的表现。