2.1.2 — как оценить сложность рекурсии, не разворачивая её вручную2.1.2 — estimating recursion's complexity without unrolling it by hand
Рекурсивный алгоритм описывается уравнением T(n) = a·T(n/b) + f(n) — но само уравнение не говорит, чему равно T(n) в терминах n. Здесь: дерево рекурсии как способ увидеть структуру задачи, метод подстановки как строгое доказательство, и Master Theorem как готовый рецепт для самого частого случая.A recursive algorithm is described by an equation T(n) = a·T(n/b) + f(n) — but the equation itself doesn't say what T(n) equals in terms of n. Here: recursion trees as a way to see the problem's structure, the substitution method as a rigorous proof, and the Master Theorem as a ready-made recipe for the most common case.
Когда алгоритм решает задачу размера n, разбивая её на a подзадач размера n/b каждая, а затем тратит f(n) времени на то, чтобы разбить исходную задачу и объединить результаты подзадач, время его работы описывается уравнением T(n) = a·T(n/b) + f(n). Это и есть рекуррентное соотношение (recurrence relation) — определение функции через саму себя на меньшем аргументе. Асимптотика (2.1.1) описывает готовую функцию T(n); рекуррентность — это шаг раньше: как из структуры рекурсии эту функцию вообще получить.When an algorithm solves a problem of size n by splitting it into a subproblems of size n/b each, then spends f(n) time splitting the original problem and combining the subproblems' results, its running time is described by T(n) = a·T(n/b) + f(n). This is a recurrence relation — a function defined in terms of itself on a smaller argument. Asymptotics (2.1.1) describes a ready-made function T(n); a recurrence is one step earlier: how to actually derive that function from the recursion's structure.
a, b и f(n) — три параметра, которые полностью определяют форму рекурсии и, следовательно, её асимптотикуa, b, and f(n) — three parameters that fully determine the recursion's shape and hence its asymptotics
Классический пример — merge sort (2.2.1): массив размера n делится на a=2 половины размера n/2 (значит b=2), а слияние двух отсортированных половин стоит f(n) = O(n). Получаем T(n) = 2T(n/2) + O(n) — и вопрос "чему равно T(n)" превращается в вопрос "как решить это уравнение".The classic example is merge sort (2.2.1): an array of size n is split into a=2 halves of size n/2 (so b=2), and merging two sorted halves costs f(n) = O(n). This gives T(n) = 2T(n/2) + O(n) — and "what does T(n) equal" becomes "how do you solve this equation."
Дерево рекурсии — это способ визуализировать рекуррентность: корень — исходный вызов T(n), у него a детей, каждый — вызов T(n/b), и так далее, пока размер подзадачи не станет базовым случаем (обычно T(1) = O(1)). Стоимость f(n) записывается в каждом узле отдельно от рекурсивного вызова — она отражает работу, сделанную на этом уровне, а не переданную дальше вглубь. Суммируя стоимость f по всем узлам каждого уровня, а затем складывая уровни — получаем T(n) без всякой алгебры, просто подсчётом.A recursion tree is a way to visualize the recurrence: the root is the original call T(n), it has a children, each a call to T(n/b), and so on until the subproblem size hits the base case (usually T(1) = O(1)). The cost f(n) is recorded at each node separately from the recursive call — it reflects the work done at that level, not passed further down. Summing f's cost across every node of each level, then adding up the levels, gives T(n) with no algebra at all, just counting.
T(n) = 2T(n/2) + O(n): на каждом уровне суммарная работа остаётся n, а уровней ровно log₂nT(n) = 2T(n/2) + O(n): total work per level stays n, and there are exactly log₂n levels
Дерево рекурсии особенно полезно, когда a, b или f(n) не подходят под условия Master Theorem (см. ниже) — оно всегда работает, просто требует аккуратного суммирования по уровням, часто через геометрическую прогрессию.A recursion tree is especially useful when a, b, or f(n) don't fit the Master Theorem's conditions (see below) — it always works, it just requires careful summation across levels, often via a geometric series.
Дерево рекурсии даёт догадку о том, чему равно T(n), но не строгое доказательство. Метод подстановки закрывает этот пробел: сначала угадывается форма ответа (обычно по дереву рекурсии), затем доказывается индукцией по n, что T(n) действительно удовлетворяет этой оценке.A recursion tree gives a guess for what T(n) equals, but not a rigorous proof. The substitution method closes that gap: first guess the answer's form (usually from the recursion tree), then prove by induction on n that T(n) actually satisfies that bound.
Для T(n) = 2T(n/2) + n дерево рекурсии подсказывает O(n log n). Гипотеза для доказательства: T(n) ≤ c·n·log₂n для некоторой константы c > 0 и всех n ≥ n₀.For T(n) = 2T(n/2) + n, the recursion tree suggests O(n log n). The hypothesis to prove: T(n) ≤ c·n·log₂n for some constant c > 0 and all n ≥ n₀.
Предполагаем, что гипотеза верна для всех значений меньше n — в частности, для n/2: T(n/2) ≤ c·(n/2)·log₂(n/2).Assume the hypothesis holds for all values smaller than n — in particular, for n/2: T(n/2) ≤ c·(n/2)·log₂(n/2).
T(n) = 2T(n/2) + n ≤ 2·c·(n/2)·log₂(n/2) + n = c·n·(log₂n − 1) + n = c·n·log₂n − c·n + n.T(n) = 2T(n/2) + n ≤ 2·c·(n/2)·log₂(n/2) + n = c·n·(log₂n − 1) + n = c·n·log₂n − c·n + n.
c·n·log₂n − c·n + n ≤ c·n·log₂n верно ровно тогда, когда −c·n + n ≤ 0, то есть c ≥ 1. Выбрав c = 1 (и проверив базовый случай отдельно), гипотеза T(n) ≤ n·log₂n доказана индукцией — значит T(n) = O(n log n).c·n·log₂n − c·n + n ≤ c·n·log₂n holds exactly when −c·n + n ≤ 0, i.e. c ≥ 1. Choosing c = 1 (and checking the base case separately), the hypothesis T(n) ≤ n·log₂n is proven by induction — so T(n) = O(n log n).
Ключевая тонкость метода: индуктивное предположение используется для меньшего аргумента (n/2), а не для n — именно поэтому это математическая индукция, а не порочный круг. Частая ошибка новичков — угадать слишком слабую форму (например, T(n) ≤ c·n вместо c·n·log₂n для этой рекуррентности) и обнаружить, что подстановка не позволяет подобрать константу — это сигнал, что исходная гипотеза неверна, а не что метод не работает.The method's key subtlety: the inductive hypothesis is used for a smaller argument (n/2), not for n itself — that's exactly why this is mathematical induction, not circular reasoning. A common beginner mistake is guessing too weak a form (e.g. T(n) ≤ c·n instead of c·n·log₂n for this recurrence) and finding that no constant closes the substitution — that's a signal the original guess is wrong, not that the method is broken.
И дерево рекурсии, и метод подстановки работают для любой рекуррентности, но требуют ручной работы каждый раз. Master Theorem — это готовый рецепт для рекуррентностей вида T(n) = a·T(n/b) + f(n) (a ≥ 1, b > 1), который сравнивает f(n) с n^(log_b a) — "стоимостью работы на листьях дерева" — и по результату сравнения сразу даёт ответ, без построения дерева заново для каждой задачи.Both the recursion tree and the substitution method work for any recurrence, but require manual work each time. The Master Theorem is a ready-made recipe for recurrences of the form T(n) = a·T(n/b) + f(n) (a ≥ 1, b > 1) that compares f(n) against n^(log_b a) — "the cost of work at the tree's leaves" — and immediately gives the answer based on that comparison, with no need to rebuild the tree for every problem.
| случайcase | условиеcondition | T(n) | интуицияintuition |
|---|---|---|---|
| 1 | f(n) = O(n^(log_b a − ε)) | Θ(n^(log_b a)) | работа сосредоточена в листьях дереваwork is concentrated at the tree's leaves |
| 2 | f(n) = Θ(n^(log_b a)) | Θ(n^(log_b a) · log n) | работа равномерно распределена по всем уровнямwork is evenly spread across all levels |
| 3 | f(n) = Ω(n^(log_b a + ε)), регулярность+ regularity | Θ(f(n)) | работа сосредоточена в корне дереваwork is concentrated at the tree's root |
Условие "регулярности" в случае 3: a·f(n/b) ≤ c·f(n) для некоторой константы c < 1 и достаточно больших n — технически нужное условие, чтобы f(n) действительно доминировала, а не просто была больше n^(log_b a) в отдельных точках. На практике для полиномиальных и полиномиально-логарифмических f(n) (то есть почти всегда на собеседовании) это условие выполняется автоматически.The "regularity" condition in case 3: a·f(n/b) ≤ c·f(n) for some constant c < 1 and sufficiently large n — a technical requirement ensuring f(n) truly dominates, not just exceeds n^(log_b a) at isolated points. In practice, for polynomial and polylogarithmic f(n) (i.e. almost always in interviews) this condition holds automatically.
// merge sort: T(n) = 2T(n/2) + O(n)// merge sort: T(n) = 2T(n/2) + O(n)
// a=2, b=2 → n^(log_b a) = n^1 = n
// f(n) = n = Θ(n) → случай 2 → T(n) = Θ(n log n)// f(n) = n = Θ(n) → case 2 → T(n) = Θ(n log n)
// бинарный поиск: T(n) = T(n/2) + O(1)// binary search: T(n) = T(n/2) + O(1)
// a=1, b=2 → n^(log_b a) = n^0 = 1
// f(n) = O(1) = Θ(1) → случай 2 → T(n) = Θ(log n)// f(n) = O(1) = Θ(1) → case 2 → T(n) = Θ(log n)
// алгоритм Штрассена (2.4.1): T(n) = 7T(n/2) + O(n²)// Strassen's algorithm (2.4.1): T(n) = 7T(n/2) + O(n²)
// a=7, b=2 → n^(log_b a) = n^(log₂7) ≈ n^2.807
// f(n) = n² = O(n^(2.807-ε)) → случай 1 → T(n) = Θ(n^log₂7)// f(n) = n² = O(n^(2.807-ε)) → case 1 → T(n) = Θ(n^log₂7)Master Theorem не покрывает всё: он молчит, если f(n) больше n^(log_b a), но не полиномиально больше (например, f(n) = n^(log_b a) / log n), или если a или b не константы, или если подзадачи разного размера (T(n) = T(n/3) + T(2n/3) + n — как в partition для quicksort, разобранном в 2.2.1). В этих случаях единственный путь — обратно к дереву рекурсии или методу подстановки.The Master Theorem doesn't cover everything: it stays silent if f(n) exceeds n^(log_b a) but not polynomially (e.g. f(n) = n^(log_b a) / log n), or if a or b aren't constants, or if subproblems have different sizes (T(n) = T(n/3) + T(2n/3) + n — as in quicksort's partition, covered in 2.2.1). In those cases the only path is back to the recursion tree or the substitution method.
libstdc++ реализует stable_sort через merge sort именно потому, что гарантия Θ(n log n) из Master Theorem держится независимо от входных данных — в отличие от quicksort, чей худший случай O(n²) недопустим там, где стабильность и предсказуемость важнее средней скорости.libstdc++ implements stable_sort via merge sort precisely because the Θ(n log n) guarantee from the Master Theorem holds regardless of input — unlike quicksort, whose O(n²) worst case is unacceptable where stability and predictability matter more than average speed.
RSA и другие алгоритмы на больших числах используют T(n) = T(n/2) + O(1) для возведения в степень (быстрое возведение в степень квадрированием) — Master Theorem даёт Θ(log n) умножений вместо Θ(n) для наивного цикла, что при показателях степени в сотни бит — разница на порядки.RSA and other big-number algorithms use T(n) = T(n/2) + O(1) for exponentiation (fast exponentiation by squaring) — the Master Theorem gives Θ(log n) multiplications instead of Θ(n) for a naive loop, which at exponents hundreds of bits long is an order-of-magnitude difference.
Θ(n^log₂7) ≈ Θ(n^2.807) вместо наивных Θ(n³) (2.4.1) — на практике константа у Штрассена больше, поэтому библиотеки вроде BLAS переключаются на него только для достаточно больших матриц, а для малых используют наивный алгоритм — тот же компромисс констант, что и в гибридных сортировках (2.1.1).Θ(n^log₂7) ≈ Θ(n^2.807) instead of the naive Θ(n³) (2.4.1) — in practice Strassen's constant is larger, so libraries like BLAS only switch to it for sufficiently large matrices and use the naive algorithm for small ones — the same constant-factor tradeoff as hybrid sorts (2.1.1).
Разделяй-и-властвуй решение (2.4.1) даёт T(n) = 2T(n/2) + O(n) — тот же вид, что у merge sort, но f(n)=O(n) здесь означает "проверить полосу шириной 2δ вокруг разделяющей линии", а не "слить массивы"; Master Theorem одинаково применим, потому что зависит только от формы уравнения, а не от смысла операции.The divide-and-conquer solution (2.4.1) gives T(n) = 2T(n/2) + O(n) — the same shape as merge sort, but here f(n)=O(n) means "check the strip of width 2δ around the dividing line," not "merge arrays"; the Master Theorem applies identically because it depends only on the equation's shape, not the operation's meaning.
T(n) = 3T(n/2) + O(n) для умножения n-значных чисел (вместо школьного O(n²)): a=3, b=2 → n^(log₂3) ≈ n^1.585, f(n)=O(n) меньше этого — случай 1, T(n) = Θ(n^1.585). GMP и другие библиотеки произвольной точности переключаются на Karatsuba начиная с определённого размера операндов.T(n) = 3T(n/2) + O(n) for multiplying n-digit numbers (instead of schoolbook O(n²)): a=3, b=2 → n^(log₂3) ≈ n^1.585, f(n)=O(n) is smaller — case 1, T(n) = Θ(n^1.585). GMP and other arbitrary-precision libraries switch to Karatsuba past a certain operand size.
T(n) = T(n/3) + T(2n/3) + n (например, quicksort с несбалансированным разбиением 1:2) — Master Theorem неприменим напрямую, потому что подзадачи разного размера. Единственный корректный путь — дерево рекурсии, где нужно заметить, что глубина дерева от log₃n (по короткой ветке) до log_{3/2}n (по длинной), но сумма работы на каждом уровне всё равно O(n), что в итоге даёт O(n log n).T(n) = T(n/3) + T(2n/3) + n (e.g. quicksort with an unbalanced 1:2 split) — the Master Theorem doesn't apply directly because the subproblems differ in size. The only correct path is the recursion tree, where you must notice the tree's depth ranges from log₃n (along the short branch) to log_{3/2}n (along the long one), but the work per level is still O(n), which ultimately gives O(n log n).
f(n) = Ω(n^(log_b a + ε)) само по себе не гарантирует T(n) = Θ(f(n)) — нужна ещё регулярность a·f(n/b) ≤ c·f(n). Для "патологических" f(n) (например, f(n) = n^(log_b a)·2^n, растущей быстрее любого полинома) условие регулярности может не выполняться, и Master Theorem в этой форме неприменим, хотя формально f(n) больше листовой стоимости.f(n) = Ω(n^(log_b a + ε)) alone does not guarantee T(n) = Θ(f(n)) — regularity a·f(n/b) ≤ c·f(n) is also required. For "pathological" f(n) (e.g. f(n) = n^(log_b a)·2^n, growing faster than any polynomial), the regularity condition can fail, and the Master Theorem in this form doesn't apply even though f(n) formally exceeds the leaf cost.
n^(log_b a) — это n в степени (log_b a), не логарифм от чего-либо; для T(n)=4T(n/2)+n это n² (log₂4=2), а не что-то с логарифмом снаружи. Перепутать основание степени с основанием логарифма — частая арифметическая ошибка, дающая неверный ответ даже при верном выборе случая.n^(log_b a) is n raised to the power (log_b a), not a logarithm of anything; for T(n)=4T(n/2)+n this is n² (log₂4=2), not something with an outer logarithm. Mixing up the exponent's base with the logarithm's base is a common arithmetic slip that gives a wrong answer even when the right case is chosen.