В информатике метод Акра – Бацци или теорема Акра – Бацци используется для анализа асимптотического поведения математических повторений, которые появляются при анализе алгоритмов « разделяй и властвуй» , где подзадачи имеют существенно разные размеры. Это обобщение основной теоремы для повторений «разделяй и властвуй» , в которой предполагается, что подзадачи имеют одинаковый размер. Он назван в честь математиков Мохамада Акра и Луая Бацци . [1]
Формулировка
Метод Акра – Бацци применяется к рекуррентным формулам вида [1]
Условия использования:
- предоставлены достаточные базовые случаи
- а также константы для всех
- для всех
- для всех
- , где c - постоянная, а O обозначает нотацию Big O
- для всех
- это константа
Асимптотика находится путем определения значения для которого и подставляя это значение в уравнение [2]
(см thetas ; ). Интуитивно представляет собой небольшое возмущение индекса . Отмечая, что и что абсолютное значение всегда между 0 и 1, можно использовать для игнорирования функции пола в индексе. Точно так же можно игнорировать функцию потолка . Например, а также будет, согласно теореме Акра – Бацци, иметь такое же асимптотическое поведение.
Пример
Предполагать определяется как 1 для целых чисел а также для целых чисел . При применении метода Акра – Бацци первым шагом является определение значения для которого . В этом примере. Тогда, используя формулу, асимптотика может быть определена следующим образом: [3]
Значимость
Метод Акра – Бацци более полезен, чем большинство других методов для определения асимптотического поведения, поскольку он охватывает такое большое количество случаев. Его основное применение - аппроксимация времени работы многих алгоритмов «разделяй и властвуй». Например, при сортировке слиянием количество сравнений, требуемых в худшем случае, которое примерно пропорционально времени его выполнения, рекурсивно задается как а также
для целых чисел , и, таким образом, могут быть вычислены с использованием метода Акра – Бацци, чтобы быть .
Смотрите также
Рекомендации
- ^ а б Акра, Мохамад; Бацци, Луай (май 1998 г.). «О решении линейных рекуррентных уравнений». Вычислительная оптимизация и приложения . 10 (2): 195–210. DOI : 10,1023 / A: 1018373005182 .
- ^ «Доказательство и применение на нескольких примерах» (PDF) .
- ^ Кормен, Томас; Лейзерсон, Чарльз; Ривест, Рональд; Стейн, Клиффорд (2009). Введение в алгоритмы . MIT Press. ISBN 978-0262033848.
Внешние ссылки
- O Método de Akra-Bazzi na Resolução de Equações de Recorrência (на португальском языке)