Метод Акра – Бацци - Akra–Bazzi method

В Информатика, то Метод Акра – Бацци, или же Теорема Акра – Бацци, используется для анализа асимптотики математического повторения которые появляются при анализе разделяй и властвуй алгоритмы где подзадачи имеют существенно разные размеры. Это обобщение основная теорема для повторений "разделяй и властвуй", который предполагает, что подзадачи имеют одинаковый размер. Назван в честь математиков. Мохамад Акра и Луай Бацци.^[1]

Формулировка

Метод Акра – Бацци применяется к рекуррентным формулам вида^[1]

{ Displaystyle Т (х) = г (х) + сумма _ {я = 1} ^ {к} а_ {я} T (b_ {я} х + h_ {я} (х)) qquad { текст {for}} x geq x_ {0}.}

Условия использования:

предоставлены достаточные базовые случаи
${ displaystyle a_ {i}}$ и ${ displaystyle b_ {i}}$ константы для всех ${ displaystyle i}$
${ displaystyle a_ {i}> 0}$ для всех ${ displaystyle i}$
${ displaystyle 0$ для всех ${ displaystyle i}$
${ Displaystyle влево | г (х) вправо | в О (х ^ {с})}$ , куда c является константой и О отмечает Обозначение Big O
${ displaystyle left | h_ {i} (x) right | in O left ({ frac {x} {( log x) ^ {2}}} right)}$ для всех ${ displaystyle i}$
${ displaystyle x_ {0}}$ это постоянная

Асимптотическое поведение ${ Displaystyle Т (х)}$ находится путем определения значения ${ displaystyle p}$ для которого ${ displaystyle sum _ {я = 1} ^ {k} a_ {i} b_ {i} ^ {p} = 1}$ и подставляя это значение в уравнение^[2]

{ Displaystyle Т (х) в Theta left (х ^ {p} left (1+ int _ {1} ^ {x} { frac {g (u)} {u ^ {p + 1) }}} ду право) право)}

(видеть Θ ). Интуитивно ${ displaystyle h_ {я} (х)}$ представляет собой небольшое возмущение индекса ${ displaystyle T}$ . Отмечая, что ${ displaystyle lfloor b_ {i} x rfloor = b_ {i} x + ( lfloor b_ {i} x rfloor -b_ {i} x)}$ и что абсолютное значение ${ displaystyle lfloor b_ {i} x rfloor -b_ {i} x}$ всегда между 0 и 1, ${ displaystyle h_ {я} (х)}$ можно использовать, чтобы игнорировать функция пола в индексе. Точно так же можно игнорировать функция потолка. Например, ${ Displaystyle Т (п) = п + Т влево ({ гидроразрыва {1} {2}} п вправо)}$ и ${ Displaystyle Т (п) = п + Т влево ( влево lfloor { frac {1} {2}} п вправо rfloor right)}$ будет, согласно теореме Акра – Бацци, иметь такое же асимптотическое поведение.

Пример

Предполагать ${ Displaystyle Т (п)}$ определяется как 1 для целых чисел ${ Displaystyle 0 Leq п Leq 3}$ и ${ displaystyle n ^ {2} + { frac {7} {4}} T left ( left lfloor { frac {1} {2}} n right rfloor right) + T left ( left lceil { frac {3} {4}} n right rceil right)}$ для целых чисел ${ displaystyle n> 3}$ . При применении метода Акра – Бацци первым шагом является определение значения ${ displaystyle p}$ для которого ${ displaystyle { frac {7} {4}} left ({ frac {1} {2}} right) ^ {p} + left ({ frac {3} {4}} right) ^ {p} = 1}$ . В этом примере ${ displaystyle p = 2}$ . Тогда, используя формулу, асимптотика может быть определена следующим образом:^[3]

{ Displaystyle { begin {align} T (x) & in Theta left (x ^ {p} left (1+ int _ {1} ^ {x} { frac {g (u)}) {u ^ {p + 1}}} , du right) right) & = Theta left (x ^ {2} left (1+ int _ {1} ^ {x} { frac {u ^ {2}} {u ^ {3}}} , du right) right) & = Theta (x ^ {2} (1+ ln x)) & = Тета (x ^ {2} log x). End {выравнивается}}}

Значимость

Метод Акра – Бацци более полезен, чем большинство других методов для определения асимптотического поведения, поскольку он охватывает такое большое количество случаев. Его основное применение - приближение время выполнения многих алгоритмов разделяй и властвуй. Например, в Сортировка слиянием, количество сравнений, требуемых в худшем случае, которое примерно пропорционально времени его выполнения, рекурсивно задается как ${ Displaystyle T (1) = 0}$ и

{ Displaystyle T (N) = T left ( left lfloor { frac {1} {2}} n right rfloor right) + T left ( left lceil { frac {1} { 2}} n right rceil right) + n-1}

для целых чисел ${ displaystyle n> 0}$ , и, таким образом, могут быть вычислены с использованием метода Акра – Бацци, чтобы быть ${ Displaystyle Theta (п журнал п)}$ .

Смотрите также

внешняя ссылка

O Método de Akra-Bazzi na Resolução de Equações de Recorrência (на португальском)

[:0-1] а ^б Акра, Мохамад; Бацци, Луай (май 1998 г.). «О решении линейных рекуррентных уравнений». Вычислительная оптимизация и приложения. 10 (2): 195–210. Дои:10.1023 / А: 1018373005182.

[2] «Доказательство и применение на нескольких примерах» (PDF).

[3] Кормен, Томас; Лейзерсон, Чарльз; Ривест, Рональд; Стейн, Клиффорд (2009). Введение в алгоритмы. MIT Press. ISBN 978-0262033848.

[1]

[2]

[3]