Base de conocimientosCentro de exámenes
ESEspañol
Elegir idioma13

CKTIS / Python

Rendimiento y complejidad

Estudia cómo crece el trabajo con el tamaño de entrada independientemente del tiempo medido.

Versión: Python 3.14; repository image, production runtime not attested

Sintaxis

bisect_left(sorted_values, target)

Estudia cómo crece el trabajo con el tamaño de entrada independientemente del tiempo medido.

Un barrido puede leer toda la lista, mientras la búsqueda binaria en datos ordenados divide el intervalo por dos y usa comparaciones logarítmicas. El índice de inserción requiere comprobar el límite y la igualdad.

Ordenar e insertar en una lista tienen costes propios.

Ejemplos

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))

Resultado

(True, 4) (False, 4)
(True, 16) (False, 16)

Ordenar e insertar en una lista tienen costes propios.

Fuentes