Мастер-теорема - Алгоритмика
Мастер-теорема

Мастер-теорема

В этой статье мы докажем важную теорему об асимптотике большого класса «разделяек», в которых задача размера nn делится на aa задач в bb раз меньшего размера, с «мерджем» за Θ(nc)\Theta(n^c).

Мастер-теорема. Пусть имеется рекуррента:

T(n)={aT(nb)+Θ(nc),n>n0Θ(1),n≤n0 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⁡bac > \log_b a, то T(n)=Θ(nc)T(n) = \Theta(n^c).
  • B. Если c=log⁡bac = \log_b a, то T(n)=Θ(nclog⁡n)T(n) = \Theta(n^c \log n).
  • C. Если c<log⁡bac < \log_b a, то T(n)=Θ(nlog⁡ba)T(n) = \Theta(n^{\log_b a}).

Дерево рекурсии

Доказательство. Рассмотрим «дерево рекурсии» этого соотношения. В нём будет log⁡bn\log_b n уровней. На kk-том уровне будет aka^k вершин, каждая из которых будет стоить (nbk)c\left(\frac{n}{b^k}\right)^c операций. Просуммируем значения во всех вершинах по всем уровням:

T(n)=∑k=0log⁡bnak(nbk)c=nc∑k=0log⁡bn(abc)k 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⁡bac > \log_b a, то ∑(abс)k\sum (\frac{a}{b^с})^k это сумма убывающей геометрической прогрессии, которая не зависит от nn и просто равна какой-то константе. Значит, T(n)=Θ(nc)T(n) = \Theta(n^c).

B. Если c=log⁡bac = \log_b a, то

T(n)=nc∑k=0log⁡bn(abc)k=nc∑k=0log⁡bn1k=Θ(nclog⁡bn) 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⁡bac < \log_b a, то так как сумма прогрессии асимптотически эквивалентна своему старшему элементу, T(n)=nc∑k=0log⁡bn(abc)k=Θ(nc(abc)log⁡bn)=Θ(nc⋅alog⁡bnnc)=Θ(alog⁡bn)=Θ(nlog⁡ba) 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}) Примечание. Для более точных оценок асимптотики «мерджа» теорема ничего не говорит. Например, если мердж занимает Θ(nlog⁡n)\Theta(n \log n) и задача разбивается каждый раз на две части, то асимптотика будет равна: ∑k=0log⁡nnlog⁡n2k=∑k=0log⁡nn(log⁡n−k)=n∑k=0log⁡nk=Θ(nlog⁡2n) \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) В то же время эта рекуррента под условия теоремы не попадает. Можно лишь получить неточные границы Ω(nlog⁡n)\Omega (n \log n) и O(n1+ε)O(n^{1+\varepsilon}), если подставить c=1c = 1 и c=1+εc = 1 + \varepsilon соответственно. Заметим, что nlog⁡nn \log n и nlog⁡2nn \log^2 n асимптотически меньше n1+εn^{1+\varepsilon}, каким бы маленьким ε\varepsilon ни был.