检查一个集合是否包含在另一个集合中的时间复杂度 [英] Time complexity of checking whether a set is contained in another set

问题描述

我正在尝试实现查找包含模式 char 的给定字符串 s 的最短子字符串的示例.我的代码运行良好，但我的目标是达到 O(N) 的时间复杂度，其中 N 是 s 的长度.这是我的代码；

I am trying to implement the example of finding the shortest substring of a given string s containing the pattern char. My code is working fine, but my goal is to attain the time complexity of O(N) where N is length of s. Here is my code;

def shortest_subtstring(s,char):
#smallest substring containing char.use sliding window
start=0
d=defaultdict(int)
minimum=9999
for i in range(len(s)):
    d[s[i]]+=1
    #check whether all the characters from char has been visited.
    while set(char).issubset(set([j for j in d if d[j]>0])):
        #if yes, can we make it shorter

        length=i-start+1
        minimum=min(length,minimum)
        if length==minimum:
            s1=s[start:i+1]
        d[s[start]]-=1
        start+=1
return (minimum,s1)

我的问题是在线；

 while set(char).issubset(set([j for j in d if d[j]>0]))

每次我检查char的所有字符串是否都保存在我的字典中，使用is.subset的思想.我可以知道如何在我的代码中找到这一步的时间复杂度吗?它是 O(1) 吗，这对于检查元素是否存在于集合中是正确的.否则时间复杂度会远大于O(N).感谢帮助.

Each time I am checking whether all strings of char are saved in my dictionary or not, using the idea of is.subset. May I know how can I find the time complexity of this step in my code? Is it O(1) , which is true for checking wether an element exists in a set or not. Otherwise, the time complexity will be much greater than O(N). Help is appreciated.

推荐答案

Per docs s.issubset(t) 相当于 s <= t 意味着在操作期间它将测试 s 中的每个元素是否是在 t.

Per docs s.issubset(t) is the equivalent of s <= t meaning that during the operation it will test if every element in s is in t.

最佳场景:如果 s 是 t 的第一个元素 -> O(1)

Best scenario: if s is the first element of t -> O(1)

最坏情况:如果 s 在 t 的最后一个元素 -> O(len(t))

Worst case scenario: if s in the last element of t -> O(len(t))

那是针对 isubset 的.对于列表理解:

That is for isubset. For the list comprehension :

j for j in d 是 O(n) 获取每个键

j for j in d is O(n) for getting each key

if d[j]>0 是 O(n) 比较字典 d

if d[j]>0 is O(n) for comparing each value of dictionary d

此处您可以找到更多信息.

这篇关于检查一个集合是否包含在另一个集合中的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！