В этой статье мы докажем важную теорему об асимптотике большого класса «разделяек», в которых задача размера $n$ делится на $a$ задач в $b$ раз меньшего размера, с «мерджем» за $\Theta(n^c)$.
Мастер-теорема. Пусть имеется рекуррента:
$$ T(n) = \begin{cases} a T(\frac{n}{b}) + \Theta(n^c), & n > n_0 \\ \Theta(1), & n \leq n_0 \end{cases} $$Тогда:
- A. Если $c > \log_b a$, то $T(n) = \Theta(n^c)$.
- B. Если $c = \log_b a$, то $T(n) = \Theta(n^c \log n)$.
- C. Если $c < \log_b a$, то $T(n) = \Theta(n^{\log_b a})$.
Доказательство. Рассмотрим «дерево рекурсии» этого соотношения. В нём будет $\log_b n$ уровней. На $k$-том уровне будет $a^k$ вершин, каждая из которых будет стоить $\left(\frac{n}{b^k}\right)^c$ операций. Просуммируем значения во всех вершинах по всем уровням:
$$ T(n) = \sum_{k=0}^{\log_b n} a^k \left(\frac{n}{b^k}\right)^c = n^c \sum_{k=0}^{\log_b n} \left(\frac{a}{b^c}\right)^k $$A. Если $c > \log_b a$, то $\sum (\frac{a}{b^с})^k$ это сумма убывающей геометрической прогрессии, которая не зависит от $n$ и просто равна какой-то константе. Значит, $T(n) = \Theta(n^c)$.
B. Если $c = \log_b a$, то
$$ T(n) = n^c \sum_{k=0}^{\log_b n} \left(\frac{a}{b^c}\right)^k = n^c \sum_{k=0}^{\log_b n} 1^k = \Theta(n^c \log_b n) $$ C. Если $c < \log_b a$, то так как сумма прогрессии асимптотически эквивалентна своему старшему элементу, $$ T(n) = n^c \sum_{k=0}^{\log_b n} \left(\frac{a}{b^c}\right)^k = \Theta\left(n^c \left(\frac{a}{b^c}\right)^{\log_b n}\right) = \Theta\left(n^c \cdot \frac{a^{\log_b n}}{n^c}\right) = \Theta(a^{\log_b n}) = \Theta(n^{\log_b a}) $$ Примечание. Для более точных оценок асимптотики «мерджа» теорема ничего не говорит. Например, если мердж занимает $\Theta(n \log n)$ и задача разбивается каждый раз на две части, то асимптотика будет равна: $$ \sum_{k=0}^{\log n} n \log \frac{n}{2^k} = \sum_{k=0}^{\log n} n (\log n - k) = n \sum_{k=0}^{\log n} k = \Theta (n \log^2 n) $$ В то же время эта рекуррента под условия теоремы не попадает. Можно лишь получить неточные границы $\Omega (n \log n)$ и $O(n^{1+\varepsilon})$, если подставить $c = 1$ и $c = 1 + \varepsilon$ соответственно. Заметим, что $n \log n$ и $n \log^2 n$ асимптотически меньше $n^{1+\varepsilon}$, каким бы маленьким $\varepsilon$ ни был.