时间戳

首页 > 解决方案 > 为什么这两段代码有不同的复杂度？

python - 为什么这两段代码有不同的复杂度？

问题描述

这两段代码都做同样的事情，即检查列表中的单词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")```

标签： pythoncomparecomplexity-theory

解决方案

magazine_words.remove(note_words[ind])秘密地是另一个循环-每次调用它时，它都必须遍历所有magazine_words直到找到。note_words[ind]

推荐阅读