cómo resolver la recurrencia $T(n) = 2T(n/3) + n\log n$

Question

¿Cómo resolvemos la recurrencia $T(n) = 2T(n/3) + n\log n$ ?

Además, ¿es posible resolver esta recurrencia por el método Maestro?

Answer 1

Pista: Se puede resolver mediante Teorema maestro .

Un método más genérico es Akra Bazzi pero no lo necesitas para este problema.

Answer 2

Para aplicar el Teorema Maestro definimos $a=2$ , $b=3$ y $f\left(n\right)=n\lg n$

Desde [ $n^{log_{3}2+0.4}\approx n$ ], tenemos que $f\left(n\right)=\Omega\left(n^{log_{b}a+\epsilon}\right)$ , donde $\epsilon=0.4$ . La condición de regularidad en $f\left(n\right)$ se verificará si, para algún $c<1$ : $$2\frac{n}{3}\lg\left(n/3\right)\leq cn\lg(n)$$ Puesto que está claro que $\left(\frac{2}{3}\right)n\left(\lg n-\lg3\right)<\left(\frac{2}{3}\right)n\lg(n)$ la constante $c=\frac{2}{3}<1$ es tal que la condición de regularidad se cumple para n suficientemente grande. Así, el caso 3 del Teorema Maestro y $T\left(n\right)=\Theta\left(n\lg n\right)$ contestando a la pregunta.

Answer 3

Existe otra recurrencia estrechamente relacionada que admite una solución exacta exacta. Supongamos que tenemos $T(0)=0$ y $T(1)=T(2)=1$ y para $n\ge 3$ $$T(n) = 2 T(\lfloor n/3 \rfloor) + n \lfloor \log_3 n \rfloor.$$

Además, dejemos que la representación de base tres de $n$ sea $$n = \sum_{k=0}^{\lfloor \log_3 n \rfloor} d_k 3^k.$$

Entonces podemos desenrollar la recurrencia para obtener lo siguiente exacto fórmula para $n\ge 3$ $$T(n) = 2^{\lfloor \log_3 n \rfloor} + \sum_{j=0}^{\lfloor \log_3 n \rfloor -1} 2^j \times (\lfloor \log_3 n \rfloor - j) \times \sum_{k=j}^{\lfloor \log_3 n \rfloor} d_k 3^{k-j}.$$

Ahora para obtener un límite superior considere una cadena de dos dígitos para obtener $$T(n) \le 2^{\lfloor \log_3 n \rfloor} + \sum_{j=0}^{\lfloor \log_3 n \rfloor -1} 2^j \times (\lfloor \log_3 n \rfloor - j) \times \sum_{k=j}^{\lfloor \log_3 n \rfloor} 2 \times 3^{k-j}.$$ Esto se simplifica a $$(9 \lfloor \log_3 n \rfloor - 18) \times 3^{\lfloor \log_3 n \rfloor} + 17 \times 2^{\lfloor \log_3 n \rfloor} + \lfloor \log_3 n \rfloor + 2.$$

Este límite se alcanza realmente y no puede mejorarse, al igual que el límite inferior, que se produce con un dígito uno seguido de ceros para dar $$T(n) \ge 2^{\lfloor \log_3 n \rfloor} + \sum_{j=0}^{\lfloor \log_3 n \rfloor -1} 2^j \times (\lfloor \log_3 n \rfloor - j) \times 3^{\lfloor \log_3 n \rfloor-j}.$$ Esto se simplifica a $$(3 \lfloor \log_3 n \rfloor - 6) \times 3^{\lfloor \log_3 n \rfloor} + 7 \times 2^{\lfloor \log_3 n \rfloor}.$$

Uniendo los términos dominantes de los límites superior e inferior obtenemos la asíntota $$\lfloor \log_3 n \rfloor \times 3^{\lfloor \log_3 n \rfloor} \in \Theta\left(\log_3 n \times 3^{\log_3 n}\right) = \Theta\left(\log n \times n\right).$$

Obsérvese que existe un término de orden inferior $$2^{\lfloor \log_3 n \rfloor} \in \Theta\left(3^{\log_3 2 \times \log_3 n}\right) = \Theta\left(n^{\log_3 2}\right).$$

Este término representa la asíntota generada por la recursividad de la recurrencia.

Ambos coinciden con lo que produciría el teorema del Maestro.

Este Enlace MSE tiene una serie de cálculos similares.