Recorrências

Para analisar o consumo de tempo de um algoritmo recursivo é necessário resolver uma recorrência. (Veja, por exemplo, a análise do algoritmo de ordenação por inserção.)  Uma recorrência (= recurrence) é uma expressão que dá o valor de uma função num dado ponto em termos dos valores da mesma função em pontos anteriores. Por exemplo,

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

é uma recorrência que dá o valor de F(n) em termos de F(n−1).  (Podemos supor 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. (No exemplo acima, poderíamos 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 de seu argumento (e sem subexpressões da forma + … + ou contendo ou ). Tipicamente, a fórmula fechada é uma combinação de polinômios, quocientes de polinômios, logaritmos, exponenciais, etc.

Exemplo A

Comecemos com uma exemplo muito simples. Considere a seguinte recorrência em que n é inteiro positivo:

  F(n) = F(n−1) + n + 1 . (A.1)

Há uma infinidade de funções F que satisfazem a recorrência. A tabela abaixo sugere uma dessas funções:

n 0 1 2 3 4 5
F(n) 1 3 6 10 15 21

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

n 0 1 2 3 4 5
F(n) 10 12 15 19 24 30

De modo mais geral, é evidente que para cada número i existe uma (e uma só) função F definida sobre os inteiros positivos que satisfaz a recorrência (A.1) e tem valor inicial F(0) = i.

Resolver a recorrência é uma arte nem sempre fácil. O primeiro truque na nossa caixa de ferramentas consiste em desenrolar a recorrência:

F(n) = F(n−1) + n + 1
  = F(n−2) + (n−1) + 1 + n + 1
  = F(n−2) + (n−1) + n + 2
  = F(n−3) + (n−2) + 1 + (n−1) + n + 2
  = F(n−3) + (n−2) + (n−1) + n + 3
  = F(n−4) + (n−3) + (n−2) + (n−1) + n + 4
 
  = F(ni) + (ni + 1) + (ni + 2) + … + (n−1) + n + i

O processo de desenrolar a recorrência revelou um padrão. Esse padrão permite concluir que F(n) = F(0) + 1 + 2 + … + (n−2) + (n−1) + n + n. Se o valor inicial é F(0) = 1 então

F(n) = 1 + n(n+1)/2 + n
  = ½ (n² + 3n + 2) .

Esta fórmula fechada é a solução da recorrência (A.1).

Exercícios 1

  1. Que número o seguinte devolve ao receber um número natural n?
    Algo (n)
    1 . se n = 0
    2 .ooo devolva 1
    3 . x := Algo (n − 1) + n + 1
    4 . devolva x
  2. Que número o seguinte devolve ao receber um número natural n?
    Algo (n)
    1 . se n = 0
    2 .ooo devolva 0
    3 . x := Algo (n − 1) + 2n − 1
    4 . devolva x

Exemplo B

Considere novamente a recorrência que aparece na introdução desta página para n = 2, 3, 4, etc.:

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

Se adotarmos o valor inicial F(1) = 1, teremos a seguinte função definida no conjunto {1, 2, 3, 4, … }:

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

Gostaríamos de obter uma fórmula fechada para a recorrência. O segundo truque na caixa de ferramentas do resolvedor de recorrências é adivinhar e depois verificar por indução matemática. Algo me diz que a solução da recorrência é

  F(n)  = 3n²/2 + 7n/2 − 4 . (B.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 (B.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 suspeitado. A fórmula (B.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 (B.2).  De modo mais geral, se adotarmos o valor inicial F(1) = i, teremos a fórmula fechada 3n²/2 + 7n/2 + i − 5, que não é muito diferente de (B.2).

Exercícios 2

  1. Prove por indução que 1 + n(n+1)/2 + n é solução da recorrência (A.1) para o valor inicial F(0) = 1.
  2. Mostre que 3n²/2 + 7n/2 + i − 5 é a solução sa recorrência (B.1) para o valor inicial F(1) = i.
  3. Seja T uma função definida sobre os números naturais maiores que 3. Suponha que e T(4) = 100 e T(n) = T(n−1) + n + 1 para todo n maior que 4. Mostre, por indução, que T(n) ≤ n² + 84 para todo n ≥ 4. Mostre, por indução, que T(n) ≥ n²/2 para todo n ≥ 4.
  4. ★ Considere a recorrência T(n) = 2 T(n − 1) + 3 para n ≥ 1. Qual a solução da recorrência a partir do valor inicial T(0) = 3?
  5. 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) = 2n − 1.
  6. Números de Fibonacci.  Considere a recorrência f(n) = f(n − 1) + f(n − 2) para n = 2, 3, 4, …  Seja φ o número (1 + √5)/2 e mostre que a função f(n) = φn satisfaz a recorrência. Os números Fibonacci são dados pelo recorrência F(n) = F(n − 1) + F(n − 2) com valores iniciais F(0) = 0 e F(1) = 1. Mostre que F(n) = Θ(φn).
  7. Considere recorrência f(n) = n · f(n − 1) para todo n natural. Dê uma fórmula fechada para a função definida por essa recorrência com valor inicial f(0) = 1.

Exemplo C

Considere agora um tipo diferente de recorrência, que define F(n) em termos de F(n/2):

  F(n)  =  F(n/2) + 3 . (C.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 não pertence a esse conjunto quando n não é o dobro de um número par. 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, então

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 + 3
  = F(2k−3) + 3 + 3 + 3
  = F(2kk) + 3k.
  = F(20) + 3k .

Como F(20) = 5 e k = lg n, temos

  F(n) = 5 + 3 lg n (C.2)

para n = 20, 21, 22, 23, etc. Esta é uma solução da recorrência (C.1) quando o valor inicial é 5. Para outros valores iniciais, a fórmula é semelhante.

Exercícios 3

  1. Confira e fórmula (C.2) por indução em n.
  2. Encontre uma fórmula fechada para a recorrência (C.1) com valor inicial F(20) = i.
  3. Mostre que F(n) = lg n + 3 para n = 20, 21, 22, 23, …  satisfaz a recorrência F(n) = F(n/2) + 1.

Exemplo D

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 (D.1)

para n = 22, 23, 24, etc.  (Observe que a recorrência faz sentido pois, 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 (D.2)

para toda potência n de 2 a partir de 20. (Por via das dúvidas, convém conferir (D.2) por indução. Eu fiz isso e agora estou tranquilo: a fórmula está correta.)

Uma observação final: No contexto da análise de algoritmos, a fórmula fechada (D.2) traz informação demais, é excessivamente detalhada. É suficiente saber que

  6n lg nF(n) ≤ 8n lg n (D.3)

para toda potência n de 2 a partir de 23. Para verificar a segunda desigualdade, basta observar que 7n lg n + 3n − 2 ≤ 7n lg n + 3n 7n lg n + n lg n = 8n lg n. Para verificar a primeira desigualdade, basta observar que 7n lg n + 3n − 2 ≥ 7n lg n − 2 ≥ 7n lg nn lg n = 6n lg n.

Exercícios 4

  1. ★ Verifique a fórmula (D.2) por indução.
  2. Mostre a partir de (D.3) que F(n) = Ο(n lg n) e F(n) = Ω(n lg n).
  3. Considere a recorrência F(n) = 2 F(n/2) + n com n =  21, 22, 23, …  Resolva a recorrência adotando F(1) = 1.
  4. 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. Encontre uma fórmula fechada para G.

Exemplo E

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 (E.1)

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 complexa. 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. (E.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

e portanto a desigualdade (E.2) está correta, CQD.

É possível mostrar também que T(n) ≥ 6n lg n para todo natural n ≥ 2. Podemos resumir esta cota inferior e a cota superior (E.2) dizendo que T(n) = Θ(n lg n).  Embora isso não seja evidente, é fato que T(n) = Θ(n lg n) qualquer que seja o valor de T(1).

Exercícios 5

  1. Na prova da fórmula (E.2) por indução, por que não adotar n = 1 como base da indução? Por que não começar o passo da indução com n = 3?
  2. Considere a recorrência (E.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.
  3. Considere a recorrência (E.1). Prove que T(n) ≥ 6n lg n para todo natural n ≥ 2.
  4. Seja T uma função definida sobre os números naturais positivos. Suponha que T satisfaz a recorrência (E.1), e tem valor inicial T(1) = 99. Mostre que T(n) = Ο(n lg n). [Dica]
  5. Resolva a recorrência T(n) = 2T(⌊n/2⌋) + 7n.
  6. 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 F(n) = F(3n/4) + 88.
  7. 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) = Ο(lg n). [Dica]
  8. Seja S a função sobre os números naturais maiores que ou iguais a 4 definida pelas seguintes condições: S(4) = 11 e S(n) = n + S(⌊n/2⌋) para todo n > 4. O que há de errado nessa definição?
  9. Método de interpolação para solução de recorrências.  A recorrência (D.1) é a restrição de (E.1) às potências de 2. Por isso, é muito mais fácil resolver (D.1) que (E.1). Como já observamos, a solução de (D.1) satisfaz as cotas 6n lg n F(n) ≤ 8n lg n para n = 23, 24, 25, etc.  Deduza daí que a solução de (E.1) satisfaz as cotas n lg n T(n) ≤ 32n lg n para todo natural n suficientemente grande. Faça isso sem recorrer à indução matemática que provou (E.2). (Sugestão: Comece por mostrar que a solução de (E.1) é crescente.) [Solução]

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ências nem admitem fórmula fechada.)  Felizmente, a análise de algoritmos fica satisfeita com uma boa cota superior. Assim, no exemplo E acima, é suficiente determinar a ordem Ο a que pertence a solução T da recorrência (E.1). Ou seja, é suficiente saber que

T(n) = Ο(n lg n).

(Mas não faz sentido tentar provar isso diretamente a partir de (E.1), sem passar por (E.2).)  A propósito, considerações análogas valem para cotas inferiores de soluções de recorrências: é suficiente saber a ordem Ω a que a solução de uma recorrência pertence.

Como mostram alguns dos exercícios abaixo, é mais fácil obter e provar uma cota (superior ou inferior) que uma fórmula fechada exata.

Exercícios 5

  1. Seja T uma função definida sobre os números naturais. Suponha que T satisfaz a recorrência (E.1). Mostre que T(n) = Ω(n lg n). [Dica]
  2. Considere a recorrência F(n) = F(n−1) + 2n para todo número natural n ≥ 2. Mostre que F(n) = Ο(n²). Mostre que F(n) = Ω(n²). (Você pode supor que F(1) = 1, embora isso não afete o resultado.)  [Dica]
  3. Considere a recorrência F(n) = 4 F(n/2) + n. Mostre que F(n) = Ω(n²). Mostre que F(n) = Ο(n²). [Dica]
  4. Considere a recorrência F(n) = 3 F(n/2) + n. Mostre que F(n) = Ω(nlg 3). Mostre que F(n) = Ο(nlg 3). [Dica]
  5. 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) = Θ(n²)?  É verdade que F(n) = Θ(n!)?

Teorema Mestre

Muitas das recorrências que ocorrem na análise de algoritmos de divisão e conquista têm a seguinte forma (com a, c e k constantes):

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

O Teorema Mestre enunciado a seguir dá a solução assintótica de todas essas recorrências. (Esse teorema é vagamente análogo à fórmula x = (− b ± √b² − 4ac)/(2a) que dá todas as soluções da equação ax² + bx + c = 0.)

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,

(Observe que lg a > k equivale a a > 2k.)

Exemplo 1:  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.)  Nessas condições, F é não decrescente e portanto o teorema garante que F(n) = Θ(nlg 3).

Exemplo 2:  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) = aF(n/2⌋) + cnk  para todo n ≥ 1. Nessas condições, F é não decrescente e portanto o teorema garante que F(n) = Θ(nlg a).

Generalização.  O Teorema Mestre pode ser generalizado como segue para resolver recorrências da forma

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

(Veja a seção 4.7 de Brassard & Bratley 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,

(Observe que lg a / lg b > k equivale a a > bk.)

Akra e Bazzi descobriram (1998) uma generalização interessante do Teorema Mestre que permite resolver uma classe maior de recorrências.

Exercícios 7

  1. Mostre que a primeira versão do Teorema Mestre é um caso particular do teorema generalizado.
  2. Mostre que lg a / lg b = logba. Mostre que lg a / lg b > k se e somente se a > bk.
  3. Considere recorrência T(n) = T(⌊n/2⌋) + T(⌈n/2⌉) + 2n² para todo número natural n ≥ 2. Adote o valor inicial T(1) = 0. Mostre como o Teorema Mestre pode ser usado para determinar a classe Θ a que T pertence. Confirme esse resultado por indução.
  4. Seja T uma função que leva números naturais em números reais e satisfaz a recorrência  T(n) = 8 T(⌊n/2⌋) + n³.  Mostre que T(n) = Θ(n³ lg n).
  5. Seja T uma função que leva números naturais em números reais e satisfaz a recorrência  T(n) = 7 T(⌊n/2⌋) + n³.  Mostre que T(n) = Θ(n³).
  6. ★ O tamanho das instâncias de um certo problema é medido por um parâmetro n. Tenho três algoritmos — A, BC — para o problema:
    • o algoritmo A divide cada instância do problema em cinco subinstâncias (veja a página Divisão e conquista) de tamanho n/2⌋, resolve as subinstâncias e então combina as soluções em tempo Ο(n);
    • o algoritmo B divide cada instância do problema em duas subinstâncias de tamanho n−1, resolve as subinstâncias e então combina as soluções em tempo Ο(1);
    • o algoritmo C divide cada instância do problema em nove subinstâncias de tamanho n/3⌋, resolve as subinstâncias e então combina as soluções em tempo Ο(n²).

    Qual o consumo de tempo de cada um dos algoritmos? Qual dos algoritmo é assintoticamente mais eficiente no pior caso?