Data: 12/03/2003
Redatora: Camila Ribeiro Rocha

Capítulo 4: Recorrências

Seção Problemas

4-4 Outros exemplos de recorrência (p. 69)
Forneça limites assintóticos superiores e inferiores para T(n) em cada uma das recorrências a seguir. Suponha que T(n) seja constante para n suficientemente pequeno. Torne seus limites tão restritos quanto possível e justifique suas respostas.

a) T(n) = 3T(n/2) + n lg n

O método escolhido foi o método mestre. Sendo assim, considerando a forma da equação padrão,

T(n) = aT(n/b) + f(n)

os valores das variáveis da equação dada são:
a = 3
b = 2
f(n) = n lg n

Observando f(n), constatou-se que a recorrência recairia no caso 1 do método mestre, que considera que f(n) = O (n^{log_ba - E}). Substituindo as variáveis,

f(n) = O (n^{log₂3 - E}) = O (n^{lg3 - E}) = O (n^{1,58 - E})

Considerando E = 0,08:

f(n) = O (n^1,5), então T(n) = THETA(n^{lg 3})

Portanto, o limite assintótico da recorrência é THETA(n^{lg 3})

f) T(n) = T(n/2) + T(n/4) + T(n/8) + n

Para obter o resultado, foi utilizado o método da árvore. A árvore resultante foi:

O número de folhas foi calculado utilizando-se a fórmula:

n° folhas = (n° de filhos)^{altura da árvore} = n^{lg 3}.

Para esse cálculo, a árvore foi considerada balanceada, uma aproximação para facilitar os cálculos (ela não é balanceada pois cada ramo cresce em uma proporção distinta). Assim, para a inserção do número de folhas na fórmula para o cálculo de recorrência, a notação THETA não poderá ser utilizada. Utilizou-se então a notação O, já que apenas o limite superior é garantido.

Extraindo as informações da árvore, tem-se a nova forma da recorrência:

T(n) = n + 7/8*n + (7/8)²*n + ... + (7/8)^i*n + O (n^lg3)

Resolvendo a recorrência:

T(n) = n + 7/8*n + (7/8)²*n + ... + (7/8)ⁱ*n + O (n^lg3)
                 _lg(n-1)
T(n) = n * Soma(7/8)ⁱ + O (n^lg3)
                         ⁱ⁼⁰
                _infinito
T(n) = n * Soma(7/8)ⁱ + O (n^lg3)
                         ⁱ⁼⁰
T(n) = n*(1 / (1 - 7/8)) + O (n^lg3)

T(n) = O (n^lg3)           (aproximadamente)

Chegou-se a um limite superior. O próximo passo é aplicar o método da substituição para tentar obter um limite mais preciso.

Supor que T(n) = O (n^c), sendo c >= 1. Neste caso, queremos mostrar que T(n) <= n^c:

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

     <= (n/2)^c + (n/4)^c + (n/8)^c + n

       = n^c * ((1/2)^c + (1/4)^c + (1/8)^c) + n

Majorando (1/2)^c + (1/4)^c + (1/8)^c, considerando que o máximo (7/8) ocorre quando c = 1:

     <= (7/8)*n^c + n

Majorando n para (1/8)n^c, o que é válido apenas para c > 1 e n >= um certo n_o

     <= (7/8)*n^c + (1/8)*n^c

     <= 1n^c          como queríamos demonstrar

 

Ainda é possível restringir mais o limite, supondo T(n) = O(n):

Suposição: T(n) <= cn

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

     <= c*(7/8)*n + n

       = (7c/8 + 1)*n

Cálculo do valor da constante c para validar a regra (7c/8 + 1)n <= cn

(7c/8 + 1)*n <= cn

7c + 8 <= c

c >= 8

Testando a constante c na relação original:

T(n) <= 8*(n/2) + 8*(n/4) + 8*(n/8) + n

         = 4n + 2n + n + n

         = 8n

Teste para o caso base:

T(1) = 1 <= 8      Sucesso

Portanto, T(n) = O(n).

O limite assintótico superior O(n) obtido também pode ser considerado o valor do limite assintótico inferior, pois a recorrência será no mínimo n (já que possui um termo desta ordem de grandeza) e no máximo 8n, como demonstrado.

Portanto, o limite assintótico da recorrência é THETA(n).

 

i) T(n) = T(n - 2) + 2 lg n

Resolvido pelo método da iteração:

T(n) = T(n - 2) + 2 lg n

       = T(n - 4) + 2 lg (n - 2) + 2 lg n

       = T(n - 6) + 2 lg (n - 4) + 2 lg (n - 2) + 2 lg n

...

Chega-se ao formato genérico:

                 _n/2
       = Soma (2 lg (n - 2i))
                ⁱ⁼¹

Retirando o somatório para o cálculo da complexidade:

       = 2[ lg n + lg (n - 2) + lg (n - 4) + ... + lg 4 + lg 2]

       = 2 lg [ n*(n - 2)*(n - 4)* ... *4*2 ]

Multiplicando e dividindo cada termo por 2:

       = 2 lg { (2n/2)*[2(n - 2)/2]*[2(n - 4)/2]* ... *[2.4/2]*[2.2/2] }

       = 2 lg { (2^n/2)*[(n/2)*(n/2 - 1)*(n/2 - 2)* ... *2*1] }

       = 2 lg [ (2^n/2)*(n/2)! ]

       = 2[ lg (2^n/2) + lg (n/2)! ]

       = 2[ n/2 + lg (n/2)! ]

       = n + 2 lg (n/2)!

      <= n + 2 THETA( (n/2) lg (n/2) )      =   THETA(n lg n)

Portanto, o limite assintótico da recorrência é THETA(n lg n).