CKTIS / Python
Performances et complexité
Étudie la croissance du travail avec la taille des données indépendamment du temps mesuré.
Version : Python 3.14; repository image, production runtime not attested
Syntaxe
bisect_left(sorted_values, target)Étudie la croissance du travail avec la taille des données indépendamment du temps mesuré.
Un balayage peut parcourir toute la liste, tandis que la recherche binaire sur données triées divise l’intervalle par deux et effectue un nombre logarithmique de comparaisons. L’indice d’insertion exige encore un contrôle de borne et d’égalité.
Trier et insérer dans une liste ont des coûts distincts.
Exemples
from bisect import bisect_left
values = list(range(0, 32, 2))
def lookup(target):
reads = 0
def key(x):
nonlocal reads
reads += 1
return x
index = bisect_left(values, target, key=key)
found = index < len(values) and values[index] == target
return found, reads
print(lookup(30), lookup(31))
def scan(target):
checks = 0
for item in values:
checks += 1
if item == target:
return True, checks
return False, checks
print(scan(30), scan(31))
Résultat
(True, 4) (False, 4) (True, 16) (False, 16)
Trier et insérer dans une liste ont des coûts distincts.