Когда теорема молчит: зазоры и чужие формы

Если понимаешь, что такое зазор между случаями и почему теорема не берёт T(n-1) и неравные разбиения, листай до «Теперь сам».

Как думаешь, всякую ли 2·T(n/2)+f возьмёт теорема

T(n) = 2·T(n/2) + n·log n. Водораздел n^(log_2 2) = n. Работа одного вызова вне рекурсии n·log n больше n - хочется сказать «случай 3, ответ Θ(n·log n)». Но проверь, НАСКОЛЬКО больше: f(n)/n^(log_b a) = (n·log n)/n = log n. Это множитель-логарифм, а не n^ε. Для случая 3 нужно, чтобы f обгоняла водораздел на степень n, а здесь - лишь на логарифм. Теорема этот случай не берёт.

На что это похоже

Три случая - три полки, между ними щели. Полка «листья больше», полка «поровну», полка «корень больше» - но между ними есть зазор, куда f проваливается, если отличается от водораздела слишком слабо, всего на логарифм. Как гиря чуть тяжелее эталона не ляжет ни на одну из трёх маркированных полок, так и n·log n не попадает ни в случай 2 (не поровну), ни в случай 3 (не полиномиально больше).

Механизм: почему решает именно «полиномиально»

Теорема стоит на геометрическом ряде: работа по уровням должна убывать (или расти) в число раз, чтобы сумму задавал один конец. «Полиномиально больше» значит f обгоняет водораздел на множитель n^ε - а n^ε при любом ε > 0 растёт быстрее любой степени логарифма. Только такой разрыв делает ряд по-настоящему геометрическим, и один конец - корень или листья - перевешивает остальные.

Множитель-логарифм для этого слишком слаб: log n растёт медленнее n^ε, сумму по уровням надо вычислять отдельно: универсального добавочного множителя здесь нет. Например, для f(n) = n/log n получается Θ(n·log log n): вклады уровней дают гармоническую сумму по логарифму входа. Для T(n) = 2·T(n/2) + n·log n деревом получается Θ(n·log² n) - на логарифм больше, чем дал бы наивный случай 3. Именно поэтому зазор выделен: наивно применить случай 3 - значит потерять этот log n.

Правило

Проверяй разрыв между f(n) и n^(log_b a) на ПОЛИНОМИАЛЬНОСТЬ (множитель n^ε, ε > 0). Разрыв лишь на логарифм - зазор, теорема неприменима, решай деревом. И теорема - только для a·T(n/b) + f(n) с постоянными a, b и равными подзадачами: вычитание и неравные разбиения не её.

Разбор: зазор между случаями 2 и 3

T(n) = 2·T(n/2) + n·log n. Водораздел n, f = n·log n, отношение log n - не n^ε. Зазор между случаями 2 и 3, теорема молчит. Решаем деревом: на уровне i вызовов 2ⁱ, размер n/2ⁱ, работа у каждого (n/2ⁱ)·log(n/2ⁱ), вместе на уровне n·log(n/2ⁱ) = n·(log n − i). Складываем по i от 0 до log n: n·(log n + (log n − 1) + ... + 1) = n·(сумма первых log n чисел) = n·Θ(log² n). Ответ Θ(n·log² n). Наивный случай 3 дал бы Θ(n·log n) - на множитель log n меньше, и это была бы ошибка.

Разбор: чужие формы, которые теорема не берёт

Теорема требует ровно a·T(n/b) + f(n). Не подходят:

• Вычитание входа: T(n) = T(n-1) + n (сортировка вставками наихудшим проходом). Вход убывает на константу, а не делится - формы a·T(n/b) нет. Решается суммой: n + (n−1) + ... + 1 = Θ(n²).
• Неравное разбиение: T(n) = T(n/3) + T(2n/3) + n. Подзадачи разного размера, единого b нет. Дерево показывает Θ(n·log n), но берётся оно не теоремой: для таких есть теорема Акры-БацциРазбирается в разделе 3, глава «Главная теорема и её три случая»: Теорема Акры-Бацци: подзадачи разного размера.
• Переменные a или b: T(n) = T(√n) + 1. Тут корень, а не деление на константу, - замена переменной, но не главная теорема.

Вычитание и переменные a, b берут дерево или подстановка из прошлой главы, неравные разбиения - теорема Акры-Бацци из следующего урока.

Что ломается без этого

Две ошибки. Применить случай 3 к зазору n·log n и потерять множитель log n (верный ответ n·log² n, а не n·log n). И «подогнать» под теорему форму с вычитанием: увидев 2·T(n-1)+1, подставить a = 2, b = 1 - но b > 1 обязательно, b = 1 теорема запрещает, и правильный ответ (экспонента) она бы не дала.

Зачем это в работе

Зазоры и чужие формы - не редкость: T(n) = 2·T(n/2) + n·log n возникает, когда уже отсортированные куски сливают с логарифмической работой на элемент; неравные разбиения дают многие геометрические алгоритмы. Знать границы теоремы важнее, чем саму теорему: применить её вне области - значит уверенно назвать неверный порядок, а это хуже, чем честно нарисовать дерево.

Теперь сам

Можно ли решить главной теоремой T(n) = 3·T(n-1) + 2? Если нет - почему и каким методом решать?