KennisbankExamencentrum
NL · NLNederlands (Nederland)
Taal kiezen13

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.

Bronnen