MAC0338/lista3.md

3.

Qunado ele faz refeência a memória, ele está querendo dizer o tamanho da pilha de execução. Ou seja, cada vez que chammos a recursão uma nova função é achamada e o consumo de memória aumenta. Pra resolver esse problema, vamos sempre iniciar a recursão na menor parte:

QUICKSORTE2 (A, p, r)
    meio = (p+r)/2
    enqunato p < r
        q <- particiona(A, p, r)
        se q >= meio
            QUICKSORTE2 (A, p, q-1)
            p <- q + 1
        senao
            QUICKSORTE2 (A, q+1, r)
            r <- q - 1

Note que o pior caso para a memória com esse algorítmo não será quando q estiver na posição r-1. O pior caso vai se dar quando q se encontrar no meio. Nesse caso (M é a qunatida de memória):

$$M(1) = 1$$ $$M(n) = M(n/2)$$

Aviso, o particiona é $O(n)$, no entanto ele consome $O(1)$ em memória. Desenvolvendo pelo método da substitituição:

$$M(n) = a + M(n/2) = a + a + M(n/2) = ia + M(\frac{n}{2^i})$$

$$M(n) = ia + M(\frac{n}{2^i})$$

Suponha que n seja multiplo de 2, ou seja, $n = 2^i$. Dessa forma:

$$M(n) = ia + M(1) = ia + 1 = lg \space n + 1$$

Vaja que no pior caso o nosso consumo de memória $O(lg \space n)$.

Vamos provar por indução que estamos certo. Lembre que a nossa hiótese é: $M(n) =lg \space n + 1$. Para a base, a demonstração é trivial.

$$M(n) = M(n/2)$$

Pela hipótese de indução:

$$M(n) = lg \space \frac{n}{2} + 1 + 1 = lg \space n + 1 $$