Временная сложность операций над множествами Python?

Question

Какова временная сложность каждой из операций над множествами python в Big O нотации?

Я использую Python set type для операции с большим количеством элементов. Я хочу знать, как на производительность каждой операции будет влиять размер набора. Например, добавить , а тест на членство:

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

Поиск в Google не нашел ресурсов, но кажется разумным, что временная сложность реализации набора Python была бы тщательно рассмотрена.

Если он существует, ссылка на что-то вроде this будет великолепной. Если ничего подобного нет, то, может быть, мы сможем решить это?

Дополнительные отметки для определения сложности времени всех операций над множествами.

Answer 1

Согласно Python wiki: сложность времени , set реализована в виде хеш-таблицы . Таким образом, вы можете ожидать поиска / вставки / удаления в среднем O (1) . Если коэффициент загрузки вашей хеш-таблицы не слишком высок, тогда вы столкнетесь с коллизиями и O (n).

P.S. по какой-то причине они требуют O (n) для операции удаления, которая выглядит как опечатка.

P.P.S. Это верно для CPython, pypy - это другая история .

Answer 2

Операция in должна быть независимой от размера контейнера, т.е. O (1) - с учетом оптимальной хеш-функции. Это должно быть почти верно для строк Python. Хэширование строк всегда важно, Python должен быть умным, и поэтому вы можете ожидать почти оптимальных результатов.