Сложность времени операций набора Python?

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

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

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

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

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

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


python set data-structures big-o complexity-theory
person Stephen Emslie    schedule 08.09.2011    source источник
comment
Хотя ссылка GWW очень информативна, вы можете рассуждать о временной сложности наборов Python, понимая, что они являются просто частными случаями словаря Python (ключи, но не значения). Итак, если вы знаете временную сложность операций на хэш-карте, вы в значительной степени на месте.   -  person Wilduck    schedule 08.09.2011

Ответы (3)


arrow_upward
90
arrow_downward

Согласно вики Python: временная сложность, set реализован как < href = "https://en.wikipedia.org/wiki/Hash_table" rel = "noreferrer"> хеш-таблица. Таким образом, вы можете рассчитывать на поиск / вставку / удаление в среднем за O (1). Если коэффициент загрузки вашей хеш-таблицы не слишком высок, вы столкнетесь с коллизиями и O (n).

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

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

person Sergey Romanovsky    schedule 19.05.2017
comment
Набор в python также выполняет автоматическую сортировку. Как вы думаете, вставка нового значения по-прежнему занимает O (1) временную сложность - person Naresh Thakur; 23.01.2020
comment
@thakurinbox Не могли бы вы подкрепить свое утверждение ссылкой? - person Sergey Romanovsky; 23.01.2020
comment
Автоматический заказ без сортировки. - person Codeformer; 03.07.2021

arrow_upward
8
arrow_downward

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

person towi    schedule 08.09.2011

arrow_upward
4
arrow_downward

В других ответах не говорится о двух важнейших операциях над множествами: объединениях и пересечениях. В худшем случае объединение займет O (n + m), тогда как пересечение займет O (min (x, y)) при условии, что в наборах не так много элементов с одинаковым хешем. Список временных сложностей общих операций можно найти здесь: https://wiki.python.org/moin/TimeComplexity

person Fırat Kıyak    schedule 11.07.2020