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.
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(n−i) + (n−i + 1) + (n−i + 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).
| Algo (n) |
| 1 . se n = 0 |
| 2 .ooo devolva 1 |
| 3 . x := Algo (n − 1) + n + 1 |
| 4 . devolva x |
| Algo (n) |
| 1 . se n = 0 |
| 2 .ooo devolva 0 |
| 3 . x := Algo (n − 1) + 2n − 1 |
| 4 . devolva x |
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, b e c.)
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).
What I hear, I forget.
What I see, I remember.
What I do, I understand.
— Confucius
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(2k−k) + 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.
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 | |
| = | 4 F(2k−2) + 14⋅2k + 6 | |
| = | 4 (2F(2k−3) + 7⋅2k−2 + 2) + 14⋅2k + 6 | |
| = | 8 F(2k−3) + 21⋅2k + 14 | |
| = | 23F(2k−3) + 7⋅3⋅2k + 2⋅23 − 2 | |
| = | 2kF(2k−k) + 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 n ≤ F(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 n − n lg n = 6n lg n.
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).
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.
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) = a F(n/2) + c nk. | (*) |
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 ± √)/(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 n ≥ n1. 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⌉) + c n 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) = a F(⌊n/2⌋) + c nk 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) = a F(n/b) + c nk. | (**) |
(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 = n0 b1, n0 b2, n0 b3, … 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.
Qual o consumo de tempo de cada um dos algoritmos? Qual dos algoritmo é assintoticamente mais eficiente no pior caso?