§26. Асимптотичні оцінки розв’язків рекурентних нерівностей 169
§ 26. Асимптотичні оцінки рішень рекурентних нерівностей
Розглянутий метод оцінювання рішень рекурентних нерівностей (25.2), (25.14) призводить до досить точних оцінок, але потребує багатоетапної роботи. Часто буває достатньо отримати опис зростання рішення у вигляді простої асимптотичної оцінки. У § 24 ми отримали оцінку (24.7), вказавши при цьому, що для її виведення не потрібно визначати чисельні значення коефіцієнтів, що входять до відповідного приватного рішення асоційованого рекурентного рівняння. Цей шлях призводить до низки загальних теорем. Для них у різних літературних джерелах використовуються синонімічні назви «теорема про рекурентну нерівність», «основна теорема про рекурентні оцінки» і т. д. Ми наведемо дві теореми такого роду.
Теорема26.1 (прорекурентномунерівності,випадок^).Нехай невід'ємнаречовафункціяfнатуральногоаргументу задовольняєнерівності
^О(п 1 про &(;,+ і 0),якщоdd)k, якщоk >0,
з деякими конкретними с0,сг,с2, причомусгФ0, якщо і тільки якщо2d=v +w,або, що те саме, якщоd=log2(v+w). Розглянемо окремо три випадки.
1 У літературі англійською мовою - "master theorem" (майстер-теорема).
170Голова6.Рекурентніспіввідношенняіскладністьалгоритмів>
деC- деяке позитивне число. Використовуючи пропозицію 25.1, укладаємо, що
деC- деяке позитивне число. Аналогічно попередньому випадку за допомогою пропозиції 25.1 отримуємоf).
Випадокdk+c2(2d)k, але тепер для досить великих значеньkбудемо мати
деC- деяке позитивне число. За допомогою пропозиції 25.1 приходимо до оцінкиf(n) =O(n1 проvw). □
Схожа теорема може бути доведена і для випадку нерівності зі знаком замість знака.
Теорема26.2 (прорекурентномунерівності,випадок^).Нехай речовафункціяf(n)натуральногоаргументузадовольняє нерівності