На этом шаге мы рассмотрим эту теорему.

Основная теорема (master theorem) может использоваться в качестве быстрого способа определения временнОй сложности вычисления алгоритмов, основанных на стратегии "разделяй и властвуй". В частности, её можно применить к рекуррентным соотношениям следующего вида:

            c,               если n = 1
    T(n) = 
            aT(n/b) + f (n), если n > 1,

где a ≥ 1, b > 1, c ≥ 0 и f() - асимптотически положительная функция. Подобные алгоритмы обычно относятся к тем задачам, исходный размер которых делится на некоторое положительное число b, не меньшее двух. Последующая обработка или объединение решений подзадач требуют f(n) операций. В зависимости от вклада слагаемых aT(n/b) и f(n) в стоимость выполнения алгоритма основная теорема в её самой общей форме утверждает, что можно определить асимптотическую жёсткую границу для T в следующих трех случаях:

Если f(n) = Ο(n^log_ba-ε) для некоторой константы ε > 0, то T(n) ∈ Θ(n^log_ba);
Если f(n) = Θ(n^log_ba (log n)^k), где k ≥ 0, то T(n) ∈ Θ(n^log_ba (log n)^k+1);
Если f(n) = Ω(n^log_ba+ε), где ε > 0 и f(n) удовлетворяет так называемому условию регулярности a * f(n/b) ≤ d * f(n) для некоторой константы d < 1 и для всех достаточно больших n, то T(n) ∈ Θ(f(n)).

Например, для

            1,           если n = 1
    T(n) = 
            T(n/2) + 2ⁿ, если n > 1

можно найти такое ε > 0, что порядок f(n) = 2ⁿ будет больше n^(log₂1)+ε = n^ε. Действительно, в этом примере допустимо любое значение ε > 0, поскольку порядок показательной функции 2ⁿ всегда выше порядка полиномиальной. Таким образом, это рекуррентное соотношение относится к третьему случаю основной теоремы, который подразумевает, что T(n) ∈ Θ(2ⁿ).

Если f(n) - полином степени k, то можно воспользоваться следующей более простой версией основной теоремы:

             Θ(n^k),       если a * b^k < 1
    T(n)  ∈  Θ(n^k log n), если a * b^k = 1    (3.28)
             Θ(n log_b a), если a * b^k > 1

Этот результат может быть получен методом расширения. Рассмотрим следующее рекуррентное соотношение:

            c,                если n = 1
    T(n) =                                        (3.29)
            aT(n/b) + d * n^k, если n > 1

где a ≥ 1, b > 1, c ≥ 0 и d ≥ 0. Процесс его расширения:

    T(n) = aT(n/b) + dn^k = a[aT(n/b²) + d(n/b)^k] + dn^k = 
           = a²T(n/b²) + dn^k(1 + a/b^k) = a²[aT(n/b³) + d(n/b²)^k] + dn^k(1 + a/b^k) = 
           = a³T(n/b³) + dn^k(1 + a/b^k + a²/b^2k) = 
           .   .   .   .
                             _i-1   
           = aⁱT(n/bⁱ) + dn^k ∑ (a / b^k)^j.
                             ^j=1

Начальное условие T(1) = c достигается при i = log_b n, а подстановка этого значения в формулу даёт:

                             _{log_bn-1}                           _{log_bn-1}
    T(n) = c * a^log_bn + d * n^k ∑ (a / b^k)^j = c * n^log_ba + d * n^k	∑ (a / b^k)^j ,
                              ^j=0                               ^j=0

где в зависимости от значений a, b и k возможны три случая.

Если a < b^k, то
```
  _{log_bn-1}
    ∑ (a / b^k)^j
    ^j=0
```
будет постоянной величиной (которая не может быть бесконечностью). Отметим, что бесконечная сумма
```
    _∞
    ∑ rⁱ = 1 / (r - 1)   -
    ⁱ⁼⁰
```
константа при r < 1 (то есть не расходится).
Таким образом, в этом случае
```
    T(n) = c * n^log_ba + dKn^k
```
для некоторой постоянной K. Кроме того, поскольку a < b^k, то есть log_b a < k, то n^k - член высшего порядка. Следовательно:
```
    T(n) ∈ Θ(n^k)         .
```

Если a = b^k, то

                           _{log_bn-1}
    T(n) = c * n^k  + d * n^k ∑ 1 = c * n^k + d * n^k log_b n ,
                            ^j=0

из чего следует, что

    T(n) ∈ Θ(n^k log n)         .

Если a > b^k, то, вычислив сумму геометрической прогрессии, получим:
```
    T(n) = c * n^log_ba + dn^k((a/b^k)^log_bn - 1))/(a/b^k - 1) = 
         = c * n^log_ba + dn^k(nlog_ba/n^k - 1) K = 
         = (c + dK) n^log_ba - dKn^k,
```
где K = 1/(a/b^k - 1) - константа. Наконец, поскольку a > b^k , то есть log_b a > k, мы имеем:
```
    T(n) ∈ Θ(n^log_ba)         .
```

На следующем шаге мы рассмотрим дополнительные примеры.

Предыдущий шаг Содержание Следующий шаг