Какова сложность оператора в в python? это тета (n)?
Это то же самое, что
def find(L, x)
for e in L:
if e == x:
return True
return False
? L - это список
Сложность in полностью зависит от того, что L. e in L станет L.__contains__(e).
См. этот Документ сложности времени для сложности нескольких встроенных типов.
Вот сводка для in:
Наихудший случай O (n) для множеств и dicts очень необычен, но может произойти, если __hash__ выполняется плохо. Это происходит только в том случае, если все в вашем наборе имеет одинаковое значение хеша.
Это полностью зависит от типа контейнера. Хеширующие контейнеры (dict, set) используют хеш и суть O (1). Типичные последовательности (list, tuple) реализованы, как вы предполагаете, и являются O (n). Деревья будут средними O (log n). И так далее. Каждый из этих типов будет иметь соответствующий метод __contains__ с его характеристиками большого O.
Это зависит от тестируемого контейнера. Обычно это то, что вы ожидаете - линейное для упорядоченных структур данных, постоянное для неупорядоченных. Конечно, существуют оба типа (упорядоченные или неупорядоченные), которые могут быть подкреплены некоторым вариантом дерева.