CKTIS / Python
Prestaties en complexiteit
Onderzoekt hoe het werk met de invoergrootte groeit, los van de gemeten duur.
Versie: Python 3.14; repository image, production runtime not attested
Syntax
bisect_left(sorted_values, target)Onderzoekt hoe het werk met de invoergrootte groeit, los van de gemeten duur.
Een scan kan de hele lijst lezen, terwijl binair zoeken in gesorteerde gegevens het interval halveert en een logaritmisch aantal vergelijkingen gebruikt. De invoegindex vereist nog een grens- en gelijkheidscontrole.
Sorteren en invoegen in de lijst kosten afzonderlijk werk.
Voorbeelden
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))
Resultaat
(True, 4) (False, 4) (True, 16) (False, 16)
Sorteren en invoegen in de lijst kosten afzonderlijk werk.