Функция считает морозные дни (температура ниже нуля) методом «разделяй и властвуй»: делит отрезок пополам и складывает ответы половин. Вызов для всего списка: frosty_days(temps, 0, len(temps) - 1). Определите время выполнения, где n — длина списка.
Пополам и ещё раз пополам
Код
def frosty_days(temps: list[int], low: int, high: int) -> int:
if low > high:
return 0
if low == high:
return 1 if temps[low] < 0 else 0
mid = (low + high) // 2
return frosty_days(temps, low, mid) + frosty_days(temps, mid + 1, high)Какое время выполнения?
Ответ: O(n)
Функция идёт в обе половины, а не в одну, как бинарный поиск. В дереве вызовов n листьев (по одному на элемент) и меньше n внутренних узлов — всего около 2n вызовов. Каждый вызов делает O(1) работы: срезов нет, передаются только индексы. Итого O(n). O(n log n) получилось бы, если бы каждый уровень делал O(n) работы — например, копировал срезы или сливал половины, как сортировка слиянием.
- Подсказка 1
Деление пополам ещё не означает O(log n). Важно, сколько вызовов получится всего.
- Подсказка 2
Нарисуйте дерево вызовов для n = 8. Сколько в нём листьев и сколько узлов всего?