Конспект: главная теорема

Понятия

Главная теорема - готовая формула для T(n) = a·T(n/b) + f(n) (a ≥ 1, b > 1, подзадачи равны). Сравнивает работу одного вызова вне рекурсии f(n) с водоразделом n^(log_b a).

Водораздел n^(log_b a) - число листьев дерева рекурсии. На уровне k узлов a^k, глубина log_b n, листьев a^(log_b n) = n^(log_b a) для степеней b; округления не меняют порядок. Работа уровня k равна a^k·f(n/b^k).

Три случая. f меньше водораздела (полиномиально) → Θ(n^(log_b a)), случай 1 (листья). f того же порядка → Θ(n^(log_b a)·log n), случай 2 (уровни). f больше (полиномиально) и выполнена регулярность → Θ(f(n)), случай 3 (корень).

Условие регулярности (только случай 3) - a·f(n/b) ≤ c·f(n) при c < 1: работа по уровням убывает геометрически вниз, поэтому её сумму задаёт корень.

Полиномиальный разрыв - отличие f от водораздела хотя бы на множитель n^ε (ε > 0). Разрыв лишь на логарифм - зазор, теорема неприменима.

Что унести

Порядок применения: выпиши a, b, f; посчитай n^(log_b a); сравни с f; назови случай. Три случая - это «листья, уровни, корень» из прошлой главы, записанные формулой.

Один и тот же ответ приходит через разные случаи. 4·T(n/2)+n и 2·T(n/2)+n² оба дают Θ(n²), но первый - случаем 1 (широкое дерево, листьев n²), второй - случаем 3 (тяжёлый корень). Понимать надо, КТО решает, а не только итог.

Случай 3 требует регулярности. У степенных f она выполняется сама, но проверить надо: a·f(n/b) ≤ c·f(n), c < 1. Смысл - уровень ниже стоит долю c от текущего, работа падает геометрически, ряд сходится к корню.

Теорема не всесильна. Зазор: f отличается от водораздела лишь на логарифм - 2·T(n/2)+n·log n даёт Θ(n·log²n) деревом, а наивный случай 3 потерял бы log n. Чужие формы: вычитание (T(n-1)) и переменные a, b берут дерево и подстановка, не теорема.

Неравные разбиения (T(n/3)+T(2n/3)+n) берёт теорема Акры-Бацци: найди p из Σ aᵢ·bᵢ^p = 1 (делением пополам, если не угадывается), ответ Θ(n^p·(1 + ∫₁ⁿ f(u)/u^(p+1) du)). Интеграл ограничен - решают листья, n^p.

Почти все «разделяй и властвуй» ложатся в теорему: слияние (2·T(n/2)+n → n·log n), Штрассен (7·T(n/2)+n² → n^(log₂7), показатель log₂7 ≈ 2,80735), число инверсий (2·T(n/2)+n → n·log n вместо квадратичного перебора).

Ловушки джокера

Спутал, что с чем сравнивают. Сравнивают f(n) с n^(log_b a), а не a с b. Показатель водораздела - log_b a, не a·b и не a.

Объявил случай 3 без проверки регулярности. Обычно ответ верный, но на подстроенных f регулярность рвётся, и Θ(f(n)) неверно.

Наивно применил случай 3 к зазору. 2·T(n/2)+n·log n - не случай 3: разрыв на log n не полиномиален. Верный ответ Θ(n·log²n), а не Θ(n·log n).

Подогнал под теорему вычитание. 2·T(n-1)+1 - не a·T(n/b): b > 1 обязательно. Ответ (экспонента) теорема не даст, решай разворачиванием.

Заменил неравные подзадачи большей. T(n/3)+T(2n/3) как 2·T(2n/3) даёт n^(log_(3/2) 2) вместо n·log n; и сумма долей меньше единицы не значит «решает корень»: T(n/2)+T(n/4)+1 растёт как n^p, где p = log₂((1+√5)/2) ≈ 0,69424.

Перепутал направление регулярности. a·f(n/b) - уровень ВНИЗ (вход в b раз меньше), подставляют n/b, а не n·b.

Проверь себя

Что такое n^(log_b a) и почему в формуле стоит именно оно?

Как по a, b, f определить случай и выписать ответ?

Зачем в случае 3 проверяют условие регулярности и что оно означает?

Почему 4·T(n/2)+n и 2·T(n/2)+n² дают один ответ Θ(n²), но разными случаями?

Почему к 2·T(n/2)+n·log n теорема неприменима и что даёт дерево?

Какие формы рекуррентностей теорема не берёт вовсе?

Как найти показатель p для T(n/3)+T(2n/3)+n и почему n^p - мера, которая при делении сохраняется?