CKTIS / Python
Leistung und Komplexität
Untersucht das Wachstum der Arbeit mit der Eingabegröße unabhängig von der gemessenen Zeit.
Version: Python 3.14; repository image, production runtime not attested
Syntax
bisect_left(sorted_values, target)Untersucht das Wachstum der Arbeit mit der Eingabegröße unabhängig von der gemessenen Zeit.
Ein Scan kann die ganze Liste lesen, die Binärsuche auf sortierten Daten halbiert den Bereich und braucht logarithmisch viele Vergleiche. Ein Einfügeindex erfordert noch Grenz- und Gleichheitsprüfung.
Sortieren und Einfügen in eine Liste verursachen eigene Kosten.
Beispiele
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))
Ergebnis
(True, 4) (False, 4) (True, 16) (False, 16)
Sortieren und Einfügen in eine Liste verursachen eigene Kosten.