База знанияИзпитен център
BGБългарски
Избери език13

CKTIS / Python

Производителност и сложност

Разглежда нарастването на работата с размера на входа независимо от измереното време.

Версия: Python 3.14; repository image, production runtime not attested

Синтаксис

bisect_left(sorted_values, target)

Разглежда нарастването на работата с размера на входа независимо от измереното време.

Обхождането може да прочете целия списък, а двоичното търсене в сортирани данни дели интервала наполовина и изисква логаритмичен брой сравнения. Индексът за вмъкване изисква още проверка на границата и равенството.

Сортирането и вмъкването в списък имат отделни разходи.

Примери

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))

Резултат

(True, 4) (False, 4)
(True, 16) (False, 16)

Сортирането и вмъкването в списък имат отделни разходи.

Източници