Сложность оператора * in * в python

Какова сложность оператора в в python? это тета (n)?
Это то же самое, что

def find(L, x)
   for e in L:
       if e == x:
           return True
   return False

? L - это список

Ответ 1

Сложность in полностью зависит от того, что L. e in L станет L.__contains__(e).

См. этот Документ сложности времени для сложности нескольких встроенных типов.

Вот сводка для in:

list - Average: O (n)
set/dict - Average: O (1), Худший: O (n)

Наихудший случай O (n) для множеств и dicts очень необычен, но может произойти, если __hash__ выполняется плохо. Это происходит только в том случае, если все в вашем наборе имеет одинаковое значение хеша.

Ответ 2

Это полностью зависит от типа контейнера. Хеширующие контейнеры (dict, set) используют хеш и суть O (1). Типичные последовательности (list, tuple) реализованы, как вы предполагаете, и являются O (n). Деревья будут средними O (log n). И так далее. Каждый из этих типов будет иметь соответствующий метод __contains__ с его характеристиками большого O.

Ответ 3

Это зависит от тестируемого контейнера. Обычно это то, что вы ожидаете - линейное для упорядоченных структур данных, постоянное для неупорядоченных. Конечно, существуют оба типа (упорядоченные или неупорядоченные), которые могут быть подкреплены некоторым вариантом дерева.