Стоимость подсчёта частот: dict.get против сортировки списка
Нужно посчитать, сколько раз встречается каждое слово в списке из миллиона элементов. Два варианта:
# A
counts = {}
for w in words:
counts[w] = counts.get(w, 0) + 1
# B
counts = {}
for w in set(words):
counts[w] = words.count(w)
Как соотносятся их сложности по времени?
- A — O(n), B — O(n·u), где u — число различных слов: `list.count` каждый раз проходит весь список
- Оба O(n): `list.count` реализован на C и потому выполняется за константу
- A — O(n log n) из-за хеширования каждого слова, B — O(n)
- A — O(n), B — O(n log n): `set(words)` внутренне сортирует значения