Análise e Projeto de Algoritmos - ufjf.br · quocientes de polinômios, logaritmos, exponenciais, etc.) Programa de Pós-Graduação em Ciência da Computação – DCC – UFJF

Análise e Projeto de Algoritmos

Prof. Eduardo Barrére

[email protected]

www.ufjf.br/pgccwww.dcc.ufjf.br

Programa de Pós-Graduação em Ciência da Computação – DCC – UFJF APA / Barrére

Solução de recorrências

Para analisar o consumo de tempo de um algoritmo recursivo énecessário resolver uma recorrência. Por exemplo,

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

podemos supor, por exemplo, que n = 2,3,4,5,… e F(1) = 1;

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".

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.)



Considere a recorrência: F(n) = F(n−1) + 3n + 2 Há uma infinidade de funções F que satisfazem a recorrência.

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

ou

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.


Solução de recorrências 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, a solução da recorrência (F(n) = F(n−1) + 3n + 2) é:

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

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 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

Pista: F(n) poderia ser da forma an²+bn+c e usamos a tabela de valores de F(n) para calcular a, b e c.)

Prove que se adotarmos o valor inicial F(1) = i, teremos a fórmula fechada 3n²/2 + 7n/2 + i − 5.


Solução de recorrências Considere a recorrência:

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

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


Solução de recorrênciasF(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(2k−k) + 3xk= F(20) + 3xk= 5 + 3k

Como k = lg n, temos: F(n) = 5 + 3 lg n



Suponha que F é uma função definida no conjunto {20, 21, 22, 23, …} sobre a qual sabemos apenas que:

F(1) = 1 e

F(n) = 2 F(n/2) + 7n + 2, para n = 21, 22, 23, 24, etc.

Vamos tentar 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 …


Solução de recorrênciasF(1) = 1 e F(n) = 2 F(n/2) + 7n + 2, para n = 21, 22, 23, 24, etc.

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

Para encontrar uma fórmula fechada, escrevendo 2k no lugar de n: F(n) = F(2k)

= 2F(2k−1) + 7×2k + 2 (2 F(n/2) + 7n + 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(2k−k) + 7k2k + 2×2k − 2 (trocando o 3 por k)= 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


Solução de recorrências 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(piso(n/2)) + 7n + 2 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


Solução de recorrênciasT(n) = 2 T(piso(n/2)) + 7n + 2 T(n) ≤ 10 n lg n

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 piso(n/2) (note que piso(n/2) ≥ 2). Então: T(n) = 2T(piso(n/2) + 7n + 2

≤ 2(10 piso(n/2) lg(piso(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 dizendo que T(n) está em Ο(n lg n).

Ordem O de uma recorrência Considerações análogas valem para cotas inferiores (ordem Ω) de soluções de

recorrências.


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 n ≥ n1. Nessas condições,

se lg a > k então F está em Θ(nlg a) , se lg a = k então F está em Θ(nk lg n) , se lg a < k então F está em Θ(nk) .


Teorema Mestre

Exemplo: 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) = 1F(piso(n/2)) + 2 F(teto(n/2)) + cn para todo n ≥ 2.(algoritmo de Karatsuba e Ofman: multiplicar dois

números naturais )

Nessas condições, F é não decrescente e portanto o teorema garante que F está em Θ(nlg 3).


Teorema MestreGeneralização O "teorema mestre" pode ser generalizado em:

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

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,

se lg a / lg b > k então F está em Θ(nlg a / lg b) , se lg a / lg b = k então F está em Θ(nk lg n) , se lg a / lg b < k então F está em Θ(nk) .


Exemplo de recursividade

No caso da recursividade, depende da quantidade de iterações que se pode chegar

Ex.: se eu quiser saber os N primeiros termos de um fatorial, a complexidade é N

Function Fatorial (N: Integer): Integer;Begin

If n=0 then Fatorial := 1Else

Fatorial := N + Fatorial (N-1)End;



FatorialO(n) = 1, se n = 0

= O(n-1) + 1, se n > 1

mas quanto é O(n-1) ?



= (O(n-1)) + 1= (O(n-2) + 1) + 1= O(n-2) + 2= (O(n-3) + 1) + 2= O(n-3) + 3..... forma geral, O(n) = O(n-k) + k, 1 k n Como k é o número do fatorial, fazendo n = k,

reduzimos a O(n) = n


Casos: Cota superior ou limite superior (upperbound)

Seja dado um problema, por exemplo, multiplicação de duas matrizes quadradas n x n.

Conhecemos um algoritmo para resolver este problema (pelo método trivial) de complexidade O(n3).

Sabemos assim que a complexidade deste problema não deve superarO(n3), uma vez que existe um algoritmo que o resolve com esta complexidade.

Uma cota superior ou limite superior (upper bound) deste problema éO(n3).

O(n3)

A cota superior de um problema pode mudar se alguém descobrir um outro algoritmo melhor.


O Algoritmo de Strassen reduziu a complexidade para O(nlog 7). Assim a cota superior do problema de multiplicação de matrizes passou a ser O(nlog 7).

O(nlog 7) O(n3)

Coppersmith e Winograd melhoraram ainda para O(n2.376).

O(n2.376) O(nlog 7) O(n3)

Note que a cota superior de um problema depende do algoritmo. Pode diminuir quando aparece um algoritmo melhor.

Cota superior (upper bound)


Cota superior: Analogia com record A cota superior para resolver um problema é análoga ao record mundial

de uma modalidade de atletismo. Ele é estabelecido pelo melhor atleta (algoritmo) do momento. Assim como o record mundial, a cota superior pode ser melhorada por um algoritmo (atleta) mais veloz.

“Cota superior” da corrida de 100 metros rasos:


Caso: Seqüência de Fibonacci

Para projetar um algoritmo eficiente, é fundamental preocupar-se com a sua complexidade. Como exemplo: considere a seqüência de Fibonacci.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...

A seqüência pode ser definida recursivamente:0 if n = 0

Fn = 1 if n = 1Fn-1 + Fn-2 if n > 1

Dado o valor de n, queremos obter o n-ésimo elemento da seqüência.


Fibonacci: Algoritmo 1: função fibo1(n)Seja a função fibo1(n) que calcula o n-ésimo elemento da seqüência de Fibonacci. Input: Valor de n Output: O n-ésimo elemento da seqüência de Fibonacci

Function fibo1(n)1: if n = 0 then2: return 03: else4: if n = 1 then5: return 16: else7: return fibo1(n - 1) + fibo1(n - 2)8: end if9: end if

Experimente rodar este algoritmo para n = 100 A complexidade é O(2n). (Mesmo se uma operação levasse um picosegundo, 2100 operações levariam

tempo “pra caramba” !!!!)


Fibonacci: Algoritmo 2: função fibo2(n)Function fibo2(n)1: if n = 0 then2: return 03: else4: if n = 1 then5: return 16: else7: penultimo = 08: ultimo = 19: for i = 2 until n do10: atual = penultimo + ultimo11: penultimo = ultimo12: ultimo = atual13: end for14: return atual15: end if16: end if

A complexidade agora passou de O(2n) para O(n).

Desafio: fazer em O(log n)


Cota inferior (lower bound)

As vezes é possível demonstrar que, para um dado problema, qualquer que seja o algoritmo a ser usado, o problema requer pelo menos um certo número de operações.

Essa complexidade é chamada cota inferior (lower bound) do problema.

Note que a cota inferior depende do problema mas não do particular algoritmo.


Cota inferior para multiplicação de matrizes

Para o problema de multiplicação de matrizes quadradas n x n, apenas para ler os elementos das duas matrizes de entrada ou para produzir os elementos da matriz produto leva tempo O(n2). Assim uma cota inferior trivial é (n2).

Na analogia anterior, uma cota inferior de uma modalidade de atletismo não dependeria mais do atleta. Seria algum tempo mínimo que a modalidade exige, qualquer que seja o atleta. Uma cota inferior trivial para os 100 metros rasos seria o tempo que a velocidade da luz leva para percorrer 100 metros no vácuo.


Meta: aproximando as duas cotas

Se um algoritmo tem uma complexidade que é igual à cota inferior do problema, então ele é assintoticamente ótimo.

O algoritmo de Coppersmith e Winograd é de O(n2.376) mas a cota inferior (conhecida até hoje) é de Ω(n2).

Portanto não podemos dizer que ele é ótimo. Pode ser que esta cota superior possa ainda ser melhorada.

Pode também ser que a cota inferior de Ω(n2) possa ser melhorada (isto é “aumentada”). Para muitos problemas interessantes, pesquisadores dedicam seu tempo tentando encurtar o intervalo (“gap”) até encostar as duas cotas.

Documents

Análise e Projeto de Algoritmos - ufjf.br · quocientes de polinômios, logaritmos, exponenciais, etc.) Programa de Pós-Graduação em Ciência da Computação – DCC – UFJF