Функция собирает список уникальных гостей из журнала регистрации длины n. Определите время выполнения в худшем случае.
Уникальные гости через список
Код
def unique_guests(log: list[str]) -> list[str]:
unique = []
for name in log:
if name not in unique:
unique.append(name)
return uniqueКакое время выполнения?
Ответ: O(n²)
Проверка x in list просматривает список подряд — O(длины списка). В худшем случае (все имена разные) список дорастает до n. Всего 0 + 1 + … + (n − 1) сравнений — O(n²). Если заменить список на множество set, проверка станет O(1) в среднем (это хеш-таблица), и вся функция — O(n).
- Подсказка 1
Сколько времени занимает проверка name in unique, если unique — это список?
- Подсказка 2
Сколько раз выполняется эта проверка и какой длины может быть список unique?