PCC104 - Projeto e Análise de Algoritmos

PCC104 - Projeto e Análise de Algoritmos

Marco Antonio M. Carvalho

Departamento de ComputaçãoInstituto de Ciências Exatas e Biológicas

Universidade Federal de Ouro Preto

27 de agosto de 2019

Marco Antonio M. Carvalho (UFOP) PCC104 27 de agosto de 2019 1 / 28

Avisos

Site da disciplina:I http://www.decom.ufop.br/marco/

Lista de e-mails:I [email protected]

Para solicitar acesso:I http://groups.google.com/group/pcc104


http://www.decom.ufop.br/marco/

[email protected]

http://groups.google.com/group/pcc104

Na aula de hoje

1 O Teorema Mestre

2 Notação Assintótica em Funções


Avisos


Recorrências

O Teorema MestreO Teorema Mestre fornece “receitas” para resolver recorrências da forma

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

em que a ≥ 1 e b > 1 são constantes positivas e f(n) é uma funçãoassintoticamente positiva.

A recorrência acima descreve a complexidade de tempo de um algoritmo quedivide o problema original de tamanho n em a subproblemas de tamanho n/b.

Os a subproblemas são resolvidos em tempo T (n/b) cada um.

A função f(n) engloba o custo de dividir o problema original e, eventualmente,combinar os resultados dos subproblemas.

Note que n/b pode não ser inteiro, entretanto, o termo T (n/b) pode sersubstituído por T (dn/be) ou T (bn/bc) sem afetar o comportamento assintóticoda recorrência.


O Teorema Mestre

Usando o Teorema MestreO Teorema Mestre enumera três casos em que se torna fácil resolverrecorrências.

Note que não estamos interessados em obter a forma fechada para arecorrência, mas sim em seu comportamento assintótico, de maneira direta.

Isto é o contrário de quando empregamos o método de substituição, noqual encontramos a forma fechada e depois analisamos seu comportamentoassintótico.


O Teorema Mestre

TeoremaSejam a ≥ 1 e b > 1 constantes, f(n) uma função e T (n) definida sobreinteiros não negativos pela recorrência

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

em que interpretamos T (n/b) como T (dn/be) ou T (bn/bc).

Então T (n) possui os seguintes limites assintóticos:1 Se f(n) = O(nlogba−ε) para alguma constante ε > 0, então T (n) =

Θ(nlogba).2 Se f(n) = Θ(nlogba), então T (n) = Θ(nlogbalog n).3 Se f(n) = Ω(nlogba+ε) para alguma constante ε > 0 e seaf(n/b) ≤ cf(n) para alguma constante c < 1 e n suficientementegrande, então T (n) = Θ(f(n)).


O Teorema Mestre

Porquê três casos?

Nos 3 casos, comparamos uma função f(n) com a função nlogba. Acomplexidade da recorrência é determinada pela maior das duas:

1 No primeiro caso, a função nlogba é maior, portanto, T (n) =Θ(nlogba).

2 No terceiro caso, a função f(n) é maior, portanto, T (n) = Θ(f(n)).3 No segundo caso, as duas funções têm o mesmo “tamanho”. A solução

é multiplicada por um fator logarítmico, portanto, T (n) =Θ(nlogbalog n) = Θ(f(n)logn).


O Teorema Mestre

nlogba


O Teorema Mestre

Observação 1nlogba é o número de folhas da árvore de recursão a-ária gerada porT (n) = aT (n/b) + f(n).

Observação 2No caso 2, multiplicamos f(n) (equivalente a nlogba) por logn para indicarque o custo f(n) se dá a cada nível da árvore mostrada anteriormente.


Teorema Mestre

Função Polinomialmente MaiorUma função f(n) é polinomialmente maior que outra função g(n) sepudermos achar algum ε > 0 tal que f(n)

g(n) = nε.

Exemplo: n2 é polinomialmente maior que n. No entanto, nlogn e 2n nãosão polinomialmente maiores que n.

Função Polinomialmente MenorUma função f(n) é polinomialmente menor que outra função g(n) sepudermos achar algum ε > 0 tal que g(n)

f(n) = nε.

Função Assintoticamente IgualUma função f(n) é assintoticamente igual a outra função g(n) selim

(f(n)g(n)

)= 1, quando n tende ao infinito.


Teorema Mestre

Observação Sobre o Caso 1A função f(n) não deve ser apenas menor do que nlogba, deve serpolinomialmente menor do que nlogba.

Em outras palavras,nlogba/f(n) = nε

f(n) deve ser assintoticamente menor que nlogba por um fator nε, paraalguma constante ε > 0.


Teorema Mestre

Condição de RegularidadeA condição de regularidade estabelece que af(n/b) ≤ cf(n) paraalguma constante c < 1 e para todo n suficientemente grande.

Isto é, para n tendendo ao infinito, há uma constante c (0 < c < 1) tal queaf(n/b) ≤ cf(n).

A condição de regularidade sempre é satisfeita quando T (n) é uma funçãomonotonicamente não decrescente (por exemplo 2n, n2, logn, n!, etc.).

Algumas funções de n (tais como sen(n) e cos(n)) não monotonicamentenão decrescentes, e não satisfazem a condição de regularidade.

Em problemas reais e de interesse prático, o tempo de execução nuncadecresce quando n cresce.


Teorema Mestre

Observação Sobre o Caso 3A função f(n) não deve ser apenas maior do que nlogba, deve serpolinomialmente maior do que nlogba, ou seja:

f(n)/nlogba = nε

f(n) deve ser assintoticamente maior que nlogba por um fator nε, paraalguma constante ε > 0.

Ainda, f(n) deve satisfazer a condição de “regularidade”

af(n/b) ≤ cf(n)

para alguma constante c < 1 e n suficientemente grande.

A condição de regularidade é satisfeita pela maioria das funções polinomiaisque encontraremos.


Teorema Mestre

Observação GeralExistem casos não cobertos para f(n) pelo Teorema Mestre:I Entre os casos 1 e 2, existem funções f(n) que são menores quenlogba, mas não são polinomialmente menores;

I Entre os casos 2 e 3, existem funções f(n) que são maiores quenlogba, mas não são polinomialmente maiores.

Se f(n) cai em um destes casos, ou não atende à condição de regularidadedo caso 3, então não é possível aplicar o Teorema Mestre.


Teorema Mestre

Exemplo 1T (n) = 9T (n/3) + n

I a = 9;I b = 3;I f(n) = n.

Logo, nlogba = nlog39 = Θ(n2).

Como f(n) = O(nlog39−ε), onde ε = 1, podemos aplicar o caso 1 doTeorema Mestre e concluir que a solução da recorrência é

T (n) = Θ(n2)


Teorema Mestre

Exemplo 1T (n) = 9T (n/3) + n

I a = 9;I b = 3;I f(n) = n.

Logo, nlogba = nlog39 = Θ(n2).

Como f(n) = O(nlog39−ε), onde ε = 1, podemos aplicar o caso 1 doTeorema Mestre e concluir que a solução da recorrência é

T (n) = Θ(n2)


Teorema Mestre

Exemplo 2T (n) = T (2n/3) + 1

I a = 1;I b = 3/2;I f(n) = 1.

Logo, nlogba = nlog3/21 = n0 = 1.

Como f(n) = Θ(nlogba) = Θ(1), podemos aplicar o caso 2 do TeoremaMestre e concluir que a solução da recorrência é

T (n) = Θ(log n)


Teorema Mestre

Exemplo 2T (n) = T (2n/3) + 1

I a = 1;I b = 3/2;I f(n) = 1.

Logo, nlogba = nlog3/21 = n0 = 1.

Como f(n) = Θ(nlogba) = Θ(1), podemos aplicar o caso 2 do TeoremaMestre e concluir que a solução da recorrência é

T (n) = Θ(log n)


Teorema Mestre

Exemplo 3T (n) = 3T (n/4) + n log n

I a = 3;I b = 4;I f(n) = n log n.

Logo, nlogba = nlog43 = n0,793.

Como f(n) = Ω(nlog43+ε), em que ε ≈ 0, 2, podemos aplicar o caso 3 doTeorema Mestre se provarmos que a condição de regularidade é verdadeirapara f(n):

af(n/b) = 3(n/4)log(n/4) ≤ (3/4)n log n = cf(n)

para c = 3/4. Desta forma, podemos aplicar o caso 3 do Teorema Mestre econcluir que a solução da recorrência é

T (n) = Θ(n log n)


Teorema Mestre


I a = 3;I b = 4;I f(n) = n log n.

Logo, nlogba = nlog43 = n0,793.

Como f(n) = Ω(nlog43+ε), em que ε ≈ 0, 2, podemos aplicar o caso 3 doTeorema Mestre se provarmos que a condição de regularidade é verdadeirapara f(n):

af(n/b) = 3(n/4)log(n/4) ≤ (3/4)n log n = cf(n)

para c = 3/4. Desta forma, podemos aplicar o caso 3 do Teorema Mestre econcluir que a solução da recorrência é

T (n) = Θ(n log n)


Teorema Mestre


I a = 2;I b = 2;I f(n) = n log n.

Logo, nlogba = nlog22 = n.

Embora f(n) seja assintoticamente maior do que nlogba, não épolinomialmente maior.

A razão f(n)/nlogba = (n log n)/n = log n é assintoticamente menor doque nε para qualquer constante positiva ε.

Desta forma, a recorrência cai entre os casos 2 e 3 e não pode ser resolvidapelo Teorema Mestre.


Teorema Mestre


I a = 2;I b = 2;I f(n) = n log n.

Logo, nlogba = nlog22 = n.

Embora f(n) seja assintoticamente maior do que nlogba, não épolinomialmente maior.

A razão f(n)/nlogba = (n log n)/n = log n é assintoticamente menor doque nε para qualquer constante positiva ε.

Desta forma, a recorrência cai entre os casos 2 e 3 e não pode ser resolvidapelo Teorema Mestre.


Teorema Mestre

Equações InadimissíveisI T (n) = 2nT

(n2

)+ nn: a não é constante – o número de

subproblemas deve ser fixo;I T (n) = 2T

(n2

)+ n

logn : A razão entre f(n) e nlogb a não é polinomial;

I T (n) = 0, 5T(n2

)+ n: a < 1 implica em menos do que um

subproblema;I T (n) = 64T

(n8

)− n2 log n: f(n) < 0 implica em tempo de

combinação negativo;I T (n) = T

(n2

)+ n(2− cosn): não atende a condição de regularidade.


Notação Assintótica em Funções

UtilizaçãoComumente, manipulamos a notação assintótica em expressõesmatemáticas.

Por exemplo, considerando a notação O, podemos escrever quen = O(n2).a

Em outro exemplo, temos que 2n2 + 3n+ 1 = 2n2 + Θ(n).

É necessário termos em mente o abuso de notação que fazemos em relaçãoà notação assintótica: = significa ∈.

Adicionalmente, é necessário lembrar que o sinal = é unidirecional.aO que é verdade, porém, impreciso.



Interpretação Lado DireitoCaso a notação assintótica apareça sozinha no lado direito de umaigualdade, temos que o lado esquerdo é membro do conjunto do ladodireito.

Por exemplo, n = O(n2) significa n ∈ O(n2) ou n ⊆ O(n2).

Note que não se escrevem igualdades em que a notação assintótica aparecesozinha do lado esquerdo.

Por exemplo, seria possível concluir erroneamente que n2 = n a partir deO(n2) = n.



Interpretação Lado Direito pt. 2Utilizamos a notação assintótica em substituição a uma função que nãonecessita ser definida precisamente.

Por exemplo,2n2 + 3n+ 1 = 2n2 + Θ(n)

significa2n2 + 3n+ 1 = 2n2 + f(n)

em que f(n) é alguma função pertencente ao conjunto Θ(n).

De fato, f(n) = 3n+ 1 pertence a Θ(n).



ConclusãoA utilização de notação assintótica em expressões nos permite abstrairdetalhes não essenciais.

Este é o caso na análise do comportamento assintótico de equações derecorrência, em que ignoramos os termos de mais baixa ordem. Porexemplo, em

T (n) = 2T (n− 1) + Θ(n)

entende-se que os termos de mais baixa ordem estão incluídos em umafunção f(n) ∈ Θ(n).



Interpretação Lado EsquerdoA notação assintótica também pode aparecer do lado esquerdo de umaigualdade, como em

2n2 + Θ(n) = Θ(n2)

Interpretamos estes casos da seguinte maneira:I Existe uma função f(n) para o lado esquerdo da igualdade tal que

existe uma função g(n) para o lado direito que torna a igualdadeválida.

I O lado direito da igualdade é definido menos precisamente do que olado esquerdo, conforme nos dois exemplos abaixo:

2n2 + 3n+ 1 = 2n2 + Θ(n)

2n2 + Θ(n) = Θ(n2)



Interpretação Lado Esquerdo pt. 22n2 + 3n+ 1 = 2n2 + Θ(n)

2n2 + Θ(n) = Θ(n2)

As duas equações dos exemplos anteriores podem ser interpretadasconforme descrito:

I A primeira equação diz que existe uma função f(n) ∈ Θ(n) tal que2n2 + 3n+ 1 = 2n2 + f(n) para todo n.

I A segunda equação diz que para qualquer função g(n) ∈ Θ(n), existeuma função h(n) ∈ Θ(n2) tal que

2n2 + g(n) = h(n)para todo n.

Note que isto implica em 2n2 + 3n+ 1 = Θ(n2), que é exatamente o queas duas equações dizem.


Teorema Mestre

ExercíciosAplique o Teorema Mestre ou prove não ser possível:

1 T (n) = 4T (n/2) + n;2 T (n) = 4T (n/2) + n2;3 T (n) = 4T (n/2) + n3;4 T (n) = 2T (n/2) + Θ(n);5 T (n) = 8T (n/2) + Θ(n2) //Multiplicação de Matrizes;6 T (n) = 7T (n/2) + Θ(n2) //Multiplicação de Strassen.


Dúvidas?


Documents

PCC104 - Projeto e Análise de Algoritmos