Теорема Акры-Бацци: подзадачи разного размера

Если умеешь найти p из уравнения Акры-Бацци и посчитать интеграл для обычных f, листай до «Теперь сам».

Как думаешь, что решают эти три рекуррентности

В прошлом уроке T(n) = T(n/3) + T(2n/3) + n пришлось отложить: подзадачи разного размера, общего b нет. Деревом выходило Θ(n·log n). Прежде чем читать дальше, ответь себе, каков порядок у двух соседок:

T(n) = T(n/2) + T(n/4) + n
T(n) = T(n/2) + T(n/4) + 1

Подзадачи вместе меньше входа: 1/2 + 1/4 = 3/4. Растёт ли T быстрее n во втором случае, где работа одного вызова вне рекурсии постоянна? И какой это будет показатель - целый?

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

Представь, что режешь брусок сыра. Длина при разрезе сохраняется: кусок длиной n дал куски n/3 и 2n/3, их длины в сумме те же n. А если после разреза половину выбрасывают, сумма длин падает, и на следующем разрезе упадёт снова в ту же долю. Тогда хочется найти другую меру куска - не длину, а «длину в степени p», - которая при разрезе сохраняется точно. Найдёшь такую меру - узнаешь, сколько «сыра» дойдёт до самых мелких крошек.

Механизм: показатель p и интеграл по масштабам

Показатель. Пусть работы вне рекурсии нет, f = 0. Подставим в рекуррентность T(n) = n^p: справа выйдет a₁·(b₁n)^p + ... = n^p·(a₁·b₁^p + ... + a_k·b_k^p). Это равно n^p ровно тогда, когда сумма в скобках равна единице. Значит n^p - мера, которая при делении на подзадачи не теряется: сумма (размер)^p сохраняется при замене одного ещё не остановившегося узла его детьми. Здесь речь о границе дерева: листья, достигшие базового случая, остаются на ней, а не исчезают при следующем шаге. Для листьев размера 1 эта сумма и есть их число - отсюда главная роль n^p. Каждая доля bᵢ меньше единицы, поэтому bᵢ^p убывает с ростом p, и корень уравнения единственный: его находят делением отрезка пополам. Для равных подзадач уравнение a·(1/b)^p = 1 даёт p = log_b a - водораздел главной теоремы.

Интеграл. При неравных долях группируем вызовы по размеру, а не по глубине: на одной глубине размеры уже могут различаться. Мысленный разрез дерева останавливает каждую ветвь при достижении масштаба около m. В модели без округления сохраняемая мера даёт около n^p/m^p подзадач этого масштаба, а их работа сравнима с n^p·f(m)/m^p. Условие регулярности ниже позволяет сравнивать работу внутри полосы размеров с работой на её границе.

Осталось сложить по масштабам. На каждой полосе [2^j, 2^(j+1)] площадь под 1/u одинакова: ln 2^(j+1) - ln 2^j = ln 2. Поэтому сумма f(u)/u^p по таким полосам соответствует интегралу ∫ f(u)/u^(p+1) du. Полоса размеров не является уровнем дерева. Единица в формуле учитывает базовую работу листьев.

Это объяснение дерева предполагает целое число вызовов и положительный порог остановки. В коде ниже аргументы округляются вниз, и лист размера 0 тоже стоит единицу: считать его вклад как 0^p нельзя. Версия теоремы допускает такие ограниченные смещения аргументов при указанных условиях; картинка меры объясняет порядок роста, а не точное число листьев в коде.

Правило

Теорема Акры-Бацци (Akra, Bazzi, 1998). Для T(n) = Σ aᵢ·T(bᵢ·n) + f(n), где все aᵢ > 0, 0 < bᵢ < 1, базовые значения положительны и ограничены константами, а f положительна, не убывает и удовлетворяет условию регулярности: для каждого фиксированного c > 1 существует постоянная d > 0, такая что при достаточно больших n выполняется f(n/c) ≥ d·f(n). Рассматриваем суммы коэффициентов не меньше единицы; показатель может быть нулём. Это достаточная версия условий для показанных здесь функций; одна лишь оценка сверху многочленом регулярность не заменяет. Найди p из Σ aᵢ·bᵢ^p = 1. Тогда T(n) = Θ(n^p·(1 + ∫₁ⁿ f(u)/u^(p+1) du)).

Разбор: треть и две трети

T(n) = T(n/3) + T(2n/3) + n. Уравнение (1/3)^p + (2/3)^p = 1 угадывается: при p = 1 выходит 1/3 + 2/3 = 1. Интеграл: ∫₁ⁿ u/u² du = ∫₁ⁿ du/u = ln n. Ответ Θ(n·(1 + ln n)) = Θ(n·log n) - то, что дерево давало в прошлом уроке, но без рисования.

Проверим на главной теореме. T(n) = 4·T(n/2) + n: 4·(1/2)^p = 1 даёт p = 2; интеграл ∫₁ⁿ u/u³ du = ∫₁ⁿ u^(-2) du = 1 - 1/n, не больше единицы. Ответ Θ(n²) - случай 1. Все три случая видны по интегралу при f = n^k: под знаком стоит u^(k-p-1). При k < p площадь ограничена (решают листья), при k = p это 1/u и выходит ln n (все уровни поровну), при k > p площадь растёт как n^(k-p), и ответ n^k (решает корень).

Разбор: дробный показатель и ответ, который колеблется

Для T(n/2) + T(n/4) уравнение (1/2)^p + (1/4)^p = 1 в целых числах не решается. Программа находит p делением пополам и сверяет предсказание с точным T(n), посчитанным рекурсией с округлением вниз:

Запись @lru_cache(maxsize=None) перед функцией - декоратор: он оборачивает её механизмом запоминания ответов. При повторном вызове с тем же n Python возвращает сохранённое значение. maxsize=None снимает ограничение числа запомненных аргументов. Здесь это ускоряет вычисление таблицы значений T(n); оно не меняет ни рекуррентность, ни число операций алгоритма, которое она описывает.

import math
from functools import lru_cache


def najti_p(chasti):            # пары (aᵢ, bᵢ), bᵢ - доля входа
    lo, hi = 0.0, 1.0           # здесь сумма aᵢ >= 1, значит p >= 0
    while sum(a * b ** hi for a, b in chasti) > 1:
        hi *= 2                # сначала заключаем корень в отрезок
    for _ in range(100):        # сумма aᵢ·bᵢ^p убывает по p
        p = (lo + hi) / 2
        if sum(a * b ** p for a, b in chasti) > 1:
            lo = p
        else:
            hi = p
    return p


@lru_cache(maxsize=None)
def t_a(n):                     # T(n/3) + T(2n/3) + n
    return 1 if n < 2 else t_a(n // 3) + t_a(2 * n // 3) + n


@lru_cache(maxsize=None)
def t_b(n):                     # T(n/2) + T(n/4) + 1
    return 1 if n < 2 else t_b(n // 2) + t_b(n // 4) + 1


@lru_cache(maxsize=None)
def t_c(n):                     # T(n/2) + T(n/4) + n
    return 1 if n < 2 else t_c(n // 2) + t_c(n // 4) + n


pa = najti_p([(1, 1 / 3), (1, 2 / 3)])
pb = najti_p([(1, 1 / 2), (1, 1 / 4)])
print(f"p для 1/3 + 2/3: {pa:.4f}   p для 1/2 + 1/4: {pb:.4f}")
print("       n   A/(n ln n)   B/n^p    C/n")
for k in range(3, 8):
    n = 10 ** k
    print(f"{n:8}   {t_a(n) / (n * math.log(n)):9.3f}"
          f"   {t_b(n) / n ** pb:6.3f}   {t_c(n) / n:5.3f}")

p для 1/3 + 2/3: 1.0000   p для 1/2 + 1/4: 0.6942
       n   A/(n ln n)   B/n^p    C/n
    1000       1.524    1.463   3.466
   10000       1.544    2.037   3.786
  100000       1.553    1.746   3.893
 1000000       1.539    1.496   3.937
10000000       1.544    2.073   3.975

Точное значение p = log₂((1+√5)/2) ≈ 0,69424. Для B (работа 1) интеграл ∫ u^(-p-1) du ограничен, поскольку p > 0, и ответ Θ(n^p): решают листья. Округлять показатель внутри Θ нельзя: даже малая постоянная разница показателей меняет асимптотический класс. Для C (работа n) интеграл ∫ u^(-p) du растёт как n^(1-p), ведь 0 < p < 1. Ответ n^p·n^(1-p) = Θ(n); решает корень. Отношение подходит к 4: работа по глубинам здесь n·(1 + 3/4 + 9/16 + ...) = 4n.

Граница наивного чтения - столбец B: в показанных пяти замерах отношение колеблется между 1,46 и 2,07. По конечной таблице нельзя доказать ни существование, ни отсутствие предела. Теорема этого и не утверждает: Θ обещает зажать T(n) между двумя постоянными кратными n^p. Округления сдвигают границы базовых случаев, поэтому постоянный множитель в этой таблице заметно меняется, оставаясь совместимым с оценкой.

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

Первая ошибка - заменить разные подзадачи большей: T(n/3) + T(2n/3) превращают в 2·T(2n/3), главная теорема даёт n^(log₁,₅ 2) ≈ n^1,71, и честный n·log n теряется под завышенной оценкой. Вторая - сложить доли и решить, что раз 1/2 + 1/4 < 1, то ответ линейный при любой f: у B он n^p, а не константа, - сумма долей меньше единицы ещё не значит «решает корень». Третья - применить теорему к f, которая растёт быстрее многочлена: при f(n) = 2ⁿ условие нарушено, вход вдвое меньше роняет f не в постоянное число раз.

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

Выбор k-го элемента медианой медианРазбирается в разделе 6, глава «Выбор k-го элемента»: Медиана медиан: линейное время в худшем случае даёт T(n) ≤ T(n/5) + T(7n/10) + n. Прочитать его главной теоремой нельзя: подзадачи разные. Сумма долей 1/5 + 7/10 = 0,9, поэтому p < 1, под интегралом u^(-p), площадь растёт как n^(1-p), и равенство для мажорирующей рекуррентности даёт Θ(n). Для исходного неравенства это доказывает верхнюю границу O(n); линейная работа самого шага дополнительно даёт Ω(n). Поэтому полный алгоритм работает за Θ(n). Так же читается слияние, которое режет вход не пополам, а в отношении 1:3: T(n/4) + T(3n/4) + n даёт p = 1 и тот же Θ(n·log n).

Теперь сам

Реши теоремой Акры-Бацци T(n) = 2·T(n/2) + n·log n - тот самый зазор, где главная теорема молчала.