Base de connaissancesCentre d’examen
FRFrançais
Choisir la langue13

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.

Sources