Complexité de l'opérateur *in* en Python

Question

Quelle est la complexité de la in en Python ? Est-ce que c'est thêta(n) ?

Est-ce la même chose que ce qui suit ?

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

L est une liste.

Answer 1

La complexité de in dépend entièrement de ce que L est. e in L deviendra L.__contains__(e) .

Voir ceci document sur la complexité temporelle pour la complexité de plusieurs types intégrés.

Voici le résumé pour in :

• liste - Moyenne : O(n)
• set/dict - Moyenne : O(1), Pire : O(n)

Le pire cas O(n) pour les ensembles et les dicts est très rare, mais il peut se produire si __hash__ est mal implémenté. Cela ne se produit que si tous les éléments de votre ensemble ont la même valeur de hachage.

Answer 2

Cela dépend entièrement du type de conteneur. Les conteneurs de hachage ( dict , set ) utilisent le hachage et sont essentiellement O(1). Les séquences typiques ( list , tuple ) sont implémentés comme vous le devinez et sont O(n). Les arbres seraient en moyenne O(log n). Et ainsi de suite. Chacun de ces types aurait un __contains__ avec ses caractéristiques big-O.

Answer 3

Cela dépend du conteneur que vous testez. C'est généralement ce que vous attendez - linéaire pour les structures de données ordonnées, constant pour les structures non ordonnées. Bien sûr, il existe les deux types (ordonné ou non ordonné) qui pourraient être soutenus par une variante d'un arbre.