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

Дерево рекурсии - это схема, в которой каждый узел изображает вызов алгоритма, а его потомки - вызовы, сделанные из него. Такая схема помогает оценить время работы: вместо попытки сразу угадать ответ можно сложить цену всех вызовов сначала на одном уровне, затем на всех уровнях. Попробуйте изменить глубину дерева в калькуляторе: для выбранной модели он показывает стоимость каждого уровня и учитывает базовые случаи.
Что изображает дерево
Рассмотрим рекуррентное соотношение
Для простоты считаем, что , где - неотрицательное целое. Вызов размера создаёт два вызова размера и делает ещё единиц собственной работы: например, условной работы по обработке элементов. Вызов размера больше не ветвится и стоит одну единицу. Числа здесь задают учебную модель; реальное время конкретной программы зависит от реализации.
Корень представляет исходный вызов, два его ребёнка - две половины, а листья соответствуют базовому случаю. Ребро означает «вызвал», а не ссылку между элементами хранимой структуры. В отличие от дерева двоичного поиска, дерево рекурсии обычно служит моделью исполнения, а не контейнером данных.
Дерево не обязано явно существовать в памяти: мы рисуем его, чтобы перечислить вызовы. В обычной последовательной реализации одновременно активна лишь одна цепочка вызовов и связанные с ней данные; сумма работ всех узлов и максимальный размер стека - разные величины.
Пример: четыре уровня при n = 8
На нулевом уровне есть один вызов размера , его собственная работа равна . Следующий уровень состоит из двух вызовов размера : их работа равна . Затем идут четыре вызова размера , снова дающие . Наконец, восемь листьев размера стоят по единице, вместе .
| Уровень | Вызовов | Размер вызова | Работа уровня |
|---|---|---|---|
| 0 | 1 | 8 | 8 |
| 1 | 2 | 4 | 8 |
| 2 | 4 | 2 | 8 |
| 3 | 8 | 1 | 8 |

Итог равен . Та же проверка непосредственной подстановкой: , , . Важно не прибавлять к узлу полное значение и одновременно считать его потомков: их работа уже входит в . На схеме мы складываем только собственную работу каждого узла.
Как вывести общую формулу
На уровне число вызовов равно , а размер каждого - . Пока дерево полное, произведение даёт стоимость уровня:
Деление прекращается при , то есть при . Нумерация начинается с нуля, поэтому вместе с листьями уровней , хотя глубина дерева в рёбрах равна . В нашей модели листья тоже дают суммарно : их , каждый стоит . Отсюда точное равенство
Здесь описывает порядок роста, а не точное число секунд. Формула точна только для указанных стоимостей и размеров. Если базовый вызов стоит другую положительную константу, сумма листьев изменится, но порядок останется прежним. Это полезный мост к общей теме временной и пространственной сложности: сначала определяем, что считаем операцией, затем устанавливаем зависимость от входа.
Алгоритм построения дерева
- Выпишите базу и размеры подзадач. Из соотношения определите число потомков каждого вызова и условие остановки. Без базы нельзя понять глубину и стоимость листьев.
- Отделите собственную работу. В слагаемое относится к текущему узлу; два слагаемых представляют его поддеревья.
- Найдите закономерность уровня. Подсчитайте число узлов, размер подзадачи в каждом и произведение этих величин, если узлы одинаковы.
- Определите границы суммы. Выясните, когда размер достигнет базы, и включите стоимость листьев. При неравномерном разбиении одной общей глубины может не быть.
- Сложите уровни и проверьте вывод. Несколько первых значений полезно сверить подстановкой в исходную рекуррентную формулу. Для строгого доказательства общей оценки при необходимости примените индукцию.
Этот порядок подходит не только к бинарному дереву. Число ветвей, размеры подзадач и стоимость узла могут быть другими. Изменив хотя бы один из этих параметров, заново посчитайте ряд уровней: схожая картинка сама по себе не гарантирует одинаковую сложность.
Число вызовов и сумма работы
Для основного примера можно отдельно посчитать и количество узлов. На уровнях стоят вызовов. Их сумма равна . При это 15 вызовов: семь внутренних и восемь базовых. Но 15 - не ответ на вопрос о работе в нашей модели: разные вызовы выполняют разный объём действий. В корне стоимость равна восьми, а в листе - единице, поэтому сумма равна 32.
Различие особенно полезно, когда в условии сказано «сколько раз вызывается функция», а не «сколько операций она выполняет». Для первого вопроса можно дать каждому узлу вес один. Для второго вес нужно выбирать по телу функции: обработка массива, копирование и соединение результатов могут стоить больше одной операции. Если счётчик внутри функции увеличивается один раз при входе, его итог совпадёт с числом узлов, но не обязательно со временем всей программы.
При последовательном обходе максимальная цепочка от корня до листа содержит активных вызовов. Если каждый кадр стека занимает постоянное место и дополнительная память не выделяется, стеку потребуется памяти при растущем . Для программы с массивами, копиями или другими структурами это лишь часть общей памяти: их размер и срок жизни необходимо проанализировать отдельно.
Когда преобладают корень или листья
Пусть для степеней двойки дана другая модель: , . На уровне собственная работа равна
Получается убывающая геометрическая сумма: уровни дают , , и так далее. Она меньше , а уже корень стоит , поэтому полная работа равна . Здесь верхние уровни определяют порядок.
Теперь возьмём с той же базой. На уровне работа равна и растёт к низу дерева. На глубине находится листьев. Геометрическая сумма ограничена постоянным множителем последнего уровня, поэтому вся работа составляет . Здесь листья и близкие к ним уровни задают порядок. Сравнение трёх примеров показывает, зачем считать стоимость уровня, а не только глубину.
Где модель требует осторожности
Для сортировки слиянием деление на две части и слияние с линейной стоимостью приводят к форме, похожей на основной пример. Но детали выделения памяти и округления размеров влияют на конкретную реализацию: см. сложность сортировки слиянием. При произвольном целом половины могут иметь размеры и ; точная формула для степеней двойки тогда не переносится без изменения, хотя порядок типичной модели остаётся .
Разбиение может быть и сильно неравным. Например, порождает ветви разной глубины; условно считаем округление до целых и останавливаемся на малых размерах. Суммарный размер подзадач на полностью развёрнутом уровне равен , но часть ветвей достигает базы раньше. Поэтому нельзя просто считать все уровни одинаково заполненными. В худшем случае быстрой сортировки дерево вырождается почти в цепочку, и это меняет сумму работ.
Повторяющиеся аргументы тоже требуют внимания. Обычное дерево вызовов учитывает повторные вычисления отдельно. Если алгоритм запоминает результаты, одинаковые подзадачи могут вычисляться лишь один раз: тогда анализировать нужно фактическую реализацию с кешем, а не дерево наивной рекурсии. Наконец, суммарная работа дерева описывает последовательный подсчёт; при параллельном исполнении время зависит ещё от критического пути и доступных процессоров.
Частые ошибки
- Считать полную стоимость поддерева работой одного узла. Это повторно учитывает потомков. Оставляйте в узле только работу вне рекурсивных вызовов.
- Забывать листья. Базовый случай тоже может стоить ненулевое время; в основном примере листья добавляют целый уровень стоимостью .
- Путать глубину и число уровней. При глубине уровни с номерами от до дают строк суммы.
- Приписывать дереву сложность памяти. Число всех вызовов не равно максимальному числу одновременно активных вызовов; учитывайте стек и выделенные данные отдельно.
- Игнорировать условия модели. Степени двойки, округление, базовый случай и кеширование способны изменить точный подсчёт.
FAQ
Дерево рекурсии и стек вызовов - одно и то же?
Нет. Дерево описывает все вызовы за выполнение, а стек последовательной программы в конкретный момент содержит активную цепочку вызовов. Дерево помогает считать суммарную работу, стек - глубину вложенности и часть расхода памяти.
Всегда ли работа на каждом уровне одинакова?
Нет. Это свойство примера . При квадратичной работе узла уровни убывают, а при трёх подзадачах размера и линейной работе возрастают. Нужно вывести стоимость уровня из конкретной формулы.
Достаточно ли рисунка для доказательства сложности?
Рисунок помогает найти формулу и увидеть предположения, но сам по себе не доказывает оценку для всех размеров. Запишите границы суммы, оцените её и, если необходимо, подтвердите вывод индукцией, особенно при округлении и неравных ветвях.
Коротко
Дерево рекурсии раскладывает работу рекурсивного алгоритма по вызовам и уровням. Для при и каждый из уровней стоит , поэтому точная сумма равна , а порядок роста - . Для другой рекурсии сначала заново определите ветвление, собственную работу и стоимость листьев.
Читайте также

Сортировка слиянием: сложность по времени и памяти
Разбираем сложность сортировки слиянием: вывод O(n log n), число сравнений на примере, расход дополнительной памяти и условия устойчивости алгоритма при равных ключах.

Временная и пространственная сложность алгоритма
Временная и пространственная сложность алгоритма простыми словами: как считать операции и дополнительную память, понимать O и сравнивать решения на примерах.

Числа Люка: формула, примеры и связь с Фибоначчи
Числа Люка начинаются с 2 и 1 и строятся сложением двух предыдущих членов. Разбираем формулу, связь с числами Фибоначчи, примеры и алгоритм вычисления.

Формула Бине: вывод и вычисление чисел Фибоначчи
Разбираем формулу Бине для чисел Фибоначчи: подробный вывод через корни характеристического уравнения, пример вычисления, округление и ограничения точности в программе.

Ханойские башни и рекурсия: решение по шагам
Ханойские башни и рекурсия: разберём правила, семь ходов для трёх дисков, рекурсивный алгоритм, доказательство минимального числа ходов и его сложность.

Обходы двоичного дерева: порядки и примеры
Обходы двоичного дерева на одном примере: прямой, симметричный, обратный и по уровням. Как работают рекурсия, стек и очередь, какие результаты и сложность.