WissensdatenbankPrüfungszentrum
DEDeutsch
Sprache wählen13

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.

Quellen