python - 这个 Python 代码在字符串中查找字符串的时间复杂度是多少

Question

以下代码在其他字符串中搜索字符串的时间和空间复杂度是多少，在查找时，函数应返回第一次出现的索引，否则为 -1。

我假设时间复杂度为 O(m*n)，其中 m 是干草堆的长度，n 是针的长度。

但是，我搜索了 python slice 的内存复杂度，并在这里找到了这个答案 -字符串切片的时间复杂度，根据它是 O(n^2)。

那么下面函数的整体时间和空间复杂度是多少。

我们可以通过在 haystack 上使用memoryview来改进它吗？

class Solution:
  def strStr(self, haystack, needle):
    if haystack == needle or needle == "":
        return 0
    
    needle_len = len(needle)
    haystack_len = len(haystack)
    
    for i in range(0, haystack_len - needle_len + 1):
        if needle == haystack[i:i+needle_len]:
            return i
    
    return -1

标签： pythontime-complexity