Асимптотические обозначения: определения, свойства и примеры

Доска 1 — определения O, Ω, Θ, o, ω и таблица соответствий со знаками сравнения

Доска 2 — примеры: 2n+5=O(n), n²/10=Ω(n), 500n=o(n²), 3ⁿ=ω(2ⁿ)

Сегодня мы начинаем осенний сезон курса: нас ждут асимптотика, мастер-теорема, теорема об экспоненциальных рекуррентных соотношениях и алгоритм Карацубы. Начнём с мотивирующего примера. Пусть есть код, который считает некоторую сумму в двух вложенных циклах длины nn:

s = 0
for i in range(n):
    for j in range(n):
        s += 1

Хочется понять, сколько времени этот код работает. Интуитивно цикл делает примерно n2n^2 итераций, и хочется сказать, что код работает «примерно за n2n^2». Однако точная формулировка окажется куда более неприятной: число действий программы может быть, например, 10n2+5n+710n^2 + 5n + 7, потому что одна итерация цикла способна занимать не одну операцию, а несколько. Оперировать такими громоздкими выражениями не хочется — хочется писать именно «примерно n2n^2». Но «примерно» — не очень конкретный значок, и мы сейчас познакомимся со специальной формалистикой, которая призвана этот «примерный квадрат» формализовать.

Перед этим ответим на вопрос: зачем вообще измерять, сколько времени работает программа? Ответ простой. Тактовая частота моего процессора составляет примерно 2,32{,}3 ГГц, то есть в распоряжении есть около 2,3⋅1092{,}3 \cdot 10^9 операций в секунду. Поставим задачу: при каком максимальном nn код, делающий примерно n2n^2 операций, успеет отработать за одну секунду? Нужно, чтобы n2≈2,3⋅109n^2 \approx 2{,}3 \cdot 10^9, то есть n≈2,3⋅109≈40 000n \approx \sqrt{2{,}3 \cdot 10^9} \approx 40\,000. Это вполне практичное знание.

Здесь есть один неприятный нюанс: оценка верна, только если вы действительно успеваете выполнять такое число операций. Для быстрого языка вроде C++ подобные прикидки работают достаточно неплохо. Но если язык медленный — например, Python, — то стоит считать, что в секунду выполняется порядка 10610^6 операций. Тогда максимальное nn для квадратичного кода составит примерно 10001000.

Чтобы формально записывать «примерно n2n^2», введём семейство обозначений. Пусть f,g ⁣:N→Z≥0f, g\colon \mathbb{N} \to \mathbb{Z}_{\ge 0} — функции из натуральных чисел в целые неотрицательные. Говорим, что f=O(g)f = O(g), если существуют константа C>0C > 0 и момент NN, такие что f(n)≤C⋅g(n)f(n) \le C \cdot g(n) для всех n≥Nn \ge N; иначе говоря, начиная с некоторого момента ff ограничена сверху константой, умноженной на gg. Говорим, что f=Ω(g)f = \Omega(g), если существуют C>0C > 0 и NN, такие что f(n)≥C⋅g(n)f(n) \ge C \cdot g(n) для всех n≥Nn \ge N — теперь ff прижата к gg снизу с какой-то константой. Наконец, Θ\Theta — комбинация этих двух обозначений: f=Θ(g)f = \Theta(g), если существуют константы c1,c2>0c_1, c_2 > 0 и момент NN, такие что c1⋅g(n)≤f(n)≤c2⋅g(n)c_1 \cdot g(n) \le f(n) \le c_2 \cdot g(n) для всех n≥Nn \ge N, то есть ff зажата между gg с двух сторон с какими-то константами.

Приведём парочку примеров. Во-первых, 2n+5=O(n)2n + 5 = O(n): достаточно взять C=3C = 3 и N=5N = 5, поскольку 2n+5≤3n2n + 5 \le 3n при всех n≥5n \ge 5. Во-вторых, 110n2=Ω(n)\tfrac{1}{10} n^2 = \Omega(n): выберем C=110C = \tfrac{1}{10}, и тогда 110n2≥110n\tfrac{1}{10} n^2 \ge \tfrac{1}{10} n при всех n≥1n \ge 1. Рассмотрим и пример с Θ\Theta: мы уже оценили 2n+52n + 5 сверху, оценим ещё и снизу. Это не более сложно: 2n≤2n+5≤3n2n \le 2n + 5 \le 3n при всех n≥5n \ge 5, так что c1=2c_1 = 2, c2=3c_2 = 3, а N=5N = 5, и значит 2n+5=Θ(n)2n + 5 = \Theta(n).

Мы познакомились с OO-большим, Ω\Omega-большим и Θ\Theta. В некотором смысле это операторы сравнения функций: про OO, Ω\Omega и Θ\Theta стоит думать как про ≤\le, ≥\ge и == соответственно — с точностью до константы. Смотрите: 2n+52n + 5 вряд ли «больше», чем nn, — с точностью до константы они действительно совпадают; а n2n^2 — «хотя бы» nn в том формализме, что мы определили. Но коль скоро существуют нестрогие знаки сравнения, должны существовать и строгие: oo-маленькое и ω\omega-маленькое, отвечающие знакам << и >>. Итого соответствие такое: O↔≤O \leftrightarrow \le, Ω↔≥\Omega \leftrightarrow \ge, Θ↔=\Theta \leftrightarrow =, o↔<o \leftrightarrow <, ω↔>\omega \leftrightarrow >.

Определим строгие сравнения. Говорим, что f=o(g)f = o(g), если для любой константы C>0C > 0 существует момент NN, такой что f(n)≤C⋅g(n)f(n) \le C \cdot g(n) для всех n≥Nn \ge N. Аналогично f=ω(g)f = \omega(g), если для любой константы C>0C > 0 существует момент NN, такой что f(n)≥C⋅g(n)f(n) \ge C \cdot g(n) для всех n≥Nn \ge N. Обратите внимание на порядок кванторов: в отличие от OO и Ω\Omega, здесь неравенство должно выполняться для любой константы, а не для какой-то одной.

Перед тем как двинуться дальше, переформулируем определение oo-маленького. Если переписать неравенство f(n)≤C⋅g(n)f(n) \le C \cdot g(n) в виде частного, получится, что f(n)g(n)≤C\frac{f(n)}{g(n)} \le C для любой константы CC с некоторого момента. Правда, стоит заметить одну маленькую вещь: в исходном определении функции ff и gg могут принимать нулевые значения, а переписанный вариант имеет смысл, только если gg никогда не обращается в ноль.

Как и в прошлый раз, посмотрим на парочку примеров. Пример первый: 500n=o(n2)500n = o(n^2), то есть 500n500n растёт существенно медленнее, чем n2n^2. Докажем это через определение с частным: нужно, чтобы 500nn2=500n≤C\frac{500n}{n^2} = \frac{500}{n} \le C для любой константы CC с некоторого момента. Для любой CC это неравенство можно просто решить: оно верно при всех n≥⌈500/C⌉n \ge \lceil 500 / C \rceil, а значит, по определению 500n=o(n2)500n = o(n^2). Пример второй: 3n=ω(2n)3^n = \omega(2^n), то есть 3n3^n растёт строго быстрее, чем 2n2^n. Действительно, частное 3n2n=1,5n\frac{3^n}{2^n} = 1{,}5^n должно быть хотя бы CC для любой константы CC с некоторого момента — и это выполнено при всех n≥⌈log⁡1,5C⌉n \ge \lceil \log_{1{,}5} C \rceil.

Зачем мы всё это вводим? Вспомните пример, где мы говорили, что функция работает «примерно за n2n^2». Теперь вместо расплывчатого «примерно» мы можем воспользоваться двумя точными утверждениями: сказать, что код работает не более чем за n2n^2 с точностью до константы, или что он работает в точности за n2n^2 с точностью до константы. То есть записать, что наш алгоритм работает за O(n2)O(n^2) или даже за Θ(n2)\Theta(n^2).

Сформулируем парочку свойств. Раз OO, Ω\Omega, Θ\Theta, oo и ω\omega — это в некотором смысле операторы сравнения, для них должны выполняться естественные свойства, и они действительно выполняются. Свойство первое: f=O(g)f = O(g) тогда и только тогда, когда g=Ω(f)g = \Omega(f) — действительно, «ff не больше gg» ровно когда «gg хотя бы ff»; аналогичный факт верен и для строгих знаков: f=o(g)f = o(g) тогда и только тогда, когда g=ω(f)g = \omega(f). Свойство второе — транзитивность: если f=O(g)f = O(g) и g=O(h)g = O(h), то f=O(h)f = O(h). Свойство третье: если f=Θ(g)f = \Theta(g), то g=Θ(f)g = \Theta(f). Свойство четвёртое: f=Θ(g)f = \Theta(g) тогда и только тогда, когда одновременно f=O(g)f = O(g) и f=Ω(g)f = \Omega(g). И пятое свойство: умножение функции на положительную константу сохраняет асимптотику — если C>0C > 0, то C⋅f=Θ(f)C \cdot f = \Theta(f). По аналогии можно сформулировать ещё парочку свойств, но нам этого будет достаточно.

Для иллюстрации докажем одно свойство — мне нравится второе, но все остальные тоже очень простые и доказываются по определению. Пусть f=O(g)f = O(g): это значит, что f(n)≤C1⋅g(n)f(n) \le C_1 \cdot g(n) для всех n≥N1n \ge N_1. Пусть также g=O(h)g = O(h): это значит, что g(n)≤C2⋅h(n)g(n) \le C_2 \cdot h(n) для всех n≥N2n \ge N_2. Из этого можно сделать прекрасный вывод: f(n)≤C1C2⋅h(n)f(n) \le C_1 C_2 \cdot h(n) для всех n≥max⁡(N1,N2)n \ge \max(N_1, N_2). Но это в точности определение OO-большого для утверждения f=O(h)f = O(h) — с константой C1C2C_1 C_2 и моментом max⁡(N1,N2)\max(N_1, N_2).

Прежде чем двинуться дальше, ещё парочка примеров того, как OO может встретиться в жизни. Первый пример — сумма гармонического ряда: ∑i=1n1i=ln⁡n+err(n)\sum_{i=1}^{n} \frac{1}{i} = \ln n + \mathrm{err}(n), где err(n)=O(1)\mathrm{err}(n) = O(1). Этот факт мы подробнее докажем на второй лекции, а пока поймём, что такая запись значит, — ведь напрямую вида «функция равна OO от чего-то» мы здесь не видим. Запись означает следующее: существует некоторая функция ошибки err(n)\mathrm{err}(n), которая равна O(1)O(1), и подстановка её в выражение превращает его в верное равенство.

Пример второй называется формулой Стирлинга. Она утверждает, что n!n! — это примерно 2πn⋅(ne)n\sqrt{2\pi n} \cdot \left(\frac{n}{e}\right)^n. Но слова «примерно» у нас нет, а точный факт формулируется так: n!=2πn⋅(ne)n⋅(1+O ⁣(1n))n! = \sqrt{2\pi n} \cdot \left(\frac{n}{e}\right)^n \cdot \left(1 + O\!\left(\frac{1}{n}\right)\right).

Ещё в жизни вам часто может встретиться запись O(log⁡n)O(\log n), причём в логарифме не указано основание. Когда основание не указано, обычно имеется в виду одно из двух: либо основание — двойка, либо основание не важно. В данном случае основание именно не важно, и вот почему. Факт: log⁡2n=Θ(log⁡5n)\log_2 n = \Theta(\log_5 n), поскольку log⁡2n=log⁡5n⋅log⁡25\log_2 n = \log_5 n \cdot \log_2 5 — то есть, говоря по-человечески, все логарифмы отличаются друг от друга в константу раз. А так как OO-большое «съедает» все константы, то основание логарифма можно и не писать.

И ещё парочка свойств. Утверждение: если к функции ff добавить или вычесть oo-маленькое от ff, то асимптотика не изменится — результат останется Θ(f)\Theta(f). Докажем. Обозначим эту добавку через gg: я знаю, что g=o(f)g = o(f), и хочу доказать, что f±g=Θ(f)f \pm g = \Theta(f). Подставим определение oo-маленького: g(n)≤C⋅f(n)g(n) \le C \cdot f(n) для любой константы CC с некоторого момента — и выберем конкретное значение, мне нравится C=0,1C = 0{,}1, то есть g(n)≤0,1⋅f(n)g(n) \le 0{,}1 \cdot f(n) при всех n≥Nn \ge N. Что это даёт? Получается, что 0,9⋅f(n)≤(f±g)(n)≤1,1⋅f(n)0{,}9 \cdot f(n) \le (f \pm g)(n) \le 1{,}1 \cdot f(n) для всех n≥Nn \ge N. А это по определению и значит, что f±g=Θ(f)f \pm g = \Theta(f): функция зажата между ff снизу и сверху с некоторыми константами, начиная с какого-то момента.

Следующее утверждение — про многочлены. Пусть есть многочлен p(x)=a0+a1x+⋯+anxnp(x) = a_0 + a_1 x + \dots + a_n x^n, причём старший коэффициент положителен: an>0a_n > 0 — так мы изучаем ситуацию, когда функция положительна. Утверждение: p(x)=Θ(xn)p(x) = \Theta(x^n), то есть многочлен асимптотически ведёт себя как свой старший член. Жизненный пример применения: 2x2−5x+3=Θ(x2)2x^2 - 5x + 3 = \Theta(x^2).

Почему же этот факт верен? Он прямо следует из предыдущего утверждения, если понять, что все мономы, кроме старшего, — это oo-маленькое от старшего. Докажем вспомогательную лемму: xk=o(xk+1)x^k = o(x^{k+1}). По определению с частным: xkxk+1=x−1\frac{x^k}{x^{k+1}} = x^{-1} должно быть ограничено любой константой CC — и действительно, x−1≤Cx^{-1} \le C при всех x≥1/Cx \ge 1/C; частный случай этого утверждения мы уже проделывали, когда сравнивали xx и x2x^2. Итак, коль скоро все мономы, кроме старшего, — oo-маленькое от старшего, их можно по предыдущему утверждению просто выкинуть, и асимптотика сохранится. Остаётся старший член anxna_n x^n, а мы уже обсуждали, что умножение на положительную константу сохраняет асимптотику: C⋅f=Θ(f)C \cdot f = \Theta(f).

Теперь представим жизненный случай: вы написали программу и хотите понять, сколько времени она работает. Первый пример — ровно тот код, что мы обсуждали в начале пары: два вложенных цикла длины nn. Мы уже пришли к тому, что его можно оценить как Θ(n2)\Theta(n^2), ну или сказать, что он O(n2)O(n^2) — в принципе, и то, и другое верные утверждения.

Посмотрим на более сложный второй пример, где внутренний цикл зависит от внешнего:

for i in range(n):
    for j in range(i):
        s += 1

Сколько операций делает этот код? Он делает сумму по ii от нуля до nn примерно i+1i + 1 операций, грубо говоря, то есть всего примерно n22\frac{n^2}{2} операций. Ну и опять-таки мы знаем, что это O(n2)O(n^2).

Третий код, в принципе, аналогичен второму, только вложенных циклов теперь пять. Опять-таки можем сказать, что это примерно n55!\frac{n^5}{5!} операций, или O(n5)O(n^5). Разве что здесь хочется обратить внимание на константу: она выросла до 5!=1205! = 120, поэтому, когда вы пишете такой код, об этой константе стоит думать — оценка n5n^5 не совсем точна, и стоит помнить, что при ней есть константа.

Оценка вложенных циклов и мастер-теорема

Доска 3 — пять примеров оценки времени работы циклов

Доска 4 — мастер-теорема: формулировка, три случая, башенка для T(n)=2T(n/2)+n

Доска 5 — дерево рекурсии, работа по уровням и геометрическая прогрессия

Пример ④. Внешний цикл перебирает ii от 1 до nn, а внутри стоит цикл for от нуля с шагом +i+i, пока индекс остаётся в диапазоне до nn:

for i = 1..n:
    for (j = 0; j < n; j += i):
        ...

Хочется сказать, что этот код работает примерно за n2n^2 операций — и это правда, но оценка слишком грубая, здесь можно получить лучше. При фиксированном ii внутренний цикл делает порядка n/in/i итераций, поэтому весь код работает за ∑i=1nn/i\sum_{i=1}^{n} n/i операций. Этот ряд нам уже знаком: вынесем nn и получим гармоническую сумму. Мы формулировали без доказательства, что ∑i=1nni=n(ln⁡n+O(1))\sum_{i=1}^{n} \frac{n}{i} = n(\ln n + O(1)). Значит, ответ — Θ(nlog⁡n)\Theta(n \log n): куда более быстрая величина, чем грубая оценка n2n^2.

Пример ⑤, в котором нас тоже ждёт подвох. Задача: посчитать количество целых неотрицательных решений уравнения x2+y2=Nx^2 + y^2 = N. Решать будем так: перебираем xx по возрастанию, а внутренним циклом уменьшаем yy до подходящего значения; если оказалось, что x2+y2=Nx^2 + y^2 = N, выводим ответ (x,y)(x, y). Стоит аккуратно заметить, что yy переиспользуется в каждой следующей итерации внешнего цикла, но это логично: когда xx увеличивается, наибольший подходящий yy, разумеется, только уменьшается.

Какая будет грубая оценка этого кода? Внешний цикл делает N\sqrt{N} итераций, и внутренний цикл за один проход делает не более N\sqrt{N} итераций, итого O(N)O(N). Такая оценка верна, но, как и в предыдущем примере, она грубая; на самом деле можно доказать, что код работает за Θ(N)\Theta(\sqrt{N}). Ключевое наблюдение: каждая итерация внутреннего цикла уменьшает yy на единицу, а yy между итерациями внешнего цикла не восстанавливается, поэтому суммарное количество итераций внутреннего цикла за всё время работы тоже не превосходит N\sqrt{N}. Итого: N\sqrt{N} итераций внешнего цикла и суммарно не более N\sqrt{N} итераций внутреннего. Вся остальная работа ограничена суммарной работой циклов, поэтому достаточно посчитать именно её — и получается Θ(N)\Theta(\sqrt{N}).

Пример ⑥ — небольшая модификация примера ④. Поставим такую задачу: для каждого числа от 1 до nn сохранить список его делителей. Например, у единицы делитель 1, у двойки — 1 и 2, у тройки — 1 и 3, у четвёрки — 1, 2 и 4. Как решать: как в коде примера ④, переберём делитель dd и пройдём по числам с шагом dd, для каждого такого числа aa запоминая делитель dd. По тем же соображениям, что и в примере ④, это работает за Θ(nlog⁡n)\Theta(n \log n).

Следующее утверждение называется мастер-теоремой, или теоремой об основных рекуррентных соотношениях. Формулируется она так: пусть T(n)=a⋅T(n/b)+ncT(n) = a \cdot T(n/b) + n^c. Когда такая рекуррента встречается в жизни? Представьте, что у нас есть алгоритм, время работы которого T(n)T(n) мы хотим оценить, и этот алгоритм запускает сам себя рекурсивно, например, два раза на задачах размера n/2n/2, а на подготовку к запуску рекурсии тратит ещё, скажем, 2n2n операций. Достаточно частый пример — время работы одного из алгоритмов сортировки: задача дважды запускается на половинном размере. Хочется понять, чему же в итоге равно T(n)T(n), и мастер-теорема отвечает на этот вопрос.

Точную формулировку запишем чуть позже, а пока зафиксируем условия: a,b,c∈Za, b, c \in \mathbb{Z} — целые константы, причём осмысленно применять теорему, когда a≥1a \ge 1, когда b≥2b \ge 2 (чтобы рекурсия не зацикливалась) и когда c≥0c \ge 0. В зависимости от нескольких случаев T(n)T(n) будет равно разным величинам, и сейчас мы разберёмся, каким именно.

Нарисуем дерево рекурсии нашего алгоритма. На самом верхнем уровне — одна задача размера nn. На следующем уровне рекурсии будет aa задач, каждая размера n/bn/b; на втором уровне — задачи размера n/b2n/b^2, и картинка продолжается до тех пор, пока частное n/bkn/b^k не станет примерно константой. Когда размер задачи ограничен константой, алгоритм работает константное время — в листьях дерева лежат задачи константного размера, n≈1n \approx 1. Отсюда, кстати, можно оценить и размер дерева рекурсии: его глубина — log⁡bn\log_b n.

Теперь просуммируем работу по этому дереву. Начнём с корня: в корне задача размера nn, то есть работа ncn^c. На следующем уровне aa задач размера n/bn/b, то есть суммарно a⋅(n/b)ca \cdot (n/b)^c. Уровнем глубже задач уже a2a^2, каждая размера n/b2n/b^2, то есть a2⋅(n/b2)ca^2 \cdot (n/b^2)^c. Можно продолжать расписывать всю сумму, но давайте её приведём: в каждом слагаемом есть множитель ncn^c, вынесем его. Первая строчка — это nc⋅(a/bc)0n^c \cdot (a/b^c)^0, вторая — nc⋅(a/bc)n^c \cdot (a/b^c), третья — nc⋅(a/bc)2n^c \cdot (a/b^c)^2, и так далее по всем уровням. Получается чудесная сумма: T(n)=∑i=0log⁡bnnc⋅(abc)iT(n) = \sum_{i=0}^{\log_b n} n^c \cdot \left(\frac{a}{b^c}\right)^i.

Вынесем ncn^c за знак суммы и посмотрим, как суммируется геометрическая прогрессия. Суммируется она просто: 1+q+q2+⋯+qn−1=1−qn1−q1 + q + q^2 + \dots + q^{n-1} = \frac{1 - q^n}{1 - q}, или, что то же самое, qn−1q−1\frac{q^n - 1}{q - 1}. Всё, что происходит внутри скобки, очень зависит от того, какая у нас прогрессия со знаменателем q=a/bcq = a/b^c: убывающая или возрастающая. И, как всегда, есть особый случай q=1q = 1, когда формула неприменима, — с него и начнём.

Если q=1q = 1, то есть a=bca = b^c, каждое из log⁡bn\log_b n слагаемых равно ncn^c. Значит, T(n)=Θ(nc⋅log⁡bn)T(n) = \Theta(n^c \cdot \log_b n). Это первый случай: при a=bca = b^c получаем Θ(nclog⁡n)\Theta(n^c \log n).

Теперь изучим, что происходит, когда q<1q < 1, то есть a/bc<1a/b^c < 1. Известный факт: сумма геометрической прогрессии со знаменателем меньше единицы стремится к константе. Давайте напишем конкретную константу: это 11−q\frac{1}{1 - q}, ведь если в выражении 1−qn1−q\frac{1 - q^n}{1 - q} перейти к пределу по nn при q<1q < 1, то qnq^n уходит в ноль. Раз сумма стремится к константе, она есть Θ(1)\Theta(1) — тем более что она хотя бы единица. Для нас это значит: если a/bc<1a/b^c < 1, то в скобке стоит константа, и T(n)=Θ(nc)T(n) = \Theta(n^c).

Перед последним случаем сделаем небольшое наблюдение. В случае a<bca < b^c геометрическая прогрессия, по сути, определена своим первым элементом: вся работа задаётся самым верхним уровнем дерева, а всё остальное оценивается константой относительно него. Во втором случае, когда a=bca = b^c, работа на каждом уровне была одинакова, поэтому итог — значение на одном уровне, умноженное на количество уровней. Если же q>1q > 1, то сумма прогрессии есть Θ\Theta её последнего члена: вся работа определяется самым нижним уровнем рекурсии. Иначе говоря, дерево разрастается настолько быстро, что уже не важно, какая функция стоит в вершине, — суммарное время работы определяется тем, насколько картинка разрослась вширь.

Поэтому в этом случае просуммируем только последний уровень. Мы договаривались, что на самом нижнем уровне всюду записано n/bkn/b^k, примерно равное константе, значит, время работы в каждой вершине последнего уровня константное. Осталось понять, сколько там вершин: T(n)=Θ(1)⋅T(n) = \Theta(1) \cdot {}(число вершин на последнем уровне), а вершин там alog⁡bna^{\log_b n}. Величина немножко неприятная — степень с логарифмом в показателе смотрится плоховато, давайте её перепишем. Заметим, что blog⁡ba=ab^{\log_b a} = a, поэтому alog⁡bn=(blog⁡ba)log⁡bn=(blog⁡bn)log⁡ba=nlog⁡baa^{\log_b n} = \left(b^{\log_b a}\right)^{\log_b n} = \left(b^{\log_b n}\right)^{\log_b a} = n^{\log_b a}. Итак, в третьем случае, при a>bca > b^c, получаем T(n)=Θ(nlog⁡ba)T(n) = \Theta\left(n^{\log_b a}\right). На случай, если возник вопрос, почему здесь я не стал явно подставлять формулу суммы прогрессии, как в предыдущем случае: можно было и так, ответ получился бы тот же, просто формул было бы чуть больше.

Вернёмся к формулировке: теперь готовы все три случая, посмотрим на примере. Пусть T(n)=2T(n/2)+nT(n) = 2T(n/2) + n: здесь a=2a = 2, b=2b = 2, c=1c = 1, то есть и aa, и bcb^c равны двум — мы попали в случай a=bca = b^c. Значит, решение этой рекурренты — Θ(nlog⁡n)\Theta(n \log n).

В данном случае тот же ответ можно получить и более простым способом — нарисуем такую картину-башенку. На верхнем уровне задача размера nn, на втором — две задачи размера n/2n/2, на следующем — четыре задачи размера n/4n/4, и так далее. Итого получается log⁡2n\log_2 n этажей, каждый из которых суммарно имеет размер nn. Значит, суммарная работа по обработке этой башенки — nlog⁡nn \log n. Но на самом деле это просто частный случай того рассуждения, которое мы только что проделали в общем виде.

Следующий наш герой — теорема об экспоненциальных рекуррентных соотношениях. Выглядит она так: пусть T(n)=∑i=1kai⋅T(n−bi)T(n) = \sum_{i=1}^{k} a_i \cdot T(n - b_i) — тогда про это T(n)T(n) тоже можно кое-что сказать, и сейчас разберёмся, что именно. Так как нас интересуют случаи, когда T(n)T(n) — время работы какой-то программы, будем считать, что ai,bi∈Za_i, b_i \in \mathbb{Z}, с естественными ограничениями ai≥1a_i \ge 1 и bi≥1b_i \ge 1 — иначе размер задачи не уменьшится.

Где такое может встретиться? Представьте, что вы разработали алгоритм для какой-то сложной задачи с экспоненциальным временем работы, но умеете чуть-чуть уменьшать задачу, запускаясь рекурсивно несколько раз, — и вам интересно, за сколько он будет работать. Короткий спойлер: раз звучат слова «экспоненциальные», программа работает за экспоненту, но за какую именно — надо ещё разобраться. В простейшем случае это достаточно очевидно: если T(n)T(n) каждый раз разбивается на два T(n−1)T(n-1), то строится полное бинарное дерево, и это явно Θ(2n)\Theta(2^n). А что будет в общем случае, мы сейчас узнаем.

Предположим, что мы в идеальном мире и T(n)T(n) — ровно cnc^n. На самом деле дальше мы и получим, что T(n)T(n) — экспоненциальная функция, но пока представим, что даже без всяких Θ\Theta это в точности cnc^n. Подставим это значение в рекурренту: слева получится cnc^n, справа — ∑iai⋅cn−bi\sum_i a_i \cdot c^{n - b_i}. Возникает логичное желание сократить на cnc^n — давайте так и сделаем. Получилось уравнение 1=∑iai⋅c−bi1 = \sum_i a_i \cdot c^{-b_i}. Может показаться странным, но это, по сути, полином от cc: степени здесь отрицательные, но если мысленно домножить на подходящую степень cc, получится самый настоящий многочлен, который, кстати, называется характеристическим.

Что важно для нас: я утверждаю, что у этого уравнения существует корень больше нуля, причём единственный. Давайте поймём, почему он действительно ровно один. Слева записана константа. А справа: каждое c−bic^{-b_i} — убывающая функция от cc, стремящаяся к нулю на бесконечности; сумма таких функций с положительными коэффициентами — снова строго монотонно убывающая функция, стремящаяся к нулю на бесконечности. Нас интересует значение единица: проведём горизонтальный уровень y=1y = 1, и точка, в которой кривая ∑iaic−bi\sum_i a_i c^{-b_i} его пересекает, — это и есть наш единственный положительный корень cc. И утверждение теоремы состоит в том, что если этот корень найти, то T(n)=Θ(cn)T(n) = \Theta(c^n), где cc — решение характеристического уравнения.

Рассмотрим это дело на частном случае — рекурренте Фибоначчи T(n)=T(n−1)+T(n−2)T(n) = T(n-1) + T(n-2). Подставляя T(n)=cnT(n) = c^n, получаем cn=cn−1+cn−2c^n = c^{n-1} + c^{n-2}, то есть 1=c−1+c−21 = c^{-1} + c^{-2}, то есть c2−c−1=0c^2 - c - 1 = 0. Это квадратное уравнение; решая его, получаем c=1+52c = \frac{1 + \sqrt{5}}{2}. Теорема говорит: раз мы такой корень нашли — а мы его нашли, — то T(n)=Θ(cn)T(n) = \Theta(c^n).

Давайте доказывать. Я докажу с вами, что T(n)=O(cn)T(n) = O(c^n); нижняя оценка Ω(cn)\Omega(c^n) доказывается аналогично, и мы её опустим. Что я хочу доказать: существует некоторая константа γ>0\gamma > 0 такая, что T(n)≤γ⋅cnT(n) \le \gamma \cdot c^n. Доказывать будем по индукции, а у индукции две части: база и переход. В базе нужно проверить неравенство для маленьких nn.

Экспоненциальные рекурренты и алгоритм Карацубы

Доска 6 — теорема об экспоненциальных рекуррентах и единственный положительный корень

Доска 7 — алгоритм Карацубы: от 4 умножений к 3, Θ(n^log₂3)

Докажем теорему о рекуррентах по индукции. Утверждение такое: существует γ>0\gamma > 0, для которой T(n)≤γcnT(n) \le \gamma c^n. Почему вообще нужно аккуратно формулировать базу? Потому что при маленьких nn рекуррентная формула просто неверна: например, при n=1n = 1 подставлять в неё нечего. В таком случае мы считаем, что T(n)T(n) при n=1,…,mn = 1, \dots, m — некоторые константы. Хочется, чтобы неравенство T(n)≤γcnT(n) \le \gamma c^n выполнялось и для них, но поскольку здесь записано лишь конечное число неравенств, можно просто подобрать γ\gamma достаточно большой, чтобы все они были верны.

Теперь переход индукции. Пусть для любого n≤N−1n \le N - 1 верно наше утверждение, то есть T(n)≤γcnT(n) \le \gamma c^n. Распишем T(N)T(N) по определению: T(N)=∑i=1kai T(N−bi)T(N) = \sum_{i=1}^{k} a_i\, T(N - b_i). Во всех слагаемых аргумент уменьшился, значит, можно применить индукционное предположение и подставить оценку в каждое слагаемое: T(N)≤∑i=1kaiγcN−biT(N) \le \sum_{i=1}^{k} a_i \gamma c^{N - b_i}. Следующим действием γ\gamma выносится за скобку, поскольку она появилась везде, и остаётся γ∑i=1kaicN−bi\gamma \sum_{i=1}^{k} a_i c^{N - b_i}. А теперь вспомним, что такое cc: это величина, которая является корнем уравнения cn=∑i=1kaicn−bic^n = \sum_{i=1}^{k} a_i c^{n - b_i}. Поэтому последнее выражение превратилось ровно в γcN\gamma c^N, что и требовалось. Если резюмировать: в переходе вся хитрость в том, что γ\gamma выносится за сумму, а в базе такую γ\gamma иначе просто не зафиксируешь — её нужно взять достаточно большой.

Ещё пару слов про оценку снизу, то есть про Ω\Omega. Соответствующие неравенства касаются главным образом базы, переход остаётся ровно таким же. Есть момент, когда база не сработает: если TT — нулевая функция, то ограничить её снизу не получится; там надо требовать, чтобы TT была хотя бы какой-то положительной константой. Если же TT всегда больше нуля, то и такая база, и такой переход остаются ровно теми же.

Последнее, что мы сегодня сделаем, — обсудим алгоритм Карацубы, который нужен, чтобы умножать многочлены и числа. Начнём с наблюдения. Если раскрыть скобки в произведении (2x+3)(x+1)(2x + 3)(x + 1), получится 2x2+5x+32x^2 + 5x + 3. А теперь умножим числа: 23⋅11=25323 \cdot 11 = 253. Заметьте, что и здесь, и здесь получилось одно и то же — и это не просто так. Умножение чисел — это почти то же самое, что умножение многочленов: когда я пишу 2323, на самом деле это 2⋅10+32 \cdot 10 + 3. Поэтому число 2323 логично представить многочленом 2x+32x + 3: умножаете ваши числа как многочлены, а в конце подстановкой x=10x = 10 превращаете многочлен обратно в число — из 2x2+5x+32x^2 + 5x + 3 получается 253253.

Есть, правда, нюанс: в конце можно получить многочлен вроде 20x2+15x+320x^2 + 15x + 3, а числа, у которого первая цифра 2020, вторая 1515, а последняя 33, не бывает. Но это несущественная трудность: вы просто получаете число 20⋅102+15⋅10+320 \cdot 10^2 + 15 \cdot 10 + 3 и делаете все переносы. Что получится? В младшем разряде остаётся 33, дальше 5⋅105 \cdot 10, а единица ушла в следующий разряд; там 21⋅10221 \cdot 10^2, снова оставляем единицу, и двойка уходит ещё выше: итого 2⋅103+1⋅102+5⋅10+32 \cdot 10^3 + 1 \cdot 10^2 + 5 \cdot 10 + 3. Поэтому, чтобы умножить числа, вы умножаете многочлены, а в конце за линейное время делаете переносы. Значит, дальше с вами будем обсуждать только, как умножать многочлены.

Самое простое умножение многочленов пишется так:

for i = 0 .. |a| - 1:
    for j = 0 .. |b| - 1:
        c[i + j] += a[i] * b[j]

Здесь есть неприятный момент: количество коэффициентов многочлена и его степень — разные вещи. Когда я пишу ∣a∣|a|, я имею в виду количество коэффициентов; например, у многочлена 2x2+5x+32x^2 + 5x + 3 оно равно трём. Несложно видеть, что этот алгоритм работает за O(n2)O(n^2).

Давайте сделаем что-то более умное. Если вам сейчас будет некомфортно с делением пополам, считайте, что nn — это просто степень двойки. Разобьём коэффициенты каждого из многочленов AA и BB на две половинки: A0A_0 забирает себе младшую половину коэффициентов, A0=a0+a1x+⋯+an/2−1xn/2−1A_0 = a_0 + a_1 x + \dots + a_{n/2 - 1} x^{n/2 - 1}, а A1A_1 — старшую, A1=an/2+an/2+1x+⋯+an−1xn/2−1A_1 = a_{n/2} + a_{n/2+1} x + \dots + a_{n-1} x^{n/2 - 1}, причём заметьте, что здесь все показатели у xx уменьшены на эту половинку. Иначе говоря, я представляю A=A0+xn/2A1A = A_0 + x^{n/2} A_1; многочлены B0B_0 и B1B_1 определяются аналогично.

Теперь распишем, что такое A⋅BA \cdot B. Подставляем наши представления и раскрываем скобки: AB=A0B0+xn/2(A1B0+A0B1)+xnA1B1AB = A_0 B_0 + x^{n/2}(A_1 B_0 + A_0 B_1) + x^n A_1 B_1. Как это вычислить? Нам дали два многочлена, мы разбили их пополам, и внутри произошли рекурсивные вызовы: получилось четыре рекурсивных вызова на половинках, результаты которых мы по этой формуле склеиваем за линейное время. Значит, время работы алгоритма выглядит так: T(n)=4 T(n/2)+O(n)T(n) = 4\,T(n/2) + O(n). Что нам говорит мастер-теорема по этому поводу? Надо сравнить aa и bcb^c: здесь a=4a = 4, а bc=21=2b^c = 2^1 = 2, то есть частное a/bca / b^c больше единицы, и мы попадаем в случай Θ ⁣(nlog⁡ba)=Θ(n2)\Theta\!\left(n^{\log_b a}\right) = \Theta(n^2). Это достаточно грустно, потому что за n2n^2 мы и так умеем очень просто умножать.

И вот тут возникает трюк Карацубы. Давайте я величину A0B1+A1B0A_0 B_1 + A_1 B_0 немножко перепишу: A0B1+A1B0=(A0+A1)(B0+B1)−A0B0−A1B1A_0 B_1 + A_1 B_0 = (A_0 + A_1)(B_0 + B_1) - A_0 B_0 - A_1 B_1. Что из этого следует? Что на самом деле нам нужно не четыре рекурсивных вызова, а три: первый — A0B0A_0 B_0, второй — A1B1A_1 B_1, третий — (A0+A1)(B0+B1)(A_0 + A_1)(B_0 + B_1), а в формуле выше снова участвуют первый и второй. Вычислив эти три произведения, мы по той же формуле склеим ответ. Значит, в рекурренте надо писать не четыре, а три: T(n)=3 T(n/2)+O(n)T(n) = 3\,T(n/2) + O(n), и по нашей теоремке получится Θ ⁣(nlog⁡23)\Theta\!\left(n^{\log_2 3}\right).

На этом наша пара на сегодня заканчивается, и в конце я добавлю ещё парочку формулировок, потому что главная тема сегодня была асимптотика, а не само умножение. Формулировки такие: логарифм в любой степени — это о-малое от степени с любым положительным показателем, то есть log⁡an=o(nb)\log^a n = o(n^b) для любых a,b>0a, b > 0; а степень с любым показателем — это о-малое от любой экспоненты, то есть na=o(cn)n^a = o(c^n) для любого c>1c > 1. Парочка примеров: log⁡2n=o ⁣(n0.0001)\log^2 n = o\!\left(n^{0.0001}\right) — квадрат логарифма меньше даже вот такой микроскопической степени; и n100=o ⁣(1.0001n)n^{100} = o\!\left(1.0001^n\right) — огромная степень проигрывает даже такой, казалось бы, безобидной экспоненте.