python - python 中文本分析器代码的时间复杂度

Question

letterList = ["a", 0, "b", 0, "c", 0, "d", 0, "e", 0, "f", 0, "g", 0, "h", 0, "i", 0,  "j", 0, "k", 0, "l", 0, "m", 0, "n", 0, "o", 0, "p", 0, "q", 0, "r", 0, "s", 0, "t", 0, "u", 0, "v", 0, "w", 0, "x", 0, "y", 0, "z", 0]
letterCount = 0
wordList = [None]
wordCount = 0
Count = 0
wordIndex = [0]
itext = cleaner(raw_input("enter itext please")).split()
print itext
for iword in itext:
    if iword in wordList:
        Count += 1
        for word in wordList:
            if iword == word:
                wordList[wordList.index(word)+1][0] += 1
                wordList[wordList.index(word)+1] += [wordCount]
            else:
                pass
    elif iword not in wordList:
        wordList += [iword]
        wordList += [[1, itext.index(iword)]]
    else:
        pass
    wordCount += 1
print wordList

代码看起来很乱，因为我在 python 和编程方面都是初学者。

谁能帮我解决代码的时间复杂度问题？

Answer 1

除了格式不同外，print itext 之后的所有内容都可以替换为:

print collections.Counter(itext)

复杂度为 O(n)。

如果没有 Counter，您可以使用字典而不是列表来更好地表达您的算法来存储字数:

word_counter = {}
for word in itext:
    if word in word_counter:
        word_counter[word] += 1
    else:
        word_counter[word] = 1

字典非常适​​合存储某物(这里是一个词)和其他东西(这里是一个计数)之间的关联。交替排列的单词和计数对的列表与字典相比有很多缺点，但致命的是在列表中查找单词的复杂度为 O(N) 而不是 O(1)。