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.
3 réponses
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.
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.
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.