EssayAI
Блог
Блог
Естественные науки

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

8 ноября 2026Время чтения: 8 минут
#дерево рекурсии#рекуррентные соотношения#сложность алгоритмов#анализ алгоритмов#рекурсия
Дерево рекурсии: как посчитать сложность по уровням

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

Что изображает дерево

Рассмотрим рекуррентное соотношение

T(n)=2T(n/2)+n,T(1)=1.T(n)=2T(n/2)+n,\qquad T(1)=1.

Для простоты считаем, что n=2kn=2^k, где kk - неотрицательное целое. Вызов размера n>1n>1 создаёт два вызова размера n/2n/2 и делает ещё nn единиц собственной работы: например, условной работы по обработке элементов. Вызов размера 11 больше не ветвится и стоит одну единицу. Числа здесь задают учебную модель; реальное время конкретной программы зависит от реализации.

Корень представляет исходный вызов, два его ребёнка - две половины, а листья соответствуют базовому случаю. Ребро означает «вызвал», а не ссылку между элементами хранимой структуры. В отличие от дерева двоичного поиска, дерево рекурсии обычно служит моделью исполнения, а не контейнером данных.

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

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

Пример: четыре уровня при n = 8

На нулевом уровне есть один вызов размера 88, его собственная работа равна 88. Следующий уровень состоит из двух вызовов размера 44: их работа равна 2⋅4=82\cdot4=8. Затем идут четыре вызова размера 22, снова дающие 88. Наконец, восемь листьев размера 11 стоят по единице, вместе 88.

Уровень iiВызововРазмер вызоваРабота уровня
0188
1248
2428
3818
Дерево для n равно 8: четыре уровня дают по 8 единиц работы и в сумме 32
Дерево для n равно 8: четыре уровня дают по 8 единиц работы и в сумме 32

Итог равен 8+8+8+8=328+8+8+8=32. Та же проверка непосредственной подстановкой: T(2)=4T(2)=4, T(4)=12T(4)=12, T(8)=32T(8)=32. Важно не прибавлять к узлу полное значение T(4)T(4) и одновременно считать его потомков: их работа уже входит в T(4)T(4). На схеме мы складываем только собственную работу каждого узла.

Как вывести общую формулу

На уровне ii число вызовов равно 2i2^i, а размер каждого - n/2in/2^i. Пока дерево полное, произведение даёт стоимость уровня:

2i⋅n2i=n.2^i\cdot\frac{n}{2^i}=n.

Деление прекращается при n/2i=1n/2^i=1, то есть при i=log⁡2n=ki=\log_2 n=k. Нумерация начинается с нуля, поэтому вместе с листьями уровней k+1k+1, хотя глубина дерева в рёбрах равна kk. В нашей модели листья тоже дают суммарно nn: их nn, каждый стоит 11. Отсюда точное равенство

T(n)=n(log⁡2n+1)=Θ(nlog⁡n)при n=2k.T(n)=n(\log_2 n+1)=\Theta(n\log n)\quad\text{при }n=2^k.

Здесь Θ\Theta описывает порядок роста, а не точное число секунд. Формула точна только для указанных стоимостей и размеров. Если базовый вызов стоит другую положительную константу, сумма листьев изменится, но порядок останется прежним. Это полезный мост к общей теме временной и пространственной сложности: сначала определяем, что считаем операцией, затем устанавливаем зависимость от входа.

Алгоритм построения дерева

  1. Выпишите базу и размеры подзадач. Из соотношения определите число потомков каждого вызова и условие остановки. Без базы нельзя понять глубину и стоимость листьев.
  2. Отделите собственную работу. В 2T(n/2)+n2T(n/2)+n слагаемое nn относится к текущему узлу; два слагаемых T(n/2)T(n/2) представляют его поддеревья.
  3. Найдите закономерность уровня. Подсчитайте число узлов, размер подзадачи в каждом и произведение этих величин, если узлы одинаковы.
  4. Определите границы суммы. Выясните, когда размер достигнет базы, и включите стоимость листьев. При неравномерном разбиении одной общей глубины может не быть.
  5. Сложите уровни и проверьте вывод. Несколько первых значений полезно сверить подстановкой в исходную рекуррентную формулу. Для строгого доказательства общей оценки при необходимости примените индукцию.

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

Число вызовов и сумма работы

Для основного примера можно отдельно посчитать и количество узлов. На уровнях стоят 1,2,4,…,2k1, 2, 4, \ldots, 2^k вызовов. Их сумма равна 2k+1−1=2n−12^{k+1}-1=2n-1. При n=8n=8 это 15 вызовов: семь внутренних и восемь базовых. Но 15 - не ответ на вопрос о работе в нашей модели: разные вызовы выполняют разный объём действий. В корне стоимость равна восьми, а в листе - единице, поэтому сумма равна 32.

Различие особенно полезно, когда в условии сказано «сколько раз вызывается функция», а не «сколько операций она выполняет». Для первого вопроса можно дать каждому узлу вес один. Для второго вес нужно выбирать по телу функции: обработка массива, копирование и соединение результатов могут стоить больше одной операции. Если счётчик внутри функции увеличивается один раз при входе, его итог совпадёт с числом узлов, но не обязательно со временем всей программы.

При последовательном обходе максимальная цепочка от корня до листа содержит k+1k+1 активных вызовов. Если каждый кадр стека занимает постоянное место и дополнительная память не выделяется, стеку потребуется Θ(log⁡n)\Theta(\log n) памяти при растущем nn. Для программы с массивами, копиями или другими структурами это лишь часть общей памяти: их размер и срок жизни необходимо проанализировать отдельно.

Когда преобладают корень или листья

Пусть для степеней двойки дана другая модель: T(n)=2T(n/2)+n2T(n)=2T(n/2)+n^2, T(1)=1T(1)=1. На уровне ii собственная работа равна

2i(n2i)2=n22i.2^i\left(\frac{n}{2^i}\right)^2=\frac{n^2}{2^i}.

Получается убывающая геометрическая сумма: уровни дают n2n^2, n2/2n^2/2, n2/4n^2/4 и так далее. Она меньше 2n22n^2, а уже корень стоит n2n^2, поэтому полная работа равна Θ(n2)\Theta(n^2). Здесь верхние уровни определяют порядок.

Теперь возьмём T(n)=3T(n/2)+nT(n)=3T(n/2)+n с той же базой. На уровне ii работа равна n(3/2)in(3/2)^i и растёт к низу дерева. На глубине log⁡2n\log_2 n находится 3log⁡2n=nlog⁡233^{\log_2 n}=n^{\log_2 3} листьев. Геометрическая сумма ограничена постоянным множителем последнего уровня, поэтому вся работа составляет Θ(nlog⁡23)\Theta(n^{\log_2 3}). Здесь листья и близкие к ним уровни задают порядок. Сравнение трёх примеров показывает, зачем считать стоимость уровня, а не только глубину.

Где модель требует осторожности

Для сортировки слиянием деление на две части и слияние с линейной стоимостью приводят к форме, похожей на основной пример. Но детали выделения памяти и округления размеров влияют на конкретную реализацию: см. сложность сортировки слиянием. При произвольном целом nn половины могут иметь размеры ⌊n/2⌋\lfloor n/2\rfloor и ⌈n/2⌉\lceil n/2\rceil; точная формула для степеней двойки тогда не переносится без изменения, хотя порядок типичной модели остаётся Θ(nlog⁡n)\Theta(n\log n).

Разбиение может быть и сильно неравным. Например, T(n)=T(n/3)+T(2n/3)+nT(n)=T(n/3)+T(2n/3)+n порождает ветви разной глубины; условно считаем округление до целых и останавливаемся на малых размерах. Суммарный размер подзадач на полностью развёрнутом уровне равен nn, но часть ветвей достигает базы раньше. Поэтому нельзя просто считать все уровни одинаково заполненными. В худшем случае быстрой сортировки дерево вырождается почти в цепочку, и это меняет сумму работ.

Повторяющиеся аргументы тоже требуют внимания. Обычное дерево вызовов учитывает повторные вычисления отдельно. Если алгоритм запоминает результаты, одинаковые подзадачи могут вычисляться лишь один раз: тогда анализировать нужно фактическую реализацию с кешем, а не дерево наивной рекурсии. Наконец, суммарная работа дерева описывает последовательный подсчёт; при параллельном исполнении время зависит ещё от критического пути и доступных процессоров.

Частые ошибки

  • Считать полную стоимость поддерева работой одного узла. Это повторно учитывает потомков. Оставляйте в узле только работу вне рекурсивных вызовов.
  • Забывать листья. Базовый случай тоже может стоить ненулевое время; в основном примере листья добавляют целый уровень стоимостью nn.
  • Путать глубину и число уровней. При глубине kk уровни с номерами от 00 до kk дают k+1k+1 строк суммы.
  • Приписывать дереву сложность памяти. Число всех вызовов не равно максимальному числу одновременно активных вызовов; учитывайте стек и выделенные данные отдельно.
  • Игнорировать условия модели. Степени двойки, округление, базовый случай и кеширование способны изменить точный подсчёт.

FAQ

Дерево рекурсии и стек вызовов - одно и то же?

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

Всегда ли работа на каждом уровне одинакова?

Нет. Это свойство примера 2T(n/2)+n2T(n/2)+n. При квадратичной работе узла уровни убывают, а при трёх подзадачах размера n/2n/2 и линейной работе возрастают. Нужно вывести стоимость уровня из конкретной формулы.

Достаточно ли рисунка для доказательства сложности?

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

Коротко

Дерево рекурсии раскладывает работу рекурсивного алгоритма по вызовам и уровням. Для T(n)=2T(n/2)+nT(n)=2T(n/2)+n при T(1)=1T(1)=1 и n=2kn=2^k каждый из k+1k+1 уровней стоит nn, поэтому точная сумма равна n(k+1)n(k+1), а порядок роста - Θ(nlog⁡n)\Theta(n\log n). Для другой рекурсии сначала заново определите ветвление, собственную работу и стоимость листьев.

Доверьте текст нейросети EssayAI

Открыть EssayAI

Бесплатно, на русском языке и без VPN

Читайте также

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

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

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

8 ноября 20268 минут
Временная и пространственная сложность алгоритма

Временная и пространственная сложность алгоритма

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

8 ноября 20268 минут
Числа Люка: формула, примеры и связь с Фибоначчи

Числа Люка: формула, примеры и связь с Фибоначчи

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

8 ноября 20268 минут
Формула Бине: вывод и вычисление чисел Фибоначчи

Формула Бине: вывод и вычисление чисел Фибоначчи

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

8 ноября 20268 минут
Ханойские башни и рекурсия: решение по шагам

Ханойские башни и рекурсия: решение по шагам

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

8 ноября 20268 минут
Обходы двоичного дерева: порядки и примеры

Обходы двоичного дерева: порядки и примеры

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

8 ноября 20268 минут