Ako určiť časovú zložitosť operácie čítania prvkov v množinách implementovaných v Pythone?

V Pythone sú množiny (set) implementované na základe hash tabuliek.

Operácia čítania (kontrola, či prvok existuje) v množine má amortizovanú časovú zložitosť O(1) — čo znamená, že sa vykonáva v konštantnom čase v priemere.

To znamená, že kontrola, či je prvok v množine, je veľmi rýchla a nezávisí od veľkosti množiny.

Príklad:

s = {1, 2, 3, 4}
if 3 in s:
    print("Prvok nájdený")

Tu sa operácia 3 in s vykonáva v priemere za O(1).