Cómo resolver esta recurrencia $T(n)=2T(n/2)+n/\log n$

Question

¿Cómo puedo solucionar la relación de recurrencia $$T(n)=2T\left(\frac n2\right)+\frac{n}{\log n}$ $?

Estoy atrapado después de unos pasos...

Llego hasta

$$T(n) = 2^k T(1) + \sum_{i=0}^{\log(n-1)} \left(\frac{n}{\log n} - i\right)$$

¿Cómo simplificar esta suma de log?

Answer 1

$$ S (k) = 2 ^ {-k} \cdot T(2^k) \implies S (k) = S (k-1) + \frac1 {k\log2} $$ $$ S (k) = S (0) + \frac {H_k} {\log2} \implies T(2^k) = \Theta (2 ^ k k\cdot\log) $$... Que no implica que el $T(n)=\Theta(n\cdot\log\log n)$, aunque esta podría ser la conclusión sugerida en tu libro de texto.

Answer 2

Supongamos que usted ha $T(0) = 0$ $T(1) = 1$ y una recurrencia de $n\ge 2$ es $$T(n) = 2 T(\lfloor n/2 \rfloor) + \frac{n}{\lfloor\log_2 n\rfloor}.$$ Esto le da la siguiente exacto de la fórmula para $T(n)$ donde $n\ge 2:$ $$T(n) = 2^{\lfloor \log_2 n \rfloor} + \sum_{j=0}^{\lfloor \log_2 n \rfloor - 1} \frac{1}{\lfloor \log_2 n \rfloor - j} \sum_{k=j}^{\lfloor \log_2 n \rfloor} d_k 2^k$$ donde suponemos que la representación binaria de $n$ es $$n = \sum_{k=0}^{\lfloor \log_2 n \rfloor} d_k 2^k.$$ El lector está invitado a verificar esta fórmula, que no es en absoluto difícil.

Ahora, para un límite superior considere una cadena de uno de los dígitos que da $$T(n) \le 2^{\lfloor \log_2 n \rfloor} + \sum_{j=0}^{\lfloor \log_2 n \rfloor - 1} \frac{1}{\lfloor \log_2 n \rfloor - j} \sum_{k=j}^{\lfloor \log_2 n \rfloor} 2^k \\ = 2^{\lfloor \log_2 n \rfloor} + \sum_{j=0}^{\lfloor \log_2 n \rfloor - 1} \frac{1}{\lfloor \log_2 n \rfloor - j} (2^{\lfloor \log_2 n \rfloor+1} - 2^j) \\= 2^{\lfloor \log_2 n \rfloor} + 2^{\lfloor \log_2 n \rfloor+1} \sum_{j=0}^{\lfloor \log_2 n \rfloor - 1} \frac{1}{\lfloor \log_2 n \rfloor - j} - \sum_{j=0}^{\lfloor \log_2 n \rfloor - 1} \frac{2^j}{\lfloor \log_2 n \rfloor - j} \\= 2^{\lfloor \log_2 n \rfloor} + 2^{\lfloor \log_2 n \rfloor+1} H_{\lfloor \log_2 n \rfloor} - \sum_{j=1}^{\lfloor \log_2 n \rfloor} \frac{2^{\lfloor \log_2 n \rfloor - j}}{j} \\= 2^{\lfloor \log_2 n \rfloor} + 2^{\lfloor \log_2 n \rfloor+1} H_{\lfloor \log_2 n \rfloor} - 2^{\lfloor \log_2 n \rfloor} \sum_{j=1}^{\lfloor \log_2 n \rfloor} \frac{2^ {j}}{j}.$$ Observe que la suma restante término converge a un número, de manera que obtenemos la siguiente asymptotics para el límite superior: $$2^{\lfloor \log_2 n \rfloor} (1+2H_{\lfloor \log_2 n \rfloor} -\log 2).$$ Este límite superior es realmente alcanzado y por lo tanto no pueden ser mejorados, como el límite inferior, a la que ahora nos calcular y que se produce por un dígito, seguido por una cadena de dígitos cero, dando $$ T(n) \ge 2^{\lfloor \log_2 n \rfloor} + \sum_{j=0}^{\lfloor \log_2 n \rfloor - 1} \frac{1}{\lfloor \log_2 n \rfloor - j} 2^{\lfloor \log_2 n \rfloor} = 2^{\lfloor \log_2 n \rfloor} (1+H_{\lfloor \log_2 n \rfloor}).$$ Unirse a la dominante en términos de la parte superior y el límite inferior tenemos una complejidad de $$\Theta\left(2^{\lfloor \log_2 n \rfloor} \times H_{\lfloor \log_2 n \rfloor}\right) = \Theta\left(2^{\log_2 n} \log \log n\right)= \Theta\left(n\log \log n\right).$$

Este MSE enlace apunta a una cadena de cálculos similares.

Answer 3

Su suma está mal, y debe de haber reemplazado $k$ $log(n)$ en su última expresión.

Aquí se detallan los pasos de esta relación de recurrencia:

$$ \\ T(n) = 2T(\frac{n}{2}) + \frac{n}{\log n} \\ T(n) = 2(2T(\frac{n}{4}) + \frac{\frac{n}{2}}{\log \frac{n}{2}}) + \frac{n}{\log n} = 2^2T(\frac{n}{2^2}) + \frac{n}{\log(n) - 1} + \frac{n}{\log n} \\ T(n) = 2(2(2T(\frac{n}{8}) + \frac{\frac{n}{4}}{\log \frac{n}{4}}) + \frac{\frac{n}{2}}{\log \frac{n}{2}}) + \frac{n}{\log n} = 2^3T(\frac{n}{2^3}) + \frac{n}{\log(n) - 2} + \frac{n}{\log(n) - 1} + \frac{n}{\log n} \\ ... \\ T(n) = 2^kT(\frac{n}{2^k}) + \sum_{i = 0}^{ k - 1}\frac{n}{\log(n) - i} \\ \text{Si } \frac{n}{2^k} = 1 \Rightarrow n = 2^k \Rightarrow k = \log_2(n) \\ T(n) = 2^{\log_2(n)}T(1) + \sum_{i = 0}^{ \log_2(n) - 1}\frac{n}{\log(n) - i} \\ T(n) = \Theta (n) + \sum_{i = 0}^{ \log_2(n) - 1}\frac{n}{\log_2(n) - i} \\ T(n) \approx \Theta (n) + \sum_{j = 1}^{ \log_2(n)}\frac{n}{j} \\ T(n) \approx \Theta (n) + nH_{\log_2(n)} \\ T(n) \approx \Theta (n) + n \ln(\log_2(n)) \\ \text{Y, finalmente,} T(n)\ \en \Theta(n \ln(\log_2(n))) $$