Какая алгоритмическая сложность проверки на вхождения элемента в список

Проверка вхождения элемента в список (element in list) в Python имеет линейную сложность O(n), так как в худшем случае необходимо пройти по всем элементам списка.

Пример:

my_list = [1, 2, 3, 4, 5]
print(3 in my_list)  # O(n) - поиск по всему списку

Оптимизация:
Если требуется частая проверка вхождения, лучше использовать множество (set), где поиск выполняется за O(1) (в среднем случае).

my_set = {1, 2, 3, 4, 5}
print(3 in my_set)  # O(1) - хеш-таблица

Вывод:
Для списков — O(n), для множеств — O(1). Выбор структуры зависит от частоты операций поиска.