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)
Сортирането и вмъкването в списък имат отделни разходи.