Функция считает кирпичи в лестнице высотой n, где ступень номер k сложена из k кирпичей. Кирпичи ступени она «укладывает» по одному, а остальную лестницу считает рекурсивно. Определите время её выполнения в зависимости от n.
bricks(4) → 10: ступени из 4, 3, 2 и 1 кирпича.
def bricks(n: int) -> int:
if n == 0:
return 0
step = 0
for _ in range(n): # укладываем ступень из n кирпичей по одному
step += 1
return step + bricks(n - 1)Ответ: O(n²)
Вызовов n, но в вызове с аргументом k цикл делает k шагов. Всего n + (n − 1) + … + 1 = n(n + 1)/2 шагов. Это та же сумма, что у сортировки выбором в главе 2. Константа ½ в «O-большом» отбрасывается, остаётся O(n²). Ответ O(n) — частая ловушка: он был бы верным, если бы каждый вызов работал за O(1).
Рекурсивных вызовов n, но работа внутри каждого разная. Сколько шагов делает цикл в вызове с аргументом k?
Сложите работу всех вызовов: n + (n − 1) + … + 1. Где вы видели такую сумму в главе 2?