Временная сложность проверки, содержится ли набор в другом наборе - PullRequest
Новая
       76

Временная сложность проверки, содержится ли набор в другом наборе

0 голосов
/ 11 апреля 2020

Я пытаюсь реализовать пример поиска самой короткой подстроки данной строки 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. Могу ли я узнать, как найти временную сложность этого шага в моем коде? Это O(1), что верно для проверки, существует ли элемент в наборе или нет. В противном случае временная сложность будет намного больше, чем O(N). Помощь приветствуется.

1 Ответ

1 голос
/ 22 апреля 2020

По документам 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

Здесь Вы можете найти больше информации.

...