Wyszukiwanie elementu w słowniku (dict) w Pythonie zazwyczaj ma amortyzowaną złożoność czasową O(1), czyli stałą. Osiąga się to dzięki użyciu tablicy haszującej.

Jednak w rzadkich przypadkach, na przykład gdy występuje wiele kolizji lub funkcja haszująca źle rozkłada klucze, złożoność może się pogorszyć do O(n), gdzie n to liczba elementów w słowniku.

W związku z tym wyszukiwanie nie zawsze jest ściśle O(1), ale w praktyce i w większości przypadków jest właśnie takie.

Poprzednia Dalej