Функция находит разброс цен: разницу между самой высокой и самой низкой. Для этого она дважды проходит по списку. Определите время её выполнения, где n — длина списка.
Два прохода по ценам
Код
def price_range(prices: list[int]) -> int:
lowest = prices[0]
for p in prices:
if p < lowest:
lowest = p
highest = prices[0]
for p in prices:
if p > highest:
highest = p
return highest - lowestКакое время выполнения?
Ответ: O(n)
Циклы идут друг за другом, а не один внутри другого. Всего получается n + n = 2n шагов. Константы в «O-большом» отбрасываются, поэтому O(2n) — то же самое, что O(n), и так не пишут. O(n²) было бы, если бы второй цикл был вложен в первый.
- Подсказка 1
Сколько раз выполняется тело каждого цикла?
- Подсказка 2
Константы в «O-большом» не записываются. Чем тогда O(2n) отличается от O(n)?