Método Akra-Bazzi para encontrar las complejidades temporales

El teorema de Master es un método popular para resolver recurrencias de complejidad temporal de la forma:

$T(n) = aT(\frac{n}{b}) + f(n)$

Con restricciones sobre a, b y f(n). La forma de relación de recurrencia limita la usabilidad del teorema de Master. Las siguientes son tres recurrencias que no se pueden resolver directamente usando el teorema de Master:

$\large{T(n) = 3T(\frac{n}{5}) + 2T(\frac{n}{5}) + \theta(n)}$
$\large{T(n) = \frac{1}{3}T(\frac{n}{3}) + \theta(\frac{1}{n})}$
$\large{T(n) = 9T(\frac{n}{3}+\log n) + \theta(n)}$

Método Akra-Bazzi : este artículo explora otro método para resolver tales recurrencias que fue desarrollado por Mohammad Akra y Louay Bazzi en 1996 . El método de Akra-Bazzi se puede aplicar a las recurrencias de la siguiente forma:

$T(n)=\sum_{i=1}^{k} a_{i} T(b_{i}n+h_{i}(n))+g(n)$

donde, $a_{i}$ y $b_{i}$ son constantes tales que:

$\ a_{i}>0$

$\ 0<b_{i}<1 \textnormal{ i.e. in the range (0, 1)}$

$\ g(n)\ \epsilon\ O(n^{c}) \textnormal{ i.e. }g(n) \textnormal{ must have a polynomial upperbound}$

$\ h_{i}(x)\ \epsilon\ O(\large\frac{n}{(logn)^{2}}\normalsize)$

A continuación, encuentre p tal que

$\large{\sum_{i=1}^k a_ib_i^p=1}$

Después

$\large{T(n)\epsilon\ \theta(n^{p}(1+\int_{1}^{n}\frac{g(u)}{u^{p+1}}du))}$

Ejemplos
Consideremos las tres recurrencias discutidas anteriormente y resolvámoslas usando el método:

Ejemplo 1.

$\large{T(n) = 3T(\frac{n}{5}) + 2T(\frac{n}{5}) + \theta(n)}$

Aquí

un ₁ = 3

segundo ₁ = $\large \frac{1}{5}$

un ₂ = 2

b ₂ = $\large \frac{1}{5}$

b ₁ y b ₂ están en el rango (0, 1)

g(n) = \theta(n) que es O(n ^c ), aquí c puede ser 1.

En este problema h ₁ (n) y h ₂ (n) no están presentes.
Aquí p=1 satisface

$3*\large {\frac{1}{5}^p}\normalsize +2*\large {\frac{1}{5}^p}\normalsize=1.$

Finalmente,

=> $n^{1}(1+\int_{1}^{n}\large\frac{u}{u^{1+1}}\normalsize du)$

=> $n(1+\log{n}-\log{1})$

=> $n+n\log{n}$

=> $\theta(n\log{n})$

Ejemplo 2.

$\large{T(n) = \frac{1}{3}T(\frac{n}{3}) + \theta(\frac{1}{n^{2}})}$

Aquí

un = $\large \frac{1}{3}$

segundo = $\large \frac{1}{3}$

g(n) = $\theta(n^2)$

b está en el rango (0, 1)

g(n) = \theta(n^2) que está en O(n ^c ), aquí c puede ser 1.

En este problema h(n) no está presente.
Aquí p= – 1 satisface

$\large\frac{1}{2}\normalsize*\large\frac{1}{2}^p\normalsize=1$

Finalmente,

=> $n^{-1}(1+\int_{1}^{n}\large\frac{\frac{1}{u}}{u^{-1+1}}\normalsize du)$

=> $\large\frac{1}{n}\normalsize(1+\int_{1}^{n}\large\frac{1}{u}\normalsize du)$

=> $\large\frac{1}{n}\normalsize(1+[\log u]_{1}^{n})$

=> $\large\frac{1}{n}\normalsize(1+\log n)$

=> $\theta(\large\frac{\log n}{n}\normalsize)$

Ejemplo 3.

$\large{T(n) = 9T(\frac{n}{3}+\log n) + \theta(n)}$

Aquí

un = 9

segundo = $\large\frac{1}{3}$

g(n) = \theta(n) $\theta(n)$

b está en el rango (0, 1)

g(n) = $\theta(n)$ que es O(n ^c ), aquí c puede ser 1.

h(n) = $\log{n}$ que es $O(\large\frac{n}{(logn)^{2}}\normalsize)$

Aquí p=2 satisface

$9*\large\frac{1}{3}^p\normalsize=1$

Finalmente,

=> $n^{2}(1+\int_{1}^{n}\large\frac{u}{u^{2+1}}\normalsize du)$

=> $n^{2}(1+\int_{1}^{n}\large\frac{1}{u^{2}}\normalsize du)$

=> $n^{2}(1+[-\large\frac{1}{u}\normalsize]_{1}^{n})$

=> $n^{2}(2-\large\frac{1}{n}\normalsize)$

=> $2n^{2}-n$

=> $\theta(n^{2})$

ventajas:

Funciona para muchos algoritmos de divide y vencerás.
Tiene una restricción menor sobre el formato de la recurrencia que el Teorema de Master.
p se puede calcular utilizando métodos numéricos para relaciones de recurrencia complejas.

Desventajas:

No funciona cuando el crecimiento de g(n) no es un polinomio acotado. Por ejemplo g(N) = 2 ^N .
No se ocupa de las funciones de techo y suelo.

Publicación traducida automáticamente

Artículo escrito por sakharamgawade1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta Cancelar la respuesta