Функция считает, сколько штрихкодов из списка queries есть в отсортированном каталоге catalog. Оба списка длины n. Определите время выполнения в худшем случае.
Бинарный поиск в цикле
Код
def count_known(queries: list[int], catalog: list[int]) -> int:
found = 0
for q in queries:
low, high = 0, len(catalog) - 1
while low <= high:
mid = (low + high) // 2
if catalog[mid] == q:
found += 1
break
if catalog[mid] < q:
low = mid + 1
else:
high = mid - 1
return foundКакое время выполнения?
Ответ: O(n log n)
Для каждого из n запросов выполняется бинарный поиск: в худшем случае это log n шагов. Внутренний цикл вложен во внешний, поэтому время перемножается: O(n × log n). Если бы вместо бинарного поиска был простой просмотр списка, получилось бы O(n²).
- Подсказка 1
Внешний цикл выполняется n раз. Сколько шагов делает внутренний while в худшем случае?
- Подсказка 2
Когда циклы вложены, их время перемножается.