Дерево рекурсии: сложить по уровням

Если умеешь построить дерево рекурсии, посчитать цену уровня и число уровней и сложить - листай до «Теперь сам».

Как думаешь, во что сложится

T(n) = 2·T(n/2) + n. Наверху корень делает n работы и вызывает две T(n/2). Каждая из них делает n/2 работы - вместе снова n. Их четыре внука по n/4 - опять n. На каждом уровне сумма работы одна и та же, n. Значит весь ответ - это n, умноженное на число уровней. Осталось сосчитать уровни.

На что это похоже

Это разворот долговых расписок по слоям. Верхняя расписка - n наличными плюс две поменьше. Разворачиваешь их - получаешь слой из двух расписок, в сумме опять n. И так вниз, слой за слоем, пока расписки не станут по одному элементу. Общий долг - это сумма по слоям, а не по отдельным распискам: складывать удобнее горизонталь, а не вертикаль.

Механизм: построить, посчитать уровень, сложить

Узел дерева - работа одного вызова БЕЗ вложенных (для T(n/2) это n/2); потомки - вызовы, которые он порождает. На уровне i вниз от корня вызовов 2ⁱ, каждый размера n/2ⁱ, работы у каждого n/2ⁱ - вместе 2ⁱ·(n/2ⁱ) = n. Уровень стоит n независимо от глубины. Уровней log₂ n + 1: корень (уровень 0) и ещё log₂ n уровней, пока размер не дойдёт от n до 1. Итог: n на каждый из log₂ n + 1 уровней - Θ(n·log n).

Правило

Дерево рекурсии: узел - работа вызова без вложенных, потомки - его вызовы. Цена уровня - сумма работы всех его узлов; ответ - сумма цен по всем уровням. Считать надо две вещи: сколько стоит уровень и сколько уровней.

Разбор: почему уровней именно log n, а не n

У 2·T(n/2) вход на каждом уровне делится пополам: n → n/2 → n/4 → ... → 1. Число делений пополам до единицы - это log₂ n (из главы про суммы). Если бы вход убывал вычитанием при ОДНОМ вызове, T(n-1)+n, уровней было бы n, дерево - цепочка, и та же линейная работа на уровне дала бы n·n = n² вместо n·log n. А если вызовов ДВА, 2·T(n-1)+n, то на каждом из n уровней число узлов ещё и удваивается - это уже экспонента. И там, и там корень зла один: уровней n (вычитание), а не log n (деление). Число уровней задаёт, как быстро убывает вход, а не сколько работы на каждом.

Разбор: когда решает не уровень, а верх или низ

Цена уровня не всегда постоянна - тогда смотрят, какой конец перевешивает.

• T(n) = 2·T(n/2) + n²: уровень i стоит 2ⁱ·(n/2ⁱ)² = n²/2ⁱ - убывает вниз. Верхний уровень n² больше всех остальных вместе (геометрический ряд), ответ Θ(n²). Решает КОРЕНЬ.
• T(n) = 2·T(n/2) + 1: уровень i стоит 2ⁱ·1 = 2ⁱ - растёт вниз. Нижний уровень (листья, их n) больше всех, ответ Θ(n). Решают ЛИСТЬЯ.
• T(n) = 2·T(n/2) + n: уровень стоит n всегда - ни верх, ни низ, решает ЧИСЛО уровней, ответ Θ(n·log n).

Три случая - постоянный, убывающий и растущий по уровням - и есть три случая главной теоремы из следующей главы.

Разбор: посчитаем на числах

Проверим рассуждение на n = 8, где всё можно сложить руками:

уровень 0:  1 вызов × 8   = 8
уровень 1:  2 вызова × 4  = 8
уровень 2:  4 вызова × 2  = 8
уровень 3:  8 листьев × 1 = 8
итого: 8 на каждый из 4 уровней = 32

Делений пополам от 8 до 1 ровно log₂ 8 = 3, плюс уровень листьев - четыре строки, и каждая стоит n = 8. Итог 8 · 4 = 32. Формула n·log₂ n при n = 8 даёт 8 · 3 = 24, плюс 8 в листьях - те же 32. Числа сошлись с рассуждением «каждый уровень по n»: удвоение числа вызовов и деление работы вдвое гасят друг друга, и вся зависимость от n внутри уровня исчезает.

Что ломается без этого

Две ошибки счёта. Спутать число уровней: у деления это log n, а не n, - и наоборот. И забыть про листья: у 2·T(n/2)+1 вся цена как раз в листьях, и если считать только внутренние уровни, получишь Θ(log n) вместо верного Θ(n). Уровень листьев - полноправная строка суммы, а часто и главная.

Зачем это в работе

Дерево - первый инструмент к незнакомой рекуррентности: нарисовал, увидел цену уровня и число уровней, сложил - и порядок в руках, без формул. CLRS так и советует: дерево удобно, чтобы УГАДАТЬ ответ, а строгое доказательство даёт подстановка (следующий урок). Для быстрой прикидки на код-ревью «во что обойдётся эта рекурсия» дерева хватает.

Теперь сам

Реши деревом: T(n) = T(n/2) + n (один вызов на половине плюс линейная работа).