python - count字符串函数的时间和空间复杂度是多少

Question

def count(substring, string):
    """
    >>> count("bc","abcabcabc")
    3
    """
    counter = 0
    for i in range(len(string) - len(substring) + 1):
        counter += string.startswith(substring, i)

    return counter

这是一个计算子字符串在基础字符串中出现的次数的函数。我认为时间复杂度是 O(n) 因为我只迭代字符串一次。我认为空间复杂度也是 O(n)，因为我在循环中递增了 N 次计数器。有人可以告诉我我是对还是错吗？

Answer 1

由于您提供的原因，时间复杂度为 O(nm)，其中 n=len(s) 和 m=len(t)，但递增 counter 不会导致占用更多空间，所以这个函数的空间复杂度是 O(1)。无论输入字符串有多长，您仍然只存储一个变量，count。

[编辑以更正海报指出的严重错误]