Введение

Метод в информатике

В информатике метод Акра–Бацци, или теорема Акра–Бацци, используется для анализа асимптотического поведения математических рекуррентных соотношений, возникающих при анализе алгоритмов «разделяй и властвуй», где подзадачи имеют существенно разные размеры. Это обобщение основной теоремы для рекуррентных соотношений типа «разделяй и властвуй», которая предполагает, что подзадачи имеют одинаковый размер. Метод назван в честь математиков Мохамада Акры и Луая Бацци. Условия применения:

* Предоставлено достаточное количество базовых случаев.
* являются константами для всех
* являются константами для всех
* являются константами для всех
, где c – константа, а O обозначает нотацию «большое O».
* является константой для всех

Асимптотическое поведение определяется путем нахождения значения , при котором , и подстановки этого значения в уравнение:

(см. Θ). Интуитивно, представляет собой небольшое отклонение в индексе . Отмечая, что и что абсолютное значение всегда находится между 0 и 1, можно использовать для игнорирования функции взятия целой части в индексе. Аналогично, можно игнорировать и функцию взятия целой части вверх. Например, и , согласно теореме Акра–Бацци, будут иметь одинаковое асимптотическое поведение.

Пример

Предположим, что функция δ определена как 1 для целых чисел n и 0 для целых чисел n, отличных от 0. При применении метода Акра–Бацци, первым шагом является поиск значения n, для которого δ(n) = 0. В этом примере, n = 1. Затем, используя формулу, асимптотическое поведение можно определить следующим образом:

Значение

Метод Акра-Бацци более полезен, чем большинство других техник для определения асимптотического поведения, поскольку он охватывает широкий спектр случаев. Его основное применение – приближение времени работы многих алгоритмов типа «разделяй и властвуй». Например, в сортировке слиянием количество сравнений, необходимых в худшем случае, которое приблизительно пропорционально времени его работы, задается рекурсивно как и для целых чисел , и, следовательно, может быть вычислено с помощью метода Акра-Бацци как .