Si encuentras algo que no entiendes puedes dejarlo en los comentarios y te responderemos tan rápido como podamos.
Solución:
Supongamos que n = 2^k;
Sabemos por series armónicas (fórmula de Euler):
Sum[i = 1 to n](1/i) ~= log(n) [n -> infinity]
t(n) = 2t(n/2) + n/log(n)
= 2(2t(n/4) + n/2/log(n/2)) + n/log(n)
= 4t(n/4) + n/log(n/2) + n/log(n)
= 4(2t(n/8) + n/4/log(n/4)) + n/log(n/2) + n/log(n)
= 8t(n/8) + n/log(n/4) + n/log(n/2) + n/log(n)
= 16t(n/16) + n/log(n/8) + n/log(n/4) + n/log(n/2) + n/log(n)
= n * t(1) + n/log(2) + n/log(4) + ... + n/log(n/2) + n/log(n)
= n(1 + Sum[i = 1 to log(n)](1/log(2^i)))
= n(1 + Sum[i = 1 to log(n)](1/i))
~= n(1 + log(log(n)))
= n + n*log(log(n)))
~= n*log(log(n)) [n -> infinity]
Cuando comience a desenrollar la recursividad, obtendrá:
Su caso base es T(1) = 1entonces esto significa que n = 2^k. Sustituyendo obtendrás:
La segunda suma se comporta igual que la serie armónica y, por lo tanto, se puede aproximar como log(k). Ahora eso k = log(n) la respuesta resultante es:
Siga el teorema de Masters extendido a continuación.
Usando el Teorema de Masters Extendido T(n)=2T(n/2)+n/logn se puede resolver fácilmente de la siguiente manera. Aquí n/log n parte se puede reescribir como n * (logn)^-1, Efectivamente haciendo valor de p=-1. Ahora el Teorema de Masters Extendido se puede aplicar fácilmente, se relacionará con el caso 2b del Teorema de Masters Extendido.
T(n)= O(nloglogn)
Siga esto para una explicación más detallada
Nos encantaría que puedieras dar visibilidad a esta reseña si lograste el éxito.