这个 python 包含切片操作的函数的时间复杂度是多少？

Question

我正在学习 python 切片操作，我决定编写一个简单的函数来遍历 window 大小为 k 的字符串，并将 window 添加到字典中以其频率。因此，例如，如果字符串输入为“abab”且 k 为 2，则字典将包含“ab:2”和“ba:1”。

我很困惑这个函数的时间复杂度是多少：

代码中，s为输入字符串，k为window大小。

def test_func(s, k):
    d = {}
    for i in range(len(s) - k + 1):
        sub_str = s[i:i+k]
        if sub_str in d:
            d[sub_str] += 1
        else:
            d[sub_str] = 1
    return d

我认为它的时间复杂度为 O(n * k)，space 它的复杂度为 O(n)，其中 n 是列表的大小，k 是 [=22 的大小=] 但我不确定它是否正确。您能否查看该功能并让我知道我的分析是否正确？谢谢！

Answer 1

时间和space都应该是O(n*k)。

查找大小为k的字典键是O(k)，因为你要散列k，这需要读取k的所有字符。虽然我们经常将字典和查找设置为分摊常数时间，但我认为当字典键大小是参数之一时我们不能使用这种简化。

由于您执行这些查找 O(n) 次，时间复杂度为 O(n*k)。

由于所有的键都必须存储在字典中，最坏的情况是没有重复的切片，因此字典可能必须包含 n*k 个键。