Solução de recorrências

Para analisar o consumo de tempo de um algoritmo recursivo é necessário resolver uma recorrência.   Uma recorrência é uma expressão que dá o valor de uma função em termos dos valores "anteriores" da mesma função.  Por exemplo,

F(n)  =  F(n−1) + 3n + 2

é uma recorrência que dá o valor de F(n) em relação a F(n−1).  (Quais os valores de n?  No presente caso, podemos supor, por exemplo, que n = 2,3,4,5,… )   Uma recorrência pode ser vista como um algoritmo recursivo que calcula uma função a partir de um "valor inicial".  (Na ilustração acima, podemos, por exemplo, tomar F(1) = 1 como valor inicial.)

Uma recorrência é satisfeita por muitas funções diferentes, uma para cada valor inicial; mas todas essas funções são, em geral, do mesmo "tipo".  As funções que nos interessam são, via de regra, definidas no conjunto dos números naturais, mas podem ser definida em outros conjuntos (como os naturais maiores que 99, as potências inteiras de 2, as potências inteiras de 1½, os racionais maiores que ½, etc.).

Resolver uma recorrência é encontrar uma "fórmula fechada" que dê o valor da função diretamente em termos do seu argumento.  (Tipicamente, a fórmula fechada é uma combinação de polinômios, quocientes de polinômios, logaritmos, exponenciais, etc.)

Veja o verbete Recurrence relation na Wikipedia.

Exemplo 1

Considere a recorrência

  F(n)  =  F(n−1) + 3n + 2 (1.1)

e suponha que n pertence ao conjunto {2,3,4,…}.  Há uma infinidade de funções F que satisfazem a recorrência.  A tabela abaixo sugere uma dessas funções:

n 1 2 3 4 5 6
F(n) 1 9 20 34 51 71

A tabela seguinte sugere outra função que satisfaz a recorrência:

n 1 2 3 4 5 6
F(n) 10 18 29 43 60 80

De modo mais geral, é evidente que para cada número i existe uma (e uma só) função F definida sobre {1,2,3,4,…} que tem valor inicial F(1) = i e satisfaz a recorrência (1.1).

Gostaríamos de obter uma fórmula fechada para a recorrência.  Nosso primeiro "método" consiste em adivinhar e depois verificar por indução. Para o valor inicial F(1) = 1, algo me diz que a solução da recorrência (1.1) é

  F(n)  =  3n²/2 + 7n/2 − 4 . (1.2)

Eis a confirmação desta suspeita, por indução em n:  Para n = 1 é fácil verificar que a fórmula está correta.  Agora tome n > 1 e suponha que a fórmula (1.2) vale com n−1 no lugar de n.  Então

F(n) = F(n−1) + 3n + 2
  = 3(n−1)²/2 + 7(n−1)/2 − 4 + 3n + 2
  = (3n² − 6n + 3 + 7n − 7 − 8 + 6n + 4)/2
  = (3n² + 7n − 8)/2
  = 3n²/2 + 7n/2 − 4 ,

como eu havia previsto.  A fórmula (1.2) está confirmada!   (Como adivinhei a fórmula correta?  Isto não interessa no momento, mas posso dar uma pista: eu suspeitei que F(n) é da forma an²+bn+c e usei a tabela de valores de F(n) para calcular a, bc.)

Se adotarmos o valor inicial F(1) = 99, teremos a fórmula fechada 3n²/2 + 7n/2 + 94, que não é muito diferente de (1.2).   De modo mais geral, se adotarmos o valor inicial F(1) = i, teremos a fórmula fechada 3n²/2 + 7n/2 + i − 5.

Exercícios

  1. Mostre que  3n²/2 + 7n/2 + i − 5  é uma solução para a recorrência (1.1) para o valor inicial F(1) = i.

Exemplo 2

Considere a recorrência

  F(n)  =  F(n/2) + 3 . (2.1)

Não faz sentido tomar n no conjunto {2,3,4,5,…} pois n/2 não pertence a esse conjunto quando n é ímpar.  Também não faz sentido tomar n no conjunto {2,4,6,8,…} pois (n/2)/2 não pertence a esse conjunto quando n/2 é ímpar.  A recorrência faz sentido, entretanto, se n pertence ao conjunto {21, 22, 23, 24, … } das potências inteiras de 2.  Nesse caso, podemos reescrever a recorrência assim:

F(2k) = F(2k−1) + 3

para k = 1,2,3,4,…  Há muitas funções F definidas sobre as potências inteiras de 2 que satisfazem essa recorrência.  Para cada número i, há uma (e uma só) função F que satisfaz a recorrência e tem valor inicial F(20) = i.  Se i = 5, por exemplo, teremos

n 1 2 4 8 16
F(n) 5 8 11 14 17

Para obter uma fórmula fechada, podemos "desenrolar" a recorrência:

F(2k) = F(2k−1) + 3
  = F(2k−2) + 3×2
  = F(2k−3) + 3×3
  = F(2kk) + 3k
  = F(20) + 3k
  = 5 + 3k .

Como k = lg n, temos

  F(n) = 5 + 3 lg n . (2.2)

Esta é uma solução da recorrência (2.1).  Para outros valores iniciais, a fórmula não será muito diferente de (2.2).

Exercícios

  1. Calcule uma fórmula fechada para a recorrência (2.1) com valor inicial F(20) = i.
  2. Mostre que  F(n) = lg n + 3  para n = 20, 21, 22, 23, … é uma solução da recorrência  F(n) = F(n/2) + 1.

Exemplo 3

Suponha que F é uma função definida no conjunto {20, 21, 22, 23, …} sobre a qual sei apenas que F(1) = 1 e

  F(n)  =  2 F(n/2) + 7n + 2 (3.1)

para n = 22, 23, 24, etc.  (Observe que a recorrência (3.1) faz sentido: para todo n em {21, 22, 23, …}, o número n/2 está no domínio da função.)  Eu gostaria de obter uma fórmula fechada para F.

É útil começar calculando os valores de F(n) para valores pequenos de n:

n 1 2 4 8 16
F(n) 1 18 66 190 494

Para encontrar uma fórmula fechada, podemos "desenrolar" a recorrência, escrevendo 2k no lugar de n:

F(n) = F(2k)
  = 2F(2k−1) + 7×2k + 2
  = 2 (2F(2k−2) + 7×2k−1 + 2) + 7×2k + 2
  = 4F(2k−2) + 14×2k + 6
  = 4 (2F(2k−3) + 7×2k−2 + 2) + 14×2k + 6
  = 8F(2k−3) + 21×2k + 14
  = 23F(2k−3) + 7×3×2k + 2×23 − 2
  = 2kF(2kk) + 7k2k + 2×2k − 2
  = 2kF(1) + 7k2k + 2×2k − 2
  = 2k + 7k2k + 2×2k − 2
  = 7k2k + 3×2k − 2 .

Como k = lg n, a fórmula fechada pode ser reescrita assim:

  F(n)  =  7n lg n + 3n − 2 . (3.2)

(Por via das dúvidas, convém conferir (3.2) por indução. Eu fiz isso e agora estou tranquilo: a fórmula está certa.)

Exercícios

  1. Verifique a fórmula (3.2) por indução.
  2. Considere a recorrência F(n) = 2F(n/2) + n com n =  21, 22, 23, …  Resolva a recorrência adotando F(1) = 0.
  3. Sabe-se que G é uma função definida no conjunto {20, 21, 22, 23, …} tal que G(1) = 5 e G(n) = 2G(n/2) + 7n para n > 1.  Determine uma fórmula fechada para G.

Exemplo 4

Seja T uma função definida no conjunto {1, 2, 3, 4, 5, …} sobre a qual sei apenas que T(1) = 1 e

  T(n)  =  2 T(⌊n/2⌋) + 7n + 2 (4.1)

(veja definição de piso) para n = 2, 3, 4, 5, …   Eis os valores da função para valores pequenos de n:

n 1 2 3 4 5
T(n) 1 18 25 66 73

Uma fórmula fechada exata para T é provavelmente muito complicada.  Por isso, ficaremos satisfeitos com uma boa cota superior.  O exemplo anterior sugere que T(n) fica abaixo de um múltiplo de n lg n.  Para verificar essa suspeita, vamos mostrar que, para todo natural n ≥ 2,

  T(n)  ≤  10 n lg n . (4.2)

Prova, por indução em n:  Se n = 2, a desigualdade está satisfeita pois o lado esquerdo vale 18 e o lado direito vale 20.  Se n = 3, a desigualdade está satisfeita pois o lado esquerdo vale 25 e o lado direito vale mais que 30.  Agora tome n > 3 e suponha, como hipótese de indução, que a desigualdade vale se trocarmos n por ⌊n/2⌋  (note que n/2⌋ ≥ 2 e portanto a recorrência está definida para ⌊n/2⌋).  Então

T(n) = 2T(⌊n/2⌋) + 7n + 2
  2(10 ⌊n/2⌋ lg ⌊n/2⌋) + 7n + 2
  20 (n/2) lg(n/2) + 7n + 2
  = 10n (lg n − lg 2) + 7n + 2
  = 10n lg n − 10n + 7n + 2
  = 10n lg n − 3n + 2
  10n lg n .

Podemos resumir a cota (4.2) dizendo que T(n) está em Ο(n lg n).   [Mas não faz o menor sentido tentar provar isso sem passar por (4.2).]  Embora isso não seja evidente, é fato que T(n) estará em Ο(n lg n) qualquer que seja o valor de T(1).

Exercícios

  1. Considere a recorrência (4.1).  Prove que  T(n) ≤ 8n lg n  para todo n ≥ 5.  Tente usar a mesma técnica para provar que  T(n) ≤ 7n lg n  para todo n ≥ 100, supondo que a desigualdade vale para n = 100,101,…,199.   Tente usar a mesma técnica para provar que  T(n) ≤ 100n  para todo n ≥ 1000, supondo que a desigualdade vale para n = 1000,1001,…,1999.  
  2. Suponha que uma função T satisfaz a recorrência (4.1) e tem valor incial T(1) = 99.  Mostre que T(n) está em Ο(n lg n).  [Dica]
  3. Resolva a recorrência T(n) = 2T(⌊n/2⌋) + 7n.
  4. Considere a recorrência F(n) = F(3n/4) + 88.  Exiba e prove uma fórmula fechada para a função F que está definida sobre as potências inteiras de 4/3, tem F(1) = 77 e satisfaz a recorrência.
  5. Seja F a função definida assim:  F(1) = 77  e  F(n) = F(⌊3n/4⌋) + 88  para todo natural n > 1.  Mostre que F(n) está em Ο(lg n).  [Dica]

Ordem O de uma recorrência

Muitas vezes é difícil obter uma fórmula fechada exata para a função que satisfaz uma recorrência.  (Algumas recorrência nem admitem fórmula fechada.)  Felizmente, a análise de algoritmos fica satisfeita com uma boa cota superior.  Assim, no exemplo 4 acima, é perfeitamente satisfatório determinar a qual ordem Ο pertence a função T que satisfaz a recorrência (4.1):

T(n)  está em  Ο(n lg n) .

Considerações análogas valem para cotas inferiores (ordem Ω) de soluções de recorrências.

Mais exercícios

  1. Seja T uma função que leva números naturais em números reais.  Suponha que T satisfaz a recorrência (4.1).  Mostre que T(n) está em Ω(n lg n).  [Dica]
  2. Seja F a função definida assim:  F(1) = 1  e  F(n) = F(n−1) + F(n−2) + … + F(1) + n  para todo natural n > 1.  Mostre que F(n) está em Ο(2n).  Mostre que F(n) está em Ω(2n).  [Dica]
  3. Considere a recorrência F(n) = F(n−1) + 2n.  Observe que ela faz sentido para todo número natural n ≥ 2.  Mostre que F(n) está em Ο(n²).  Mostre que F(n) está em Ω(n²).  (Você pode supor que F(1) = 1, embora isso não afete o resultado.)  [Dica]
  4. Considere a recorrência  F(n) = 4 F(n/2) + n.  Mostre que F(n) está em Ω(n²).  Mostre que F(n) está em Ο(n²).  [Dica]
  5. Considere a recorrência  F(n) = 3 F(n/2) + n.  Mostre que F(n) está em Ω(nlg 3).  Mostre que F(n) está em Ο(nlg 3).  [Dica]
  6. Seja F a função que satisfaz as seguintes condições:  F(1) = 0  e  F(n) = nF(n−1) + n  para n = 2,3,4,…  É verdade que F(n) está em Θ(n²)? É verdade que F(n) está em Θ(n!)?

Teorema mestre

Muitas das recorrências que ocorrem na análise de algoritmos de divisão e conquista têm a forma

  F(n)  =  a F(n/2) + cnk . (*)

O seguinte "teorema mestre" dá a solução (em termos assintóticos) de todas essas recorrências.

Teorema:  Sejam a um número natural não nulo, k um número natural, e c um número real positivo.  Seja F uma função que leva números naturais em números reais positivos e satisfaz a recorrência (*) para n = 21, 22, 23, …  Suponha que F é assintoticamente não decrescente, ou seja, que existe n1 tal que F(n) ≤ F(n+1) para todo nn1.  Nessas condições,

Exemplo A:  Seja c um número real positivo e F uma função que leva números naturais em números reais positivos.  Suponha que  F(n) = F(⌊n/2⌋) + 2 F(⌈n/2⌉) + cn  para todo n ≥ 2.  (Esta recorrência aparece na análise do algoritmo de Karatsuba e Ofman.)  Nessas condições, F é não decrescente e portanto o teorema garante que F está em Θ(nlg 3).

Exemplo B:  Sejam a e k números naturais tais que a > 2k e seja c > 0 um número real.  Seja F é uma função que leva números naturais em números reais positivos e satisfaz a recorrência  F(n) = a F(n/2⌋) + cnk  para todo n ≥ 1.  Nessas condições, F é não decrescente e portanto o teorema garante que F está em Θ(nlg a).

Generalização

O "teorema mestre" pode ser generalizado como segue para tratar de recorrências como

  F(n)  =  a F(n/b) + cnk . (**)

(Veja a seção 4.7 de BB e a seção 4.4 de CLRS.)

Teorema generalizado:  Sejam a ≥ 1, b ≥ 2, k ≥ 0 e n0 ≥ 1 números naturais e seja c > 0 um número real.  Seja F é uma função que leva números naturais em números reais positivos e satisfaz a recorrência (**) para n = n0b1, n0b2, n0b3, …   Suponha ainda que F é assintoticamente não decrescente.  Nessas condições,

Exercícios

  1. Seja T uma função que leva números naturais em números reais e satisfaz a recorrência  T(n) = 8T(⌊n/2⌋) + n³.  Mostre que T está em Θ(n³ lg n).
  2. Seja T uma função que leva números naturais em números reais e satisfaz a recorrência  T(n) = 7T(⌊n/2⌋) + n³.  Mostre que T está em Θ(n³).

Valid HTML 4.01 Strict Valid CSS!