aula07 NotacaoTetaOmegaEtc

Prévia do material em texto

Universidade Federal de Alfenas
Projeto e Análise de Algoritmos
Aula 07 – Notações θ, Ω, ω, ο
humberto@bcc.unifal-mg.edu.br
Última aula
Notação O
• Uma função f(n) domina assintoticamente outra função 
g(n) se existem duas constantes positivas 
▫ c e n0
Última aula
Notação O
• Uma função f(n) domina assintoticamente outra função 
g(n) se existem duas constantes positivas 
▫ c e n0
• tais que, para qualquer 
▫ n >= n0, 
Última aula
Notação O
• Uma função f(n) domina assintoticamente outra função 
g(n) se existem duas constantes positivas 
▫ c e n0
• tais que, para qualquer 
▫ n >= n0, 
• temos 
▫ g(n) <= c . f(n)
Outras notações
• Assim como a notação O fornece uma maneira 
assintótica de dizer que uma função é “menor ou igual 
a”outra, existem outras notação que fornecem outras 
conclusões sobre a complexidade de algoritmos;
Outras notações
• Assim como a notação O fornece uma maneira 
assintótica de dizer que uma função é “menor ou igual 
a”outra, existem outras notação que fornecem outras 
conclusões sobre a complexidade de algoritmos;
▫ Θ
Outras notações
• Assim como a notação O fornece uma maneira 
assintótica de dizer que uma função é “menor ou igual 
a”outra, existem outras notação que fornecem outras 
conclusões sobre a complexidade de algoritmos;
▫ Θ
▫ Ω
Outras notações
• Assim como a notação O fornece uma maneira 
assintótica de dizer que uma função é “menor ou igual 
a”outra, existem outras notação que fornecem outras 
conclusões sobre a complexidade de algoritmos;
▫ Θ
▫ Ω
▫ ω
Outras notações
• Assim como a notação O fornece uma maneira 
assintótica de dizer que uma função é “menor ou igual 
a”outra, existem outras notação que fornecem outras 
conclusões sobre a complexidade de algoritmos;
▫ Θ
▫ Ω
▫ ω
▫ ο
Notação Ω 
Notação Ω
• A notação Ω é bem parecida com a notação O;
▫ „O‟ define um limite assintótico superior, e;
▫ Ω define um limite assintótico inferior.
Notação Ω
• A notação Ω é bem parecida com a notação O;
▫ „O‟ define um limite assintótico superior, e;
▫ Ω define um limite assintótico inferior.
• Exemplos:
)( 34 nn 
Notação Ω
• A notação Ω é bem parecida com a notação O;
▫ „O‟ define um limite assintótico superior, e;
▫ Ω define um limite assintótico inferior.
• Exemplos:
)( 34 nn 
)1(n
Notação Ω
• A notação Ω é bem parecida com a notação O;
▫ „O‟ define um limite assintótico superior, e;
▫ Ω define um limite assintótico inferior.
• Exemplos:
)( 34 nn 
)1(n
))(log()log(3 nn 
Notação Ω
• A notação Ω é bem parecida com a notação O;
▫ „O‟ define um limite assintótico superior, e;
▫ Ω define um limite assintótico inferior.
• Exemplos:
)( 34 nn 
)1(n
))(log()log(3 nn 
)1(1 
Notação Ω
• A notação Ω é bem parecida com a notação O;
▫ „O‟ define um limite assintótico superior, e;
▫ Ω define um limite assintótico inferior.
• Exemplos:
)( 34 nn 
)1(n
))(log()log(3 nn 
)1(1 
)2(! nn 
Notação Ω
}nnf(n) g(n)c| 
ne c{f(n):(g(n)) 
0
0
0 
0


• Limite assintótico inferior
Notação Ω
• Limite assintótico inferior
Notação Ω
• Na prática a notação Ω não é vista sozinha em análises 
de algoritmos;
Notação Ω
• Na prática a notação Ω não é vista sozinha em análises 
de algoritmos;
▫ Pelo motivo de não interessar para a análise de algoritmos;
Notação Ω
• Na prática a notação Ω não é vista sozinha em análises 
de algoritmos;
▫ Pelo motivo de não interessar para a análise de algoritmos;
▫ A notação O possui sua importância, pois o programador conclui 
que seu algoritmo é no máximo tão complexo a uma função. 
Notação Ω
• Na prática a notação Ω não é vista sozinha em análises 
de algoritmos;
▫ Pelo motivo de não interessar para a análise de algoritmos;
▫ A notação O possui sua importância, pois o programador conclui 
que seu algoritmo é no máximo tão complexo a uma função. 
▫ Mas no mínimo tão complexo, como a notação Ω descreve, não é 
importante para conclusões práticas sobre algoritmos.
Notação Ω
• Na prática a notação Ω não é vista sozinha em análises 
de algoritmos;
▫ Pelo motivo de não interessar para a análise de algoritmos;
▫ A notação O possui sua importância, pois o programador conclui 
que seu algoritmo é no máximo tão complexo a uma função. 
▫ Mas no mínimo tão complexo, como a notação Ω descreve, não é 
importante para conclusões práticas sobre algoritmos.
• Ω vem na maioria das vezes acompanhada a notação Θ;
▫ Como um complemento na análise, nunca sozinha...
Notação θ
• Conhecida também como “limite firme” ou “limite assintoticamente 
restrito”.
Notação θ
• Conhecida também como “limite firme” ou “limite assintoticamente 
restrito”.
• A notação O, apesar de fornecer informações sobre a complexidade do 
algoritmo, nem sempre nos revela algo importante;
Notação θ
• Conhecida também como “limite firme” ou “limite assintoticamente 
restrito”.
• A notação O, apesar de fornecer informações sobre a complexidade do 
algoritmo, nem sempre nos revela algo importante;
• Não faz sentido, para algum algoritmo, dizer que suas complexidade é 
por exemplo O(n!). 
▫ Ou faz?
Notação θ
• Conhecida também como “limite firme” ou “limite assintoticamente 
restrito”.
• A notação O, apesar de fornecer informações sobre a complexidade do 
algoritmo, nem sempre nos revela algo importante;
• Não faz sentido, para algum algoritmo, dizer que suas complexidade é 
por exemplo O(n!). Ou faz?
• Exemplos da falta de precisão de O:
Notação θ
)!(
)2(
)(
)(
)(
)(
1000
5
4
3
nOn
On
nOn
nOn
nOn
nOn
n






Notação θ
• Uma função f(n) pertence ao conjunto θ(g(n)) se existem 
constantes positivas n0, c1 e c2
Notação θ
}nng(n) cf(n)g(n)c| 
ne,c c{f(n):Θ(g(n)) 
021
021
0 
0


• Uma função f(n) pertence ao conjunto θ(g(n)) se existem 
constantes positivas n0, c1 e c2 tais que ela possa ser “imprensada” 
entre 
c1.g(n) e c2.g(n), 
para um valor de n suficientemente 
grande.
• Exemplo:
• Para isso, devemos definir 
constantes c1, c2 e n0 tais que:
• Encontre constantes que satisfaça as duas desigualdades...
Notação θ
)Θ(nn
n 2
2
3
2

2
2
22
1 3
2
1
ncnnnc 
}nng(n) cf(n)g(n)c| 
ne,c c{f(n):Θ(g(n)) 
021
021
0 
0


• Exemplo de constantes:
Notação θ
21
3
2
1
c
n
c 






 22
22
1 3
2
1
ncnnnc
Dividindo por n2 ...
• Exemplo de constantes:
• Portanto, se existem tais constantes
Notação θ
7
2
1
14
1
0
2
1



n
c
c
)Θ(nn
n 2
2
3
2

21
3
2
1
c
n
c 






 22
22
1 3
2
1
ncnnnc
Dividindo por n2 ...
Notação θ
))(()(
))(()(
)()(
xgxf
e
xgOxf
sse
)xΘ(gxf



• Observação:
Notação ο (o minúsculo)
• O limite assintótico superior fornecido pela notação O (ó-zão) 
pode:
Notação ο
• O limite assintótico superior fornecido pela notação O (ó-zão) 
pode:
▫ Ser assintoticamente restrito;
Notação ο
• O limite assintótico superior fornecido pela notação O (ó-zão) 
pode:
▫ Ser assintoticamente restrito;
▫ Não ser assintoticamente restrito;
Notação ο
• O limite assintótico superior fornecido pela notação O (ó-zão) 
pode:
▫ Ser assintoticamente restrito;
▫ Não ser assintoticamente restrito;
• Exemplos:
▫ Assintoticamente restrito:▫ Não assintoticamente restrito:
Notação ο
)(2 22 nOn 
)()log(
)(2 2
ncOn
nOn


Notação ο
• Todas as funções de O (ó-zão) que não definem um limite 
assintoticamente restrito pertencem a „‟o” (ó-zinho)
Notação ο
))(()(
))(()())(()(
ngnf
entaongnfengOnfse


• Todas as funções de O (ó-zão) que não definem um limite 
assintoticamente restrito pertencem a „‟o” (ó-zinho)
Notação ο
)()log(
)(2 2
nn
nn




))(()(
))(()())(()(
ngnf
entaongnfengOnfse


• Todas as funções de O (ó-zão) que não definem um limite 
assintoticamente restrito pertencem a „‟o” (ó-zinho)
• Comparativo com a notação O;
Notação ο
}nng(n) cnf| 
 nc{f(n):(g(n)) 
0
0
)(0 
0,0


0c constantes as todaspara 
 válidoé )()(0 limite o )),(()(
0c constante alguma para 
 válidomantém se )()(0 limite o )),(()(




ncgnfngnf
ncgnfngOnf

Não é <=, é somente <
Notação ο
0
)(
)(
lim
então Se


 ng
nf
ο(g(n))f(n)
n
• Facilitando o entendimento...
Notação ω (omega minúsculo)
• O limite assintótico inferior fornecido pela notação Ω (omega-
zão) pode:
▫ Ser assintoticamente restrito;
▫ Não ser assintoticamente restrito;
• Exemplos:
▫ Assintoticamente restrito:
▫ Não assintoticamente restrito:
Notação ω
)(2 22 nn 
)(2 3 nn 
Notação ω
))(log(2
)1(2 2
nn
n




))(()(
))(()())(()(
ngnf
entaongnfengOnfse


• Todas as funções de Ω (omegazão) que não definem um limite 
assintoticamente restrito pertencem a ω
Notação ω
}nn nfg(n)c| 
 nc{f(n):(g(n)) 
0
0
)(0 
0,0


Não é <=, é somente <
Notação ω


 )(
)(
lim
então Se
ng
nf
(g(n))f(n)
n

• Facilitando o entendimento...
Exercícios
Exercícios – V ou F
))(()())(()( nfngssengnf  
))(()())(()( ngnfentaongnfse (a)
(b)
(c)
(d)
(e)
(f)
(g)
(h)
(i)
))(()())(()( ngnfentaongnfse 
))(()())(()( ngnfentaongnfse 
))(()())(()( ngnfentaongOnfse 
))(()())(()( ngnfentaongnfse 
))(()())(()( ngnfentaongnfse 
))(()())(()( ngnfentaongnfse 
))(()())(()( ngnfentaongnfse 
Exercício para próxima aula
• Descreva e implemente 3 algoritmos para a seguinte espiral:
• Eles devem ter respectivamente as seguintes complexidades:
▫ Θ(n);
▫ Θ(sqrt(n));
▫ Θ(1).
• Eu informo n, e você informa as coordenadas x, y do n-ésino ponto.
Leitura para próxima aula
• Livro: Algoritmos (Cormen)
▫ 4 Recorrências;
 4.1 O método de substituição;
 4.2 O método de árvore de recursão
 4.3 O método mestre
Bibliografia
• CORMEN, T. H.; LEISERSON, C. E.; RIVEST, R. L.; (2002). 
Algoritmos – Teoria e Prática. Tradução da 2ª edição americana. Rio 
de Janeiro. Editora Campus.
• TAMASSIA, ROBERTO; GOODRICH, MICHAEL T. (2004). Projeto 
de Algoritmos - Fundamentos, Análise e Exemplos da Internet.