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.