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

Question

我创建这个算法是为了返回大海捞针中第一次出现的针的索引，如果该针不是大海捞针的一部分，则返回 -1。对于 Needle 和 haystack，它通过了 LeetCode，下界为 1，上限为 10 的 4 次方，人们说 O(n * m) 解决方案根本没有通过，所以我假设平均时间复杂度比这要好一些；但是，我无法确定，因为主 while 循环的时间复杂度很难理解。

代码是：

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("", "")

最糟糕的情况显然是干草堆是一个巨大的重复模式，而针在“哈哈哈哈哈哈”和“哈哈”或“aaaaaaaaaaaaaaaaaaaaaa”和“aa”等情况下遵循该模式。

Answer 1

您的算法本质上执行面包优先搜索，其中您将在上一次迭代中找到的所有部分匹配扩展为一个字符，并保留仍然匹配的那些。因此，对于最坏的情况，我们希望在尽可能多的迭代中拥有尽可能多的部分匹配。

其中一个最坏情况的输入可能是一个大小均匀的干草堆，其中 𝑛 乘以字母“a”，以及一根带有 𝑛/2 个字符的针，除了最后一个字母（最后一个字母是“b”）之外，所有字符都是“a” ”。例如，如果 𝑛 是 10：

haystack = "aaaaaaaaaa"
needle   = "aaaab"

while 1:

循环将进行 𝑛/2−2 次迭代（“minus-2”是在循环开始之前已经与 2 个字母匹配的结果）。

内部

for first, start, check in new

循环将进行 𝑛/2+1 次迭代

综合考虑，内部

if

语句将执行 (𝑛/2-2)(𝑛/2+1) 次，即 𝑛²/4−𝑛/2−2 次，即 O(𝑛²)，并且因此是算法的时间复杂度。

人们说 O(n * m) 个解决方案根本没有通过

您已提供证据证明他们的说法是错误的。在这里，重要的是要认识到时间复杂度绝对“没有说明”算法需要多少时间来处理“实际”（有限！）输入。时间复杂度与渐近行为有关。