Złożoność czasowa operacji zestawu Pythona?

Question

Jaka jest złożoność czasu każdej z ustawionych operacji Pythona w notacji Big O?

Używam Pythona set type do operacji na dużej liczbie elementów. Chcę wiedzieć, jaki wpływ na wydajność każdej operacji ma rozmiar zestawu. Na przykład, add, i test członkostwa:

myset = set() 
myset.add('foo') 
'foo' in myset 

googlowania wokół nie okazało się żadnych zasobów, ale wydaje się rozsądne, że złożoność czas realizacji zadanej Pythona byłby dokładnie rozważyć.

Jeśli istnieje, link do czegoś takiego jak this byłby świetny. Jeśli nic takiego nie istnieje, to może uda się to rozwiązać?

Dodatkowe znaki za znalezienie złożoności czasowej wszystkich operacji zestawu.

Answer 1

Operacja in powinna być niezależna od wielkości pojemnika, tj. O (1) - biorąc pod uwagę optymalną funkcję skrótu. To powinno być prawie prawdziwe dla napisów w języku Python. Sznurowanie jest zawsze krytyczne, Python powinien być sprytny i dlatego można oczekiwać niemal optymalnych rezultatów.

Answer 2

Zgodnie z Python wiki: Time complexity, zestaw jest zaimplementowany jako hash table. Więc możesz oczekiwać, że będziesz wyszukiwał/wstawiał/usuwał średnio o O (1). O ile współczynnik obciążenia tabeli mieszania nie jest zbyt wysoki, występują kolizje i O (n).

P.S. z jakiegoś powodu twierdzą, że O (n) do operacji usuwania, która wygląda jak błąd.

P.P.S. Dotyczy to CPython, pypy to different story.