Временная сложность операций набора python?

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

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

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

В Googling не появилось никаких ресурсов, но представляется разумным, что временная сложность реализации набора Python была бы тщательно рассмотрена.

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

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

Ответ 1

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

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

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

Ответ 2

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