En informática , el método de Akra-Bazzi , o teorema de Akra-Bazzi , se utiliza para analizar el comportamiento asintótico de las recurrencias matemáticas que aparecen en el análisis de algoritmos de divide y vencerás donde los subproblemas tienen tamaños sustancialmente diferentes. Es una generalización del teorema maestro para las recurrencias de divide y vencerás , que asume que los subproblemas tienen el mismo tamaño. Lleva el nombre de los matemáticos Mohamad Akra y Louay Bazzi . [1]
Formulación
El método Akra – Bazzi se aplica a las fórmulas de recurrencia de la forma [1]
Las condiciones de uso son:
- se proporcionan suficientes casos base
- y son constantes para todos
- para todos
- para todos
- , donde c es una constante y O indica la notación Big O
- para todos
- es una constante
El comportamiento asintótico de se encuentra determinando el valor de para cual e insertando ese valor en la ecuación [2]
(ver Θ ). Intuitivamente, representa una pequeña perturbación en el índice de . Al notar que y que el valor absoluto de siempre está entre 0 y 1, se puede usar para ignorar la función de piso en el índice. Del mismo modo, también se puede ignorar la función de techo . Por ejemplo, y tendrá, según el teorema de Akra-Bazzi, el mismo comportamiento asintótico.
Ejemplo
Suponer se define como 1 para números enteros y para enteros . Al aplicar el método de Akra-Bazzi, el primer paso es encontrar el valor de para cual . En este ejemplo,. Luego, usando la fórmula, el comportamiento asintótico se puede determinar de la siguiente manera: [3]
Significado
El método Akra-Bazzi es más útil que la mayoría de las otras técnicas para determinar el comportamiento asintótico porque cubre una amplia variedad de casos. Su aplicación principal es la aproximación del tiempo de ejecución de muchos algoritmos de divide y vencerás. Por ejemplo, en el tipo de combinación , el número de comparaciones necesarias en el peor de los casos, que es aproximadamente proporcional a su tiempo de ejecución, se da de forma recursiva como y
para enteros , y por lo tanto se puede calcular utilizando el método de Akra-Bazzi para ser .
Ver también
Referencias
- ^ a b Akra, Mohamad; Bazzi, Louay (mayo de 1998). "Sobre la solución de ecuaciones de recurrencia lineal". Optimización Computacional y Aplicaciones . 10 (2): 195–210. doi : 10.1023 / A: 1018373005182 .
- ^ "Prueba y aplicación sobre algunos ejemplos" (PDF) .
- ^ Cormen, Thomas; Leiserson, Charles; Rivest, Ronald; Stein, Clifford (2009). Introducción a los algoritmos . Prensa del MIT. ISBN 978-0262033848.