查找字符串中每个字符出现的次数的复杂性

Question

input_string = "foobaarfoooobaaaarfo"
count_dict = {}
for char in input_string:
    try:
        count_dict[char]=count_dict[char]+1
    except:
        count_dict[char]=1
print(count_dict)

对于给定的问题陈述，这是复杂度为O（N）的最佳算法吗

Answer 1

是的，O(n)是你能做的最好的了。你知道吗

有必要访问每个角色以将其全部计算在内。你知道吗

但是，就python实现而言，使用专门的集合Counter可能会获得更好的性能和更可读的代码：

from collections import Counter
input_string = "foobaarfoooobaaaarfo"
counter = Counter(input_string)
print(counter)

Answer 2

我同意O(N)是你能做的最好的。你知道吗

我简化了你的程序。您不必在这里使用try和raisexception。你知道吗

input_string = "foobaarfoooobaaaarfo"
count_dict = {}
for char in input_string:
    count_dict[char] = count_dict.get(char, 0) + 1
print(count_dict)