Почему эти два куска кода имеют разные сложности? - PullRequest
Новая
       9

Почему эти два куска кода имеют разные сложности?

0 голосов
/ 01 декабря 2019

Оба этих фрагмента кода выполняют одно и то же: проверяют, достаточно ли слов в списке magazine_words, чтобы составить сообщение, продиктованное словами в списке note_words. Однако выполнение первого фрагмента кода занимает намного больше времени, что не позволяет ему работать при больших входах. Это почему? Поскольку оба решения используют одиночные циклы for, разве они не должны иметь одинаковую сложность, т. Е. Запускаться примерно одинаково?

Первое решение: 

lengths = input().split ()
m = int(lengths[0])
n = int(lengths [1])
magazine_words = input ().split()
note_words = input ().split()
def checkMagazine(m,n,magazine_words,note_words):
  flag = "Yes"
  for ind in range (n):
    if not (note_words[ind] in magazine_words):
      flag = "No"
      break
    else:
      magazine_words.remove(note_words[ind])
  return flag
print (checkMagazine(m,n,magazine_words,note_words))

Второе решение: 

def ransom_note(magazine, ransom):
    rc = {} # dict of word: count of that word in the note
    for word in ransom:
        if word not in rc:
            rc[word] = 0
        rc[word] += 1

    for word in magazine:
        if word in rc:
            rc[word] -= 1
            if rc[word] == 0:
                del rc[word]
                if not rc:
                    return True
    return False



m, n = map(int, input().strip().split(' '))
magazine = input().strip().split(' ')
ransom = input().strip().split(' ')
answer = ransom_note(magazine, ransom)
if(answer):
    print("Yes")
else:
    print("No")```

1 Ответ

1 голос
/ 01 декабря 2019

magazine_words.remove(note_words[ind]) - тайно другой цикл - он должен перебирать все magazine_words, пока не найдет note_words[ind], каждый раз, когда вы вызываете его.

...