Resolver T (n) = 2T (n / 2) + log n con el método del árbol de recurrencia

9

Estaba resolviendo relaciones de recurrencia. La primera relación de recurrencia fue

T(n)=2T(n/2)+n

La solución de este puede ser encontrada por Master Theorem o el método del árbol de recurrencia. El árbol de recurrencia sería algo como esto:

! [ingrese la descripción de la imagen aquí

La solución sería:

T(n)=n+n+n+...+nlog2n=k times=Θ(nlogn)

Luego me enfrenté al siguiente problema:

T(n)=2T(n/2)+logn

Mi libro muestra que por el teorema maestro o incluso por algún enfoque de sustitución, esta recurrencia tiene la solución Θ(n). Tiene la misma estructura que el árbol anterior con la única diferencia que realiza en cada llamadalogntrabajo. Sin embargo, no puedo usar el mismo enfoque anterior para este problema.

anir
fuente

Respuestas:

5

El término no recursivo de la relación de recurrencia es el trabajo para fusionar soluciones de subproblemas. El nivelk de su árbol de recurrencia (binario) contiene 2k subproblemas con tamaño n2k, así que primero necesitas encontrar el trabajo total en el nivel k y luego resumir este trabajo en todos los niveles de los árboles.

Por ejemplo, si el trabajo es constante C, entonces el trabajo total en el nivel k estarán 2kCy el tiempo total T(n) se dará por la siguiente suma:

T(n)=k=1log2n2kC=C(2log2n+12)=Θ(n)

Sin embargo, si el trabajo crece logarítmicamente con el tamaño del problema, deberá calcular con precisión la solución. La serie sería la siguiente:

T(n)=log2n+2log2(n2)+4log2(n4)+8log2(n8)+....log2n times

Será una suma bastante compleja:

T(n)=log2n+k=1log2n2klog2(n2k)

Voy a denotar temporalmente m=log2n y simplifica la suma anterior:

k=1m2klog2(n2k)==k=1m2k(log2nk)==log2nk=1m2kk=1mk2k==log2n(2m+12)(m2m+12m+1+2)

Aquí usé una fórmula para el k=1mk2ksuma de la calculadora de álgebra simbólica en línea Wolfram | Alpha . Entonces necesitamos reemplazarm de vuelta por log2n:

T(n)=log2n+2nlog2n2log2n2nlog2n+2n2
=2nlog2n2=Θ(n)

QED

HEKTO
fuente
1
maldita sea, cometí un error súper estúpido al hacer una pregunta. Ahora corregido. Sin embargo, ahora no puedo entender cómo las cosas se cancelan entre sí en la serie:20log2n20+21log2n21+22log2n22+...+2log2nlog2n2log2n=log2n+2log2n2+4log2n4+...+nlog21.. Esta es la serie que se te ocurre, ¿verdad? Tratando conn=8, Tengo log28+2log24+4log22+8log21=3+4+4=11. ¿Qué pasa aquí?
anir
@anir - Usa la igualdad log2(n2k)=log2nk
HEKTO
1
Todavía no entendí cómo esa serie colapsa Θ(n) : '¬ (Math-noob-here ...
anir
@anir - Ampliaré mi respuesta
HEKTO
@HEKTO Si resuelve el comentario anterior, ¿aún obtiene nlog (n)? He intentado mucho ¿podrías ayudarme por favor?
roottraveller