Complejidad del operador * in * en Python

¿Cuál es la complejidad del operador in en Python? ¿Es theta (n)?

¿Es lo mismo que lo siguiente?

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

L es una lista.

La complejidad de in depende completamente de lo que es L e in L se convertirá en L.__contains__(e) .

Vea este documento de complejidad de tiempo para la complejidad de varios tipos incorporados.

Aquí está el resumen para in :

  • lista – Promedio: O (n)
  • set / dict – Promedio: O (1), Peor: O (n)

El caso O (n) más desfavorable para conjuntos y dictados es muy poco frecuente, pero puede suceder si __hash__ se implementa de manera deficiente. Esto solo sucede si todo en tu conjunto tiene el mismo valor hash.

Depende totalmente del tipo de contenedor. Los contenedores de hash ( dict , set ) usan el hash y son esencialmente O (1). Las secuencias típicas ( list , tuple ) se implementan a medida que adivina y son O (n). Los árboles serían promedio O (log n). Y así. Cada uno de estos tipos tendría un método __contains__ apropiado con sus características big-O.

Depende del contenedor que estés probando. Normalmente es lo que se esperaría: lineal para estructuras de datos ordenadas, constante para los desordenados. Por supuesto, hay dos tipos (ordenados o no ordenados) que pueden estar respaldados por alguna variante de un árbol.