Как да определим времевата сложност на операцията за четене на елементи в множества, реализирани в Python?

В Python, множествата (set) са реализирани на базата на хеш таблици.

Операцията за четене (проверка дали елемент съществува) в множество има амортизирана времева сложност O(1) — тоест, изпълнява се за постоянно време в средния случай.

Това означава, че проверката дали елемент е в множество, е много бърза и не зависи от размера на множеството.

Пример:

s = {1, 2, 3, 4}
if 3 in s:
    print("Елементът е намерен")

Тук операцията 3 in s се изпълнява за O(1) в средния случай.