Теорема Акры — Баззи — результат, дающий оценку асимптотического поведения рекуррентных функций, которые возникают при анализе алгоритмов типа «разделяй и властвуй», обобщает основную теорему о рекуррентных соотношениях на случай, когда подзадачи имеют существенно разные размеры. Установлена ливанскими математиками Мохамадом Акрой и Луаем Баззи в 1998 году.
Применяется для рекуррентных формул вида: , для которых выполнено: , при малых искомая рекуррента , где обозначает -большое, и являются константами для всех от 1 до , для всех от 1 до , для всех от 1 до , , где — константа, для всех от 1 до . Теорема утверждает, что асимптотическое поведение рекурренты находится путём определения значения для которого и последующей подстановкой этого значения в выражение:
(под имеется в виду одновременное выполнение условий -большое (ограниченность сверху) и (ограниченность снизу)).
Функции можно рассматривать как небольшие возмущения в аргументах рекурренты . Учитывая, что и что абсолютная величина всегда находится в интервале между 0 и 1, можно использовать добавки для исключения взятия целой части аргумента. К примеру, рекуррентные формулы и будут, согласно теореме Акры — Баззи, иметь одинаковое асимптотическое поведение.
Теорема получила широкое применение в теории вычислительной сложности, обеспечивая технически удобный и более эффективный во случаях метод определения асимптотического поведения в весьма широком классе задач. В основном применяется для оценки времени выполнения алгоритмов типа «разделяй и властвуй».
Примеры Для , заданной системой:
значение определяется решением уравнения: , то есть . Далее, по формуле Акры — Баззи можно определить асимптотическое поведение следующим образом:
В алгоритме классической сортировки слиянием на каждом уровне рекурсии функция сортировки вызывает себя дважды на половинных наборах входных данных и выполняет слияние подмассивов, производя в худшем случае сравнение. Таким образом, рекуррентная формула для сортировки слиянием даётся системой:
Решение уравнения даёт . Далее, используя формулу теоремы, можно определить асимптотическое поведение следующим образом:
Примечания
Ссылки O Método de Akra-Bazzi na Resolução de Equações de Recorrência Категория:Рекуррентные соотношения Категория:Теоремы дискретной математики