PAA Aula 3

Prévia do material em texto

bruno.conceicao@ufop.edu.br
Prof. Bruno César Cota Conceição
Projeto e análise de Algoritmos
 Aula 3 
Notações assintóticas
Notação Assintótica
Sendo n o tamanho da nossa entrada
Notação Assintótica
Sendo n o tamanho da nossa entrada
Nós identificamos as operações
básicas, contamos e transformamos
em função
Notação Assintótica
Essa entrada vai
variar, visto que
nossas funções
mesmo sendo
lineares, ou
polinômios cada
uma tem uma
entrada de valores
diferentes de n
para nossa f(n)
Notação Assintótica
Isso dificulta muito na hora de pegar essas funções de complexidade e
comparar com as funções de complexidade de algoritmos diferentes.
Notação Assintótica
Isso dificulta muito na hora de pegar essas funções de complexidade e
comparar com as funções de complexidade de algoritmos diferentes.
O que fazer?
Notação Assintótica
Isso dificulta muito na hora de pegar essas funções de complexidade e
comparar com as funções de complexidade de algoritmos diferentes.
O que fazer?
Ao invés de comparar elas diretamente, o que vamos fazer como metodologia de análise
de algoritmo é mapear essas funções de f(n) para um grupo de complexidades parecidas.
Notação Assintótica
Isso dificulta muito na hora de pegar essas funções de complexidade e
comparar com as funções de complexidade de algoritmos diferentes.
O que fazer?
Ao invés de comparar elas diretamente, o que vamos fazer como metodologia de análise
de algoritmo é mapear essas funções de f(n) para um grupo de complexidades parecidas.
Ao invés de comparar as funções em si, vamos comparar a ordem de crescimento dessas
funções de complexidade.
Para isso utilizamos a notação assintótica.
Notação Assintótica
Notação Assintótica
Ou seja, uma função f(n) pertence a esse conjunto O(g(n)) se ela possui
uma ordem de crescimento igual ou menor que g(n).
Notação Assintótica
Notação Assintótica
Notação Assintótica
Se eu tenho uma função de
complexidade n, qual a relação
entre essa função e o conjunto
dessas funções de 
Notação Assintótica
Se eu tenho uma função de
complexidade n, qual a relação
entre essa função e o conjunto
dessas funções de 
A n pertence a O(n^2), porque a
O(n^2) limita superiormente em
relação a ordem de crescimento
dessa função n. 
Notação Assintótica
Se eu tenho uma função de
complexidade n, qual a relação
entre essa função e o conjunto
dessas funções de 
A n pertence a O(n^2), porque a
O(n^2) limita superiormente em
relação a ordem de crescimento
dessa função n. 
Ou seja, a n nunca vai crescer
mais rápido que a função
quadrática. 
Notação Assintótica
A 100n + 1 também pertence a
O(n^2).
Notação Assintótica
A n^3 não pertence a O(n^2)
porque funções cúbicas tem
uma ordem de crescimento
maior que a quadrática. 
Notação Assintótica
A n^3 não pertence a O(n^2)
porque funções cúbicas tem
uma ordem de crescimento
maior que a quadrática. 
Então é possível funções cúbicas
crescerem mais rápido que as
funções quadráticas que no caso
é o limite superior desse
conjunto de funções.
Notação Assintótica
A n^3 não pertence a O(n^2)
porque funções cúbicas tem
uma ordem de crescimento
maior que a quadrática. 
Então é possível funções cúbicas
crescerem mais rápido que as
funções quadráticas que no caso
é o limite superior desse
conjunto de funções.
Lembrando que essa notação
também engloba os casos em que n
é igual a n^2.
Notação Assintótica
A n^3 não pertence a O(n^2)
porque funções cúbicas tem
uma ordem de crescimento
maior que a quadrática. 
Então é possível funções cúbicas
crescerem mais rápido que as
funções quadráticas que no caso
é o limite superior desse
conjunto de funções.
Lembrando que essa notação
também engloba os casos em que n
é igual a n^2.
Notação Assintótica
Notação Assintótica
Notação Assintótica
Notação Assintótica: combinando a O com a ômega
Notação Assintótica: combinando a O com a ômega
Para isso acontecer, a nossa f(n) tem que pertencer ao mesmo tempo as duas
notações que vimos anteriormente.
Notação Assintótica: combinando a O com a ômega
Para isso acontecer, a nossa f(n) tem que pertencer ao mesmo tempo as duas
notações que vimos anteriormente.
Essa é uma notação apertada, ou seja, é uma relação mais forte. É mais
informativo do ponto de vista da classificação da complexidade dos algoritmos.
Notação Assintótica: combinando a O com a ômega
Notação Assintótica: combinando a O com a ômega
Notação Assintótica: combinando a O com a ômega
não porque n^2 é no máximo n^3, ou
seja, n^2 é O(n^3), mas n^2 não é 
Notação Assintótica: combinando a O com a ômega
não porque n^2 é no máximo n^3, ou
seja, n^2 é O(n^3), mas n^2 não é 
não pertence pelo motivo inverso
Notação Assintótica: combinando a O com a ômega
não porque n^2 é no máximo n^3, ou
seja, n^2 é O(n^3), mas n^2 não é 
não pertence pelo motivo inverso
Notação Assintótica: combinando a O com a ômega
Quando eu tenho uma função linear, eu vou
dizer que ela é theta, se eu conseguir limitar
essa função superiormente e inferiormente,
eu não dei um limite superior e um inferior,
eu disse exatamente a ordem de grandeza
dessa função.
Definição formal
Definição formal
Definição formal
Nós vamos tentar encontrar uma função, no máximo multiplicada por uma constante,
que limite superiormente a nossa f(n).
inicialmente a função n não domina a n0
Definição formal
Definição formal
O que acontece antes de n0 não importa, pode dominar ou não.
Definição formal
O que acontece antes de n0 não importa, pode dominar ou não.
Definição formal
Para a segunda definição é o mesmo, porém, ao invés de limitar superiormente, vai
limitar inferiormente
Definição formal
E como provo que vale para Theta?
Definição formal
E como provo que vale para Theta?
Definição formal
E como provo que vale para Theta?
Definição formal
E como provo que vale para Theta?
Exemplos
Exemplos
Exemplos
Exemplos
Exemplos
As condições estão sendo atendidas para c e n0?
Exemplos
Exemplos
Se você quiser, pode testar substituindo os valores de c e n0.
Exemplos
Agora vamos tentar encontrar o limite inferior e mostrar que ela cresce pelo menos n^2.
Exemplos
Agora vamos tentar encontrar o limite inferior e mostrar que ela cresce pelo menos n^2.
Exemplos
Agora vamos tentar encontrar o limite inferior e mostrar que ela cresce pelo menos n^2.
Exemplos
Agora vamos tentar encontrar o limite inferior e mostrar que ela cresce pelo menos n^2.
No caso anterior nós encontramos os valores por tentativa e erro, mas
nesse caso, vamos por uma aboradagem mais analítica:
Exemplos
Agora vamos tentar encontrar o limite inferior e mostrar que ela cresce pelo menos n^2.
Exemplos
Agora vamos tentar encontrar o limite inferior e mostrar que ela cresce pelo menos n^2.
Exemplos
Agora vamos tentar encontrar o limite inferior e mostrar que ela cresce pelo menos n^2.
Exemplos
Agora vamos tentar encontrar o limite inferior e mostrar que ela cresce pelo menos n^2.
Exemplos
Exemplos
Exemplos
Exemplos
Exemplos
n cresce ao infinito, dessa forma não
existe c e n0 que faça essa inequação
ser verdade. 
Exemplos
n cresce ao infinito, dessa forma não
existe c e n0 que faça essa inequação
ser verdade. 
Exemplos
n cresce ao infinito, dessa forma não
existe c e n0 que faça essa inequação
ser verdade. 
Se, por exemplo, outro algoritmo para o mesmo problema tem função de complexidade
f1(n) = O(n), 
Alguns detalhes sobre a notação O
Se, por exemplo, outro algoritmo para o mesmo problema tem função de complexidade
f1(n) = O(n), 
podemos comparar f(n) e f1(n) e, em consequência, comparar a eficiência dos
programas que os implementam. 
Alguns detalhes sobre a notação O
Se, por exemplo, outro algoritmo para o mesmo problema tem função de complexidade
f1(n) = O(n), 
podemos comparar f(n) e f1(n) e, em consequência, comparar a eficiência dos
programas que os implementam. 
Em um deles, o tempo de execução é linear e no outro,o
tempo é quadrático
Alguns detalhes sobre a notação O
Alguns detalhes sobre a notação O
Alguns detalhes sobre a notação O
Convenções para a notação O
Convenções para a notação O
Convenções para a notação O
Algumas expressões de O são tão freqüentes que receberam denominações
próprias:
Convenções para a notação O
Algumas expressões de O são tão freqüentes que receberam denominações
próprias:
Referências:
Créditos ao professor Vinícius Dias pelo material disponibilizado.
 LEVITIN, Anany. Introduction to the Design and Analysis of Algorithms. 3a edition. Editora
Addison Wesley;
2. CORMEN, Thomas H.; LEISERSON, Charles E.; RIVEST, Ronald L.; STEIN, Clifford.
Introduction to Algorithms. 3a edition. Editora The MIT Press;
3. ERICKSON, Jeffe. Algorithms. 1st edition. June 2019.
Disponível em: https://jeffe.cs.illinois.edu/teaching/algorithms/book/Algorithms-JeffE.pdf
4. KLEINBERG, Jon; TARDOS, Éva. Algorithm Design. Editora Addison Wesley.
5. DASGUPTA, Sanjoy; PAPADIMITRIOU, Christos; VAZIRANI, Umesh. Algorithms. Editora
McGraw-Hill.
Disponível em: https://integrada.minhabiblioteca.com.br/#/books/9788563308535/pageid/0
6. MANBER, Udi. Introduction to Algorithms: A Creative Approach. 1st edition. Editora
AddisonWesley
7. DE, A. et al. [s.l: s.n.]. Disponível em: <http://waltenomartins.com.br/ap_aa_v1.pdf>. Acesso em: 4 out. 2023.