Complexité de l'opérateur *in* en Python [fermé]

Quelle est la complexité de l' opérateur en Python? Est-ce thêta (n)?

Est-il le même que le suivant?

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

L est une liste.

25
demandé sur Peter Mortensen 2012-12-14 22:17:22
la source

3 ответов

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

Voir le document sur la complexité temporelle pour la complexité de plusieurs types.

Voici le sommaire in:

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

O(n) le pire des cas pour les ensembles et dicts est très rare, mais cela peut arriver si __hash__ est mal mise en place. Cela se produit uniquement si tout dans votre a la même valeur de hachage.

69
répondu Andrew Clark 2018-07-31 03:32:31
la source

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

8
répondu kindall 2014-04-24 19:08:02
la source

cela dépend du contenant que vous testez. C'est généralement ce que vous attendez - linéaire pour les structures de données ordonnées, constante pour les non ordonnées. Bien sûr, il y a les deux types (ordonnés ou non ordonnés) qui peuvent être soutenus par une certaine variante d'un arbre.

0
répondu Marcin 2012-12-14 22:20:15
la source

Autres questions sur