Combinar análisis de complejidad de tiempo de tipo

Question

¿Cómo puedo probar que $T(n) = 2T(n/2) + n$ es $O(n \log n)$?

Answer 1

Que $L(k)=T(2^k)$ y $n = 2^k$. $L(k)=T(n)$, $L(k-1)=T(n/2)$ Y $L(k)=2L(k-1)+2^k$. Por lo tanto, $$ \begin{align} L(1) &= 2\;L(0) + 2^1 \\ L(2) &= 2\;L(1) + 2^2 \\ &= (2^2\;L(0) + 2^2) +2^2 \\ L(3) &= 2\;L(2) + 2^3 \\ &= (2^3\;L(0)+2^3+2^3)+2^3 \\ L(4) &= 2\;L(3) + 2^4 \\ &= (2^4\;L(0)+2^4+2^4+2^4)+2^4 \\ &\dots \\ L(k) &= 2^k\;L(0) + k\;2^k \\ &\text{or}\\ T(n) &= n\;T(1) + \log_2(n)\;n \\ &\text{when }n\text{ is a power of }2 \end {Alinee el} $$ % Por lo tanto, $T(n)=O(n\log(n))$.

Answer 2

T(1) = 1

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

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

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

T(n) = 2 [2T (n/4) + c (n/2)] + cn

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

Manera similar, T(n) = 8T (n/8) + 3cn

General T(n) = 2 ^ k T (n/2 ^ K) + CNK

(n/2 ^ k) = 1

n = 2 ^ k

k = log n de base2

enchufe en k en la fórmula general

T(n) = T(1) n + cn logBase2n

T(n) = Thetha(n log n) grande

Answer 3

SUGERENCIA:

Utilizar la inducción para mostrar que hay constantes $c$y $n_0$ s.t. $T(n) \leq c \cdot n \log n \quad\forall n \geq n_0$. Utilizar $T(2)$ como el caso base. Recordar registro fresco propiedades para reducir el logaritmo y utilizar la hipótesis de inducción.

Publicar su progreso si te quedas atascado.

Answer 4

Hay dos ideas para ello. La primera de ellas es telescópica donde recurrentemente se utiliza la definición de $T(n)$ o supuesto podría utilizar la inducción (esto casi siempre funciona). Para un bosquejo de la página prueba 3 aquí. Tenga en cuenta que aquí se supone que $n$ es una potencia de 2 que la prueba sea más sencillo, si no va sin embargo de la misma manera.

Answer 5

Utilizar el Teorema maestro.