python-3.x - 检查一个集合是否包含在另一个集合中的时间复杂度

Question

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

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. 我可以知道如何在我的代码中找到这一步的时间复杂度吗？Is it O(1)，这对于检查集合中是否存在元素是正确的。否则，时间复杂度将远大于O(N)。帮助表示赞赏。

标签： python-3.xsetsliding-window

Answer 1

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

最佳方案：如果 s 是 t 的第一个元素 -> O(1)

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

那是针对isubset的。对于列表理解：

j for j in d获取每个密钥的时间是 O(n)

if d[j]>0是 O(n) 用于比较字典的每个值d

在这里您可以找到更多信息。