LeetCode 567 大 O 时间复杂度

Question

下面是我的LeetCode 567的解法https://leetcode.com/problems/permutation-in-string/

下面代码的大时间复杂度是多少？

它不应该是 O(n*m) 因为 if (pattern_map == str_map): 在代码中吗？

编辑：n = pattern_map, m = str_map 编辑 1：正如接受的答案所述，正确的值是 n = s1 的长度和 m = s2 的长度。

我查看了这个解决方案 10:00 标记 (https://www.youtube.com/watch?v=6gRj_FH3MsA)，他们似乎在使用数组。我不确定它可以是 O(N) 时间复杂度

class Solution:
        def checkInclusion(self, s1: str, s2: str) -> bool:
            
            pattern = s1
            str = s2
            
            pattern_map = {}
            str_map = {}
    
            for i in range(len(pattern)):
                patt_char = pattern[i]
                pattern_map[patt_char] = 1 + pattern_map.get(patt_char, 0)
    
            window_start = 0
            for i in range(len(str)):
                right_char = str[i]
                str_map[right_char] = 1 + str_map.get(right_char, 0)
    
                length_of_window = i-window_start+1
                if length_of_window == len(pattern):
                    left_char = str[window_start]
                    if (pattern_map == str_map):
                        return True
                    str_map[left_char] = str_map[left_char] - 1
    
                    if str_map[left_char] == 0:
                        del str_map[left_char]
    
                    window_start += 1
            
            return False

Answer 1

是的，这就像 O(N+M)，但为了简单起见，您可以只说 O(N)

Answer 2

是O(n + m)，其中n是s1的长度，m等于s2的长度。（这次分析假设字母表的大小固定在26，10^4大小绑定在s1和s2上只是为了保证代码可以在合理的时间内进行测试。）

第一个 for 循环有 O(n) 次迭代，并且每次迭代执行固定数量的工作。所以，它的运行时间是 O(n).

第二个 for 循环有 O(m) 次迭代。它在每次迭代中不断地工作。请注意，字典在字母及其计数之间进行映射。然而，问题陈述说“s1 和 s2 由小写英文字母组成。”这些字典的大小受常数限制（准确地说最多 26 个键），因此比较它们需要常数时间。循环中的其他一切都需要常数时间。所以这个循环需要 O(m) 时间。

因此，运行时间为 O(n + m)。

如果我们不能假设字母表的大小固定为常数（让 a 为字母表大小），那么我们第二个循环的每次迭代可能需要 O(a) 时间。然后，我们的运行时间将受到 O(n + a * m).

的限制

LeetCode 567 大 O 时间复杂度

Big O time complexity of LeetCode 567

python

big-o

time-complexity

sliding-window