ACH2002-Aula04_AnaliseAssintotica

Prévia do material em texto

1
Profa. Ariane Machado Lima
ACH2002
Aula 4
Análise assintótica
2SISTEMAS DE
INFORMAÇÃO 22SISTEMAS DE
INFORMAÇÃO 22SISTEMAS DE
INFORMAÇÃO 2SISTEMAS DE
INFORMAÇÃO 22SISTEMAS DE
INFORMAÇÃO 22SISTEMAS DE
INFORMAÇÃO 2SISTEMAS DE
INFORMAÇÃO 2SISTEMAS DE
INFORMAÇÃO 22 2SISTEMAS DE
INFORMAÇÃO 22SISTEMAS DE
INFORMAÇÃO 2SISTEMAS DE
INFORMAÇÃO 22SISTEMAS DE
INFORMAÇÃO 22SISTEMAS DE
INFORMAÇÃO 2SISTEMAS DE
INFORMAÇÃO 22SISTEMAS DE
INFORMAÇÃO
2
Aula passada
 Problema, algoritmo e programa
 Prova de corretude de algoritmos iterativos: 
– Prova por indução de invariantes 
 Análise de complexidade (ex: tempo)
– Testes empíricos
– Análise numérica do insertion-sort
3
Profa. Ariane Machado Lima
Prova por indução
Ex: prova por indução que
Base: P é verdadeira para n = 1:
Hipótese: P é verdadeira para um dado n qualquer: 
Passo: Dado que P vale para n, P é verdadeira para n+1:
Note que um loop é 
uma série...
4
Profa. Ariane Machado Lima
Prova de corretude por indução
Base: no início da primeira 
iteração ( j = 1), x é o elemento 
máximo de v[0] 
Hipótese: assuma que é 
verdadeiro para um j < n, que x é o 
elemento máximo de v[0..j-1]
Passo da indução: se x é o elemento máximo de v[0..j-1] no início da iteração para o 
valor j, então na próxima instrução (que é única no loop): 
- se x < v[j], x será substituído por v[j], o que o torna o elemento máximo de v[0,j] no 
início da próxima iteração (valor j+1)
- se x >= v[j], x não mudará de valor, pois continua sendo o elemento máximo de v[0,j] no 
início da próxima iteração (valor j+1)
x, o valor retornado, é o elemento máximo do vetor
5SISTEMAS DE
INFORMAÇÃO 55SISTEMAS DE
INFORMAÇÃO 55SISTEMAS DE
INFORMAÇÃO 5SISTEMAS DE
INFORMAÇÃO 55SISTEMAS DE
INFORMAÇÃO 55SISTEMAS DE
INFORMAÇÃO 5SISTEMAS DE
INFORMAÇÃO 5SISTEMAS DE
INFORMAÇÃO 55 5SISTEMAS DE
INFORMAÇÃO 55SISTEMAS DE
INFORMAÇÃO 5SISTEMAS DE
INFORMAÇÃO 55SISTEMAS DE
INFORMAÇÃO 55SISTEMAS DE
INFORMAÇÃO 5SISTEMAS DE
INFORMAÇÃO 55SISTEMAS DE
INFORMAÇÃO
5
Aula passada
 Problema, algoritmo e programa
 Prova de corretude de algoritmos iterativos: 
– Prova por indução de invariantes 
 Análise de complexidade (ex: tempo)
– Testes empíricos
– Análise numérica do insertion-sort
6SISTEMAS DE
INFORMAÇÃO 66SISTEMAS DE
INFORMAÇÃO 66SISTEMAS DE
INFORMAÇÃO 6SISTEMAS DE
INFORMAÇÃO 66SISTEMAS DE
INFORMAÇÃO 66SISTEMAS DE
INFORMAÇÃO 6SISTEMAS DE
INFORMAÇÃO 6SISTEMAS DE
INFORMAÇÃO 66 6SISTEMAS DE
INFORMAÇÃO 66SISTEMAS DE
INFORMAÇÃO 6SISTEMAS DE
INFORMAÇÃO 66SISTEMAS DE
INFORMAÇÃO 66SISTEMAS DE
INFORMAÇÃO 6SISTEMAS DE
INFORMAÇÃO 66SISTEMAS DE
INFORMAÇÃO
6
Aula passada
 Problema, algoritmo e programa
 Prova de corretude de algoritmos iterativos: 
– Prova por indução de invariantes 
 Análise de complexidade (ex: tempo)
– Testes empíricos
– Análise numérica do insertion-sort
7
Profa. Ariane Machado Lima
 Função de custo de um algoritmo
 engloba o custo de tempo de cada instrução e o número de vezes que cada 
instrução é executada
 Exemplo: insertion-sort(A) (entrada: array A que tem tamanho n)
tj – número de vezes 
que a linha é 
executada para um 
dado j (depende do j)
// “número a inserir”
8
Profa. Ariane Machado Lima
Melhor caso: vetor já ordenado (A[i] 
≤ chave na linha 5  tj=1 para 
j=2,3,...,n)
T(n)=c1n + c2(n-1) + c4(n-1) + c5(n-1) 
+ c8(n-1) =
( c1+ c2 + c4 + c5 + c8)n - (c2 + c4 + c5 + 
c8)
Tempo de execução, neste caso, 
pode ser expresso como an + b para 
constantes a e b que dependem dos 
custos de instrução ci  função 
linear de n
9
Profa. Ariane Machado Lima
1010SISTEMAS DE
INFORMAÇÃO 1010SISTEMAS DE
INFORMAÇÃO 1010SISTEMAS DE
INFORMAÇÃO 10SISTEMAS DE
INFORMAÇÃO 1010SISTEMAS DE
INFORMAÇÃO 1010SISTEMAS DE
INFORMAÇÃO 10SISTEMAS DE
INFORMAÇÃO 10SISTEMAS DE
INFORMAÇÃO 1010 10SISTEMAS DE
INFORMAÇÃO 1010SISTEMAS DE
INFORMAÇÃO 10SISTEMAS DE
INFORMAÇÃO 1010SISTEMAS DE
INFORMAÇÃO 1010SISTEMAS DE
INFORMAÇÃO 10SISTEMAS DE
INFORMAÇÃO 1010SISTEMAS DE
INFORMAÇÃO
Exercícios (Indução matemática)
1. Prove que 12 + 22 + 32 + ... + n2 = (2n3 + 3n2 + n)/6, n  1
2. Prove que 1 + 3 + 5 + ... + 2n - 1= n2 , n  1
3. Prove que 13 + 23 + 33 + ... + n3 = (n4 + 2n3 + n2)/4, n  1
4. Prove que 13 + 33 + 53 + ... + (2n - 1)3 = 2n4 – n2 , n  1
5. Prove que 1 + 2 + 22 + 23 + ... + 2n = 2n+1 - 1 , n  0
6. Prove que 2n  n2; , n  4
7. Prove que 
8. Prove que a soma dos cubos de três números naturais positivos sucessivos é divisível por 9.
9. Prove que todo número natural n > 1 pode ser escrito como o produto de primos (indução forte).
10. Prove que todo número natural positivo pode ser escrito como a soma de diferentes potências de 2 (indução forte).
1
1−
1
2 +
1
3−. ..+ 1
2n−1−
1
2 n=
1
n+1 +
1
n+2 +. ..+ 1
2 n
Desculpem, os dois últimos ainda não estudamos…
Conseguiram fazer os demais?
11
Profa. Ariane Machado Lima
Aula de hoje
 Análise assintótica (de complexidade)
 Análise formal (matemática) de algoritmos 
12
Profa. Ariane Machado Lima
Análise assintótica
 Primeiro: consciência que a complexidade (tempo, memória, 
etc) normalmente depende do tamanho da entrada 
13
Profa. Ariane Machado Lima
Análise de algorimos
 Em geral:
 tempo de execução de um algoritmo é fixo para uma 
determinada entrada
 analisamos apenas o pior caso dos algoritmos:
 é um limite superior sobre o tempo de execução de qualquer entrada;
 pior caso ocorre com muita frequência para alguns algoritmos. 
Exemplo: registro inexistente em um banco de dados;
 muitas vezes, o caso médio é quase tão ruim quanto o pior caso
1414SISTEMAS DE
INFORMAÇÃO 1414SISTEMAS DE
INFORMAÇÃO 1414SISTEMAS DE
INFORMAÇÃO 14SISTEMAS DE
INFORMAÇÃO 1414SISTEMAS DE
INFORMAÇÃO 1414SISTEMAS DE
INFORMAÇÃO 14SISTEMAS DE
INFORMAÇÃO 14SISTEMAS DE
INFORMAÇÃO 1414 14SISTEMAS DE
INFORMAÇÃO 1414SISTEMAS DE
INFORMAÇÃO 14SISTEMAS DE
INFORMAÇÃO 1414SISTEMAS DE
INFORMAÇÃO 1414SISTEMAS DE
INFORMAÇÃO 14SISTEMAS DE
INFORMAÇÃO 1414SISTEMAS DE
INFORMAÇÃO
 Nas análises anteriores, foram feitas algumas simplificações em relação às 
constantes, chegando à função linear e à função quadrática
 Taxa de crescimento ou ordem de crescimento:
 considera apenas o termo inicial de uma fórmula (exemplo: an2), pois os termos de 
mais baixa ordem são relativamente insignificantes para grandes valores de n;
 ignora o coeficiente constante do termo inicial (a) também por ser menos 
significativo para grandes entradas;
 Portanto, dizemos que: a ordenação por inserção, por exemplo, tem um tempo de 
execução do pior caso igual a (n2) (lê-se “theta de n ao quadrado”);
 Em geral, consideramos um algoritmo mais eficiente que outro se o tempo de 
execução do seu pior caso apresenta uma ordem de crescimento mais baixa.
1515SISTEMAS DE
INFORMAÇÃO 1515SISTEMAS DE
INFORMAÇÃO 1515SISTEMAS DE
INFORMAÇÃO 15SISTEMAS DE
INFORMAÇÃO 1515SISTEMAS DE
INFORMAÇÃO 1515SISTEMAS DE
INFORMAÇÃO 15SISTEMAS DE
INFORMAÇÃO 15SISTEMAS DE
INFORMAÇÃO 1515 15SISTEMAS DE
INFORMAÇÃO 1515SISTEMAS DE
INFORMAÇÃO 15SISTEMAS DE
INFORMAÇÃO 1515SISTEMAS DE
INFORMAÇÃO 1515SISTEMAS DE
INFORMAÇÃO 15SISTEMAS DE
INFORMAÇÃO 1515SISTEMAS DE
INFORMAÇÃO
Complexidade? Assintótica?
 Complexidade
(cs) sf (complexo+dade) Qualidade do que é complexo.
 Complexo
 (cs) adj (lat complexu) 1 Que abrange ou encerra muitos 
elementos ou partes. 2 Que pode ser considerado sob 
vários pontos de vista. 3 Complicado. 
1616SISTEMAS DE
INFORMAÇÃO 1616SISTEMAS DE
INFORMAÇÃO 1616SISTEMAS DE
INFORMAÇÃO 16SISTEMAS DE
INFORMAÇÃO 1616SISTEMAS DE
INFORMAÇÃO 1616SISTEMAS DE
INFORMAÇÃO 16SISTEMAS DE
INFORMAÇÃO 16SISTEMAS DE
INFORMAÇÃO 1616 16SISTEMAS DE
INFORMAÇÃO 1616SISTEMAS DE
INFORMAÇÃO 16SISTEMAS DE
INFORMAÇÃO 1616SISTEMAS DE
INFORMAÇÃO 1616SISTEMAS DE
INFORMAÇÃO 16SISTEMAS DE
INFORMAÇÃO 1616SISTEMAS DE
INFORMAÇÃO
Complexidade? Assintótica?
 Assintótico
adj (assíntota+ico2) Geom 1 Pertencente ou relativo à 
assíntota. 2 Qualificativo do espaço compreendido entre 
uma curva e a sua assíntota. 3 Diz-se da direção paralela 
de uma assíntota. Var: assimptótico.
Assíntotasf (gr asýmptotos) Geom Linha reta que se aproxima 
indefinidamente de uma curva sem nunca poder tocá-
la. Var: assímptota.
A função 
f(x)=1/x tem como assíntotas 
os eixos coordenados.
(Fonte: http://pt.wikipedia.org/wiki/Assímptota)
1717SISTEMAS DE
INFORMAÇÃO 1717SISTEMAS DE
INFORMAÇÃO 1717SISTEMAS DE
INFORMAÇÃO 17SISTEMAS DE
INFORMAÇÃO 1717SISTEMAS DE
INFORMAÇÃO 1717SISTEMAS DE
INFORMAÇÃO 17SISTEMAS DE
INFORMAÇÃO 17SISTEMAS DE
INFORMAÇÃO 1717 17SISTEMAS DE
INFORMAÇÃO 1717SISTEMAS DE
INFORMAÇÃO 17SISTEMAS DE
INFORMAÇÃO 1717SISTEMAS DE
INFORMAÇÃO 1717SISTEMAS DE
INFORMAÇÃO 17SISTEMAS DE
INFORMAÇÃO 1717SISTEMAS DE
INFORMAÇÃO
Crescimento Assintótico de Funções
 Escolha do algoritmo não é um problema crítico quando n é 
pequeno.
 O problema é quando n cresce.
 Por isso, é usual analisar o comportamento das funções de 
custo quando n é bastante grande:
 analisa-se o comportamento assintótico das funções de custo;
 representa o limite do comportamento da função de custo 
quando n cresce.
1818SISTEMAS DE
INFORMAÇÃO 1818SISTEMAS DE
INFORMAÇÃO 1818SISTEMAS DE
INFORMAÇÃO 18SISTEMAS DE
INFORMAÇÃO 1818SISTEMAS DE
INFORMAÇÃO 1818SISTEMAS DE
INFORMAÇÃO 18SISTEMAS DE
INFORMAÇÃO 18SISTEMAS DE
INFORMAÇÃO 1818 18SISTEMAS DE
INFORMAÇÃO 1818SISTEMAS DE
INFORMAÇÃO 18SISTEMAS DE
INFORMAÇÃO 1818SISTEMAS DE
INFORMAÇÃO 1818SISTEMAS DE
INFORMAÇÃO 18SISTEMAS DE
INFORMAÇÃO 1818SISTEMAS DE
INFORMAÇÃO
Crescimento Assintótico de Funções
 Eficiência assintótica dos algoritmos:
 estuda a maneira como o tempo de execução de um 
algoritmo aumenta com o tamanho da entrada no limite, à 
medida que o tamanho da entrada aumenta 
indefinidamente (sem limitação)
 em geral, um algoritmo que é assintoticamente mais 
eficiente será a melhor escolha para toda as entradas, 
exceto as pequenas.
1919SISTEMAS DE
INFORMAÇÃO 1919SISTEMAS DE
INFORMAÇÃO 1919SISTEMAS DE
INFORMAÇÃO 19SISTEMAS DE
INFORMAÇÃO 1919SISTEMAS DE
INFORMAÇÃO 1919SISTEMAS DE
INFORMAÇÃO 19SISTEMAS DE
INFORMAÇÃO 19SISTEMAS DE
INFORMAÇÃO 1919 19SISTEMAS DE
INFORMAÇÃO 1919SISTEMAS DE
INFORMAÇÃO 19SISTEMAS DE
INFORMAÇÃO 1919SISTEMAS DE
INFORMAÇÃO 1919SISTEMAS DE
INFORMAÇÃO 19SISTEMAS DE
INFORMAÇÃO 1919SISTEMAS DE
INFORMAÇÃO
Crescimento Assintótico de Funções
 Vamos comparar funções assintoticamente, ou seja, 
para valores grandes, desprezando constantes 
multiplicativas e termos de menor ordem.
2020SISTEMAS DE
INFORMAÇÃO 2020SISTEMAS DE
INFORMAÇÃO 2020SISTEMAS DE
INFORMAÇÃO 20SISTEMAS DE
INFORMAÇÃO 2020SISTEMAS DE
INFORMAÇÃO 2020SISTEMAS DE
INFORMAÇÃO 20SISTEMAS DE
INFORMAÇÃO 20SISTEMAS DE
INFORMAÇÃO 2020 20SISTEMAS DE
INFORMAÇÃO 2020SISTEMAS DE
INFORMAÇÃO 20SISTEMAS DE
INFORMAÇÃO 2020SISTEMAS DE
INFORMAÇÃO 2020SISTEMAS DE
INFORMAÇÃO 20SISTEMAS DE
INFORMAÇÃO 2020SISTEMAS DE
INFORMAÇÃO
Comportamento Assintótico
 Supondo uma máquina que execute 1 milhão (106) 
de operações por segundo n
2222SISTEMAS DE
INFORMAÇÃO 2222SISTEMAS DE
INFORMAÇÃO 2222SISTEMAS DE
INFORMAÇÃO 22SISTEMAS DE
INFORMAÇÃO 2222SISTEMAS DE
INFORMAÇÃO 2222SISTEMAS DE
INFORMAÇÃO 22SISTEMAS DE
INFORMAÇÃO 22SISTEMAS DE
INFORMAÇÃO 2222 22SISTEMAS DE
INFORMAÇÃO 2222SISTEMAS DE
INFORMAÇÃO 22SISTEMAS DE
INFORMAÇÃO 2222SISTEMAS DE
INFORMAÇÃO 2222SISTEMAS DE
INFORMAÇÃO 22SISTEMAS DE
INFORMAÇÃO 2222SISTEMAS DE
INFORMAÇÃO
Comportamento Assintótico – Resumindo...
 Se f(n) é a função de complexidade de um algoritmo A
 O comportamento assintótico de f (n) representa o limite do 
comportamento do custo (complexidade) de A quando n cresce.
 A análise de um algoritmo (função de complexidade)
 Geralmente considera apenas algumas operações elementares ou 
mesmo uma operação elementar (e.g., o número de comparações).
 A complexidade assintótica relata crescimento assintótico das 
operações elementares.
2323SISTEMAS DE
INFORMAÇÃO 2323SISTEMAS DE
INFORMAÇÃO 2323SISTEMAS DE
INFORMAÇÃO 23SISTEMAS DE
INFORMAÇÃO 2323SISTEMAS DE
INFORMAÇÃO 2323SISTEMAS DE
INFORMAÇÃO 23SISTEMAS DE
INFORMAÇÃO 23SISTEMAS DE
INFORMAÇÃO 2323 23SISTEMAS DE
INFORMAÇÃO 2323SISTEMAS DE
INFORMAÇÃO 23SISTEMAS DE
INFORMAÇÃO 2323SISTEMAS DE
INFORMAÇÃO 2323SISTEMAS DE
INFORMAÇÃO 23SISTEMAS DE
INFORMAÇÃO 2323SISTEMAS DE
INFORMAÇÃO
Relacionamento Assintótico
 Definição:
 Uma função g(n) domina assintoticamente outra função 
f(n) se existem duas constantes positivas c e m tais que, 
para n ≥ m, tem-se |f(n)| ≤ c . |g(n)|.
m
n
cg
f
2424SISTEMAS DE
INFORMAÇÃO 2424SISTEMAS DE
INFORMAÇÃO 2424SISTEMAS DE
INFORMAÇÃO 24SISTEMAS DE
INFORMAÇÃO 2424SISTEMAS DE
INFORMAÇÃO 2424SISTEMAS DE
INFORMAÇÃO 24SISTEMAS DE
INFORMAÇÃO 24SISTEMAS DE
INFORMAÇÃO 2424 24SISTEMAS DE
INFORMAÇÃO 2424SISTEMAS DE
INFORMAÇÃO 24SISTEMAS DE
INFORMAÇÃO 2424SISTEMAS DE
INFORMAÇÃO 2424SISTEMAS DE
INFORMAÇÃO 24SISTEMAS DE
INFORMAÇÃO 2424SISTEMAS DE
INFORMAÇÃO
Relacionamento Assintótico
 Definição:
 Uma função g(n) domina assintoticamente outra função 
f(n) se existem duas constantes positivas c e m tais que, 
para n ≥ m, tem-se |f(n)| ≤ c . |g(n)|.
m
n
cg
f
 Exemplo: g(n) = n e f (n) = n2
 Alguém domina alguém?
2525SISTEMAS DE
INFORMAÇÃO 2525SISTEMAS DE
INFORMAÇÃO 2525SISTEMAS DE
INFORMAÇÃO 25SISTEMAS DE
INFORMAÇÃO 2525SISTEMAS DE
INFORMAÇÃO 2525SISTEMAS DE
INFORMAÇÃO 25SISTEMAS DE
INFORMAÇÃO 25SISTEMAS DE
INFORMAÇÃO 2525 25SISTEMAS DE
INFORMAÇÃO 2525SISTEMAS DE
INFORMAÇÃO 25SISTEMAS DE
INFORMAÇÃO 2525SISTEMAS DE
INFORMAÇÃO 2525SISTEMAS DE
INFORMAÇÃO 25SISTEMAS DE
INFORMAÇÃO 2525SISTEMAS DE
INFORMAÇÃO
Relacionamento Assintótico
 Definição:
 Uma função g(n) domina assintoticamente outra função 
f(n) se existem duas constantes positivas c e m tais que, 
para n ≥ m, tem-se |f(n)| ≤ c . |g(n)|.
m
n
cg
f
 Exemplo: g(n) = n e f (n) = n2
 Alguém domina alguém?
 ∣n∣ ≤ ∣n2∣ para todo n ∈ N
• Para c = ? e m = ? ⇒ g(n) ≤ f(n)∣ ∣ ∣ ∣
• Portanto, f (n) domina assintoticamente g(n).
2626SISTEMAS DE
INFORMAÇÃO 2626SISTEMAS DE
INFORMAÇÃO 2626SISTEMAS DE
INFORMAÇÃO 26SISTEMAS DE
INFORMAÇÃO 2626SISTEMAS DE
INFORMAÇÃO 2626SISTEMAS DE
INFORMAÇÃO 26SISTEMAS DE
INFORMAÇÃO 26SISTEMAS DE
INFORMAÇÃO 2626 26SISTEMAS DE
INFORMAÇÃO 2626SISTEMAS DE
INFORMAÇÃO 26SISTEMAS DE
INFORMAÇÃO 2626SISTEMAS DE
INFORMAÇÃO 2626SISTEMAS DE
INFORMAÇÃO 26SISTEMAS DE
INFORMAÇÃO 2626SISTEMAS DE
INFORMAÇÃO
Relacionamento Assintótico
 Definição:
 Uma função g(n) domina assintoticamente outra função 
f(n) se existem duas constantes positivas c e m tais que, 
para n ≥ m, tem-se |f(n)| ≤ c . |g(n)|.
m
n
cg
f
 Exemplo: g(n) = n e f (n) = n2
 Alguém domina alguém?
 ∣n∣ ≤ ∣n2∣ para todo n ∈ N
• Para c = 1 e m = 0 ⇒ g(n) ≤ f(n)∣ ∣ ∣ ∣
• Portanto, f (n) domina assintoticamente g(n).
Não necessariamente precisa 
mostrar os primeiros valores 
(c=13 e m=5 também vale 
para a prova)
2727SISTEMAS DE
INFORMAÇÃO 2727SISTEMAS DE
INFORMAÇÃO 2727SISTEMAS DE
INFORMAÇÃO 27SISTEMAS DE
INFORMAÇÃO 2727SISTEMAS DE
INFORMAÇÃO 2727SISTEMAS DE
INFORMAÇÃO 27SISTEMAS DE
INFORMAÇÃO 27SISTEMAS DE
INFORMAÇÃO 2727 27SISTEMAS DE
INFORMAÇÃO 2727SISTEMAS DE
INFORMAÇÃO 27SISTEMAS DE
INFORMAÇÃO 2727SISTEMAS DE
INFORMAÇÃO 2727SISTEMAS DE
INFORMAÇÃO 27SISTEMAS DE
INFORMAÇÃO 2727SISTEMAS DE
INFORMAÇÃO
Relacionamento Assintótico
 g(n) = n e f (n) = -n2
 Alguém domina alguém?
 ???
2828SISTEMAS DE
INFORMAÇÃO 2828SISTEMAS DE
INFORMAÇÃO 2828SISTEMAS DE
INFORMAÇÃO 28SISTEMAS DE
INFORMAÇÃO 2828SISTEMAS DE
INFORMAÇÃO 2828SISTEMAS DE
INFORMAÇÃO 28SISTEMAS DE
INFORMAÇÃO 28SISTEMAS DE
INFORMAÇÃO 2828 28SISTEMAS DE
INFORMAÇÃO 2828SISTEMAS DE
INFORMAÇÃO 28SISTEMAS DE
INFORMAÇÃO 2828SISTEMAS DE
INFORMAÇÃO 2828SISTEMAS DE
INFORMAÇÃO 28SISTEMAS DE
INFORMAÇÃO 2828SISTEMAS DE
INFORMAÇÃO
Relacionamento Assintótico
 g(n) = n e f (n) = -n2
 Alguém domina alguém?
 |n| ≤ ∣-n2∣ para todo n N.∈
 Por ser módulo, o sinal não importa
 Para c = 1 e m = 0 ⇒ ∣g(n)∣ ≤ ∣f(n)∣.
 Portanto, f (n) domina assintoticamente g(n).
2929SISTEMAS DE
INFORMAÇÃO 2929SISTEMAS DE
INFORMAÇÃO 2929SISTEMAS DE
INFORMAÇÃO 29SISTEMAS DE
INFORMAÇÃO 2929SISTEMAS DE
INFORMAÇÃO 2929SISTEMAS DE
INFORMAÇÃO 29SISTEMAS DE
INFORMAÇÃO29SISTEMAS DE
INFORMAÇÃO 2929 29SISTEMAS DE
INFORMAÇÃO 2929SISTEMAS DE
INFORMAÇÃO 29SISTEMAS DE
INFORMAÇÃO 2929SISTEMAS DE
INFORMAÇÃO 2929SISTEMAS DE
INFORMAÇÃO 29SISTEMAS DE
INFORMAÇÃO 2929SISTEMAS DE
INFORMAÇÃO
Relacionamento Assintótico
 g(n) = (n+1)2 e f (n) = n2
 Alguém domina alguém?
 ???
3030SISTEMAS DE
INFORMAÇÃO 3030SISTEMAS DE
INFORMAÇÃO 3030SISTEMAS DE
INFORMAÇÃO 30SISTEMAS DE
INFORMAÇÃO 3030SISTEMAS DE
INFORMAÇÃO 3030SISTEMAS DE
INFORMAÇÃO 30SISTEMAS DE
INFORMAÇÃO 30SISTEMAS DE
INFORMAÇÃO 3030 30SISTEMAS DE
INFORMAÇÃO 3030SISTEMAS DE
INFORMAÇÃO 30SISTEMAS DE
INFORMAÇÃO 3030SISTEMAS DE
INFORMAÇÃO 3030SISTEMAS DE
INFORMAÇÃO 30SISTEMAS DE
INFORMAÇÃO 3030SISTEMAS DE
INFORMAÇÃO
Relacionamento Assintótico
 g(n) = (n+1)2 e f (n) = n2
 Alguém domina alguém?
 Vamos colocar em um 
gráfico
(n+1)2
n2
3131SISTEMAS DE
INFORMAÇÃO 3131SISTEMAS DE
INFORMAÇÃO 3131SISTEMAS DE
INFORMAÇÃO 31SISTEMAS DE
INFORMAÇÃO 3131SISTEMAS DE
INFORMAÇÃO 3131SISTEMAS DE
INFORMAÇÃO 31SISTEMAS DE
INFORMAÇÃO 31SISTEMAS DE
INFORMAÇÃO 3131 31SISTEMAS DE
INFORMAÇÃO 3131SISTEMAS DE
INFORMAÇÃO 31SISTEMAS DE
INFORMAÇÃO 3131SISTEMAS DE
INFORMAÇÃO 3131SISTEMAS DE
INFORMAÇÃO 31SISTEMAS DE
INFORMAÇÃO 3131SISTEMAS DE
INFORMAÇÃO
Relacionamento Assintótico
 g(n) = (n+1)2 e f (n) = n2
 Alguém domina alguém?
 Vamos colocar em um 
gráfico
 ∣n2∣ ≤ ∣(n+1)2∣, para n ≥ 0, 
c = 1
 g(n) domina f(n)
(n+1)2
n2
3232SISTEMAS DE
INFORMAÇÃO 3232SISTEMAS DE
INFORMAÇÃO 3232SISTEMAS DE
INFORMAÇÃO 32SISTEMAS DE
INFORMAÇÃO 3232SISTEMAS DE
INFORMAÇÃO 3232SISTEMAS DE
INFORMAÇÃO 32SISTEMAS DE
INFORMAÇÃO 32SISTEMAS DE
INFORMAÇÃO 3232 32SISTEMAS DE
INFORMAÇÃO 3232SISTEMAS DE
INFORMAÇÃO 32SISTEMAS DE
INFORMAÇÃO 3232SISTEMAS DE
INFORMAÇÃO 3232SISTEMAS DE
INFORMAÇÃO 32SISTEMAS DE
INFORMAÇÃO 3232SISTEMAS DE
INFORMAÇÃO
Relacionamento Assintótico
 g(n) = (n+1)2 e f (n) = n2
 Alguém domina alguém?
 Será somente isso?
 Não há como f(n) dominar 
g(n)?
 ???
(n+1)2
n2
3333SISTEMAS DE
INFORMAÇÃO 3333SISTEMAS DE
INFORMAÇÃO 3333SISTEMAS DE
INFORMAÇÃO 33SISTEMAS DE
INFORMAÇÃO 3333SISTEMAS DE
INFORMAÇÃO 3333SISTEMAS DE
INFORMAÇÃO 33SISTEMAS DE
INFORMAÇÃO 33SISTEMAS DE
INFORMAÇÃO 3333 33SISTEMAS DE
INFORMAÇÃO 3333SISTEMAS DE
INFORMAÇÃO 33SISTEMAS DE
INFORMAÇÃO 3333SISTEMAS DE
INFORMAÇÃO 3333SISTEMAS DE
INFORMAÇÃO 33SISTEMAS DE
INFORMAÇÃO 3333SISTEMAS DE
INFORMAÇÃO
Relacionamento Assintótico
 g(n) = (n+1)2 e f (n) = n2
 Alguém domina alguém?
 Não há como f(n) dominar g(n)?
 Lembre que a definição envolve também uma constante.
 Suponha que queremos g(n) ≤ cf(n)
 Então ∣(n+1)2∣ ≤ ∣cn2∣
 Mas, para isso, basta que ∣(n+1)2∣ ≤ ∣(√c n)2∣,
 ou ∣n+1∣ ≤ ∣√c n∣
 Se √c = 2, ou seja, c=4, isso é verdade
(n+1)2
n2
3434SISTEMAS DE
INFORMAÇÃO 3434SISTEMAS DE
INFORMAÇÃO 3434SISTEMAS DE
INFORMAÇÃO 34SISTEMAS DE
INFORMAÇÃO 3434SISTEMAS DE
INFORMAÇÃO 3434SISTEMAS DE
INFORMAÇÃO 34SISTEMAS DE
INFORMAÇÃO 34SISTEMAS DE
INFORMAÇÃO 3434 34SISTEMAS DE
INFORMAÇÃO 3434SISTEMAS DE
INFORMAÇÃO 34SISTEMAS DE
INFORMAÇÃO 3434SISTEMAS DE
INFORMAÇÃO 3434SISTEMAS DE
INFORMAÇÃO 34SISTEMAS DE
INFORMAÇÃO 3434SISTEMAS DE
INFORMAÇÃO
Relacionamento Assintótico
(n+1)2
4n2
3535SISTEMAS DE
INFORMAÇÃO 3535SISTEMAS DE
INFORMAÇÃO 3535SISTEMAS DE
INFORMAÇÃO 35SISTEMAS DE
INFORMAÇÃO 3535SISTEMAS DE
INFORMAÇÃO 3535SISTEMAS DE
INFORMAÇÃO 35SISTEMAS DE
INFORMAÇÃO 35SISTEMAS DE
INFORMAÇÃO 3535 35SISTEMAS DE
INFORMAÇÃO 3535SISTEMAS DE
INFORMAÇÃO 35SISTEMAS DE
INFORMAÇÃO 3535SISTEMAS DE
INFORMAÇÃO 3535SISTEMAS DE
INFORMAÇÃO 35SISTEMAS DE
INFORMAÇÃO 3535SISTEMAS DE
INFORMAÇÃO
Notação O
 Knuth(1971) * criou a notação O (lê-se "O grande") para 
expressar que g(n) domina assintoticamente f(n)
 Escreve-se f(n) = O(g(n)) e lê-se: "f(n) é da ordem no máximo 
g(n)".
 Para que serve isto para o Bacharel em Sistemas de 
Informação?
*Knuth, D.E. (1971) "Mathematical Analysis of Algorithms". Proceedings IFIP Congress 71, vol. 1, 
North Holland, Amsterdam, Holanda, 135-143.
3636SISTEMAS DE
INFORMAÇÃO 3636SISTEMAS DE
INFORMAÇÃO 3636SISTEMAS DE
INFORMAÇÃO 36SISTEMAS DE
INFORMAÇÃO 3636SISTEMAS DE
INFORMAÇÃO 3636SISTEMAS DE
INFORMAÇÃO 36SISTEMAS DE
INFORMAÇÃO 36SISTEMAS DE
INFORMAÇÃO 3636 36SISTEMAS DE
INFORMAÇÃO 3636SISTEMAS DE
INFORMAÇÃO 36SISTEMAS DE
INFORMAÇÃO 3636SISTEMAS DE
INFORMAÇÃO 3636SISTEMAS DE
INFORMAÇÃO 36SISTEMAS DE
INFORMAÇÃO 3636SISTEMAS DE
INFORMAÇÃO
Notação O
 Para que serve isto para o Bacharel em Sistemas de 
Informação?
 Muitas vezes calcular a função de complexidade exata f(n) de 
um algoritmo é complicado.
 É mais fácil determinar que f(n) é O(g(n)), isto é, que 
assintoticamente f(n) cresce no máximo como g(n).
3737SISTEMAS DE
INFORMAÇÃO 3737SISTEMAS DE
INFORMAÇÃO 3737SISTEMAS DE
INFORMAÇÃO 37SISTEMAS DE
INFORMAÇÃO 3737SISTEMAS DE
INFORMAÇÃO 3737SISTEMAS DE
INFORMAÇÃO 37SISTEMAS DE
INFORMAÇÃO 37SISTEMAS DE
INFORMAÇÃO 3737 37SISTEMAS DE
INFORMAÇÃO 3737SISTEMAS DE
INFORMAÇÃO 37SISTEMAS DE
INFORMAÇÃO 3737SISTEMAS DE
INFORMAÇÃO 3737SISTEMAS DE
INFORMAÇÃO 37SISTEMAS DE
INFORMAÇÃO 3737SISTEMAS DE
INFORMAÇÃO
Notação O
 Definição:
 O(g(n)) = {f(n): existem constantes positivas c e n0 tais 
que 0 ≤ f(n) ≤ cg(n), para todo n ≥ n0}
 Informalmente, dizemos que, se f(n) ∈ O(g(n)), 
então f(n) cresce no máximo tão rapidamente quanto 
g(n).
n0
Conjunto de funções dominadas por g(n)
cg é um limite superior de f
funções assintoticamente não negativas
3838SISTEMAS DE
INFORMAÇÃO 3838SISTEMAS DE
INFORMAÇÃO 3838SISTEMAS DE
INFORMAÇÃO 38SISTEMAS DE
INFORMAÇÃO 3838SISTEMAS DE
INFORMAÇÃO 3838SISTEMAS DE
INFORMAÇÃO 38SISTEMAS DE
INFORMAÇÃO 38SISTEMAS DE
INFORMAÇÃO 3838 38SISTEMAS DE
INFORMAÇÃO 3838SISTEMAS DE
INFORMAÇÃO 38SISTEMAS DE
INFORMAÇÃO 3838SISTEMAS DE
INFORMAÇÃO 3838SISTEMAS DE
INFORMAÇÃO 38SISTEMAS DE
INFORMAÇÃO 3838SISTEMAS DE
INFORMAÇÃO
Notação O
3939SISTEMAS DE
INFORMAÇÃO 3939SISTEMAS DE
INFORMAÇÃO 3939SISTEMAS DE
INFORMAÇÃO 39SISTEMAS DE
INFORMAÇÃO 3939SISTEMAS DE
INFORMAÇÃO 3939SISTEMAS DE
INFORMAÇÃO 39SISTEMAS DE
INFORMAÇÃO 39SISTEMAS DE
INFORMAÇÃO 3939 39SISTEMAS DE
INFORMAÇÃO 3939SISTEMAS DE
INFORMAÇÃO 39SISTEMAS DE
INFORMAÇÃO 3939SISTEMAS DE
INFORMAÇÃO 3939SISTEMAS DE
INFORMAÇÃO 39SISTEMAS DE
INFORMAÇÃO 3939SISTEMAS DE
INFORMAÇÃO
Notação O
4040SISTEMAS DE
INFORMAÇÃO 4040SISTEMAS DE
INFORMAÇÃO 4040SISTEMAS DE
INFORMAÇÃO 40SISTEMAS DE
INFORMAÇÃO 4040SISTEMAS DE
INFORMAÇÃO 4040SISTEMAS DE
INFORMAÇÃO 40SISTEMAS DE
INFORMAÇÃO 40SISTEMAS DE
INFORMAÇÃO 4040 40SISTEMAS DE
INFORMAÇÃO 4040SISTEMAS DE
INFORMAÇÃO 40SISTEMAS DE
INFORMAÇÃO 4040SISTEMAS DE
INFORMAÇÃO 4040SISTEMAS DE
INFORMAÇÃO 40SISTEMAS DE
INFORMAÇÃO 4040SISTEMAS DE
INFORMAÇÃO
Notação O
4141SISTEMAS DE
INFORMAÇÃO 4141SISTEMAS DE
INFORMAÇÃO 4141SISTEMAS DE
INFORMAÇÃO 41SISTEMAS DE
INFORMAÇÃO 4141SISTEMAS DE
INFORMAÇÃO 4141SISTEMAS DE
INFORMAÇÃO 41SISTEMAS DE
INFORMAÇÃO 41SISTEMAS DE
INFORMAÇÃO 4141 41SISTEMAS DE
INFORMAÇÃO 4141SISTEMAS DE
INFORMAÇÃO 41SISTEMAS DE
INFORMAÇÃO 4141SISTEMAS DE
INFORMAÇÃO 4141SISTEMAS DE
INFORMAÇÃO 41SISTEMAS DE
INFORMAÇÃO 4141SISTEMAS DE
INFORMAÇÃO
Notação O
Qualquer n0 >= 0
vale
4242SISTEMAS DE
INFORMAÇÃO 4242SISTEMAS DE
INFORMAÇÃO 4242SISTEMAS DE
INFORMAÇÃO 42SISTEMAS DE
INFORMAÇÃO 4242SISTEMAS DE
INFORMAÇÃO 4242SISTEMAS DE
INFORMAÇÃO 42SISTEMAS DE
INFORMAÇÃO 42SISTEMAS DE
INFORMAÇÃO 4242 42SISTEMAS DE
INFORMAÇÃO 4242SISTEMAS DE
INFORMAÇÃO 42SISTEMAS DE
INFORMAÇÃO 4242SISTEMAS DE
INFORMAÇÃO 4242SISTEMAS DE
INFORMAÇÃO 42SISTEMAS DE
INFORMAÇÃO 4242SISTEMAS DE
INFORMAÇÃO
Notação O
 Usamos a notação O para dar um limite superior 
sobre uma função, dentro de um fator constante.
n0
4343SISTEMAS DE
INFORMAÇÃO 4343SISTEMAS DE
INFORMAÇÃO 4343SISTEMAS DE
INFORMAÇÃO 43SISTEMAS DE
INFORMAÇÃO 4343SISTEMAS DE
INFORMAÇÃO 4343SISTEMAS DE
INFORMAÇÃO 43SISTEMAS DE
INFORMAÇÃO 43SISTEMAS DE
INFORMAÇÃO 4343 43SISTEMAS DE
INFORMAÇÃO 4343SISTEMAS DE
INFORMAÇÃO 43SISTEMAS DE
INFORMAÇÃO 4343SISTEMAS DE
INFORMAÇÃO 4343SISTEMAS DE
INFORMAÇÃO 43SISTEMAS DE
INFORMAÇÃO 4343SISTEMAS DE
INFORMAÇÃO
Notação O
 Com a notação O podemos descrever frequentementeo tempo de execução de um 
algoritmo apenas inspecionando a estrutura global do algoritmo.
 Exemplo: estrutura de laço duplamente aninhado 
no algoritmo insertion-sort (visto anteriormente) 
produz um limite superior O(n2) no pior caso:
– custo de uma iteração do laço interno é 
limitado superiormente por O(1) (constante)
– índices i e j são no máximo n
– laço interno é executado no máximo uma vez 
para cada um dos n2 pares de valores 
correspondentes a i e j 
4444SISTEMAS DE
INFORMAÇÃO 4444SISTEMAS DE
INFORMAÇÃO 4444SISTEMAS DE
INFORMAÇÃO 44SISTEMAS DE
INFORMAÇÃO 4444SISTEMAS DE
INFORMAÇÃO 4444SISTEMAS DE
INFORMAÇÃO 44SISTEMAS DE
INFORMAÇÃO 44SISTEMAS DE
INFORMAÇÃO 4444 44SISTEMAS DE
INFORMAÇÃO 4444SISTEMAS DE
INFORMAÇÃO 44SISTEMAS DE
INFORMAÇÃO 4444SISTEMAS DE
INFORMAÇÃO 4444SISTEMAS DE
INFORMAÇÃO 44SISTEMAS DE
INFORMAÇÃO 4444SISTEMAS DE
INFORMAÇÃO
Operações com a notação O
4545SISTEMAS DE
INFORMAÇÃO 4545SISTEMAS DE
INFORMAÇÃO 4545SISTEMAS DE
INFORMAÇÃO 45SISTEMAS DE
INFORMAÇÃO 4545SISTEMAS DE
INFORMAÇÃO 4545SISTEMAS DE
INFORMAÇÃO 45SISTEMAS DE
INFORMAÇÃO 45SISTEMAS DE
INFORMAÇÃO 4545 45SISTEMAS DE
INFORMAÇÃO 4545SISTEMAS DE
INFORMAÇÃO 45SISTEMAS DE
INFORMAÇÃO 4545SISTEMAS DE
INFORMAÇÃO 4545SISTEMAS DE
INFORMAÇÃO 45SISTEMAS DE
INFORMAÇÃO 4545SISTEMAS DE
INFORMAÇÃO
Operações com a notação O
Particularmente útil para analisar algoritmos (sequências de trechos de código)
4646SISTEMAS DE
INFORMAÇÃO 4646SISTEMAS DE
INFORMAÇÃO 4646SISTEMAS DE
INFORMAÇÃO 46SISTEMAS DE
INFORMAÇÃO 4646SISTEMAS DE
INFORMAÇÃO 4646SISTEMAS DE
INFORMAÇÃO 46SISTEMAS DE
INFORMAÇÃO 46SISTEMAS DE
INFORMAÇÃO 4646 46SISTEMAS DE
INFORMAÇÃO 4646SISTEMAS DE
INFORMAÇÃO 46SISTEMAS DE
INFORMAÇÃO 4646SISTEMAS DE
INFORMAÇÃO 4646SISTEMAS DE
INFORMAÇÃO 46SISTEMAS DE
INFORMAÇÃO 4646SISTEMAS DE
INFORMAÇÃO
Operações com a notação O
 A regra O(f(n)) + O(g(n)) = O(max(f(n),g(n))) pode 
ser usada para calcular o tempo de execução de uma 
sequência de trechos de um programa
 Suponha 3 trechos: O(n), O(n2) e O(nlogn)
 Qual o tempo de execução do algoritmo como um todo?
 ???
4747SISTEMAS DE
INFORMAÇÃO 4747SISTEMAS DE
INFORMAÇÃO 4747SISTEMAS DE
INFORMAÇÃO 47SISTEMAS DE
INFORMAÇÃO 4747SISTEMAS DE
INFORMAÇÃO 4747SISTEMAS DE
INFORMAÇÃO 47SISTEMAS DE
INFORMAÇÃO 47SISTEMAS DE
INFORMAÇÃO 4747 47SISTEMAS DE
INFORMAÇÃO 4747SISTEMAS DE
INFORMAÇÃO 47SISTEMAS DE
INFORMAÇÃO 4747SISTEMAS DE
INFORMAÇÃO 4747SISTEMAS DE
INFORMAÇÃO 47SISTEMAS DE
INFORMAÇÃO 4747SISTEMAS DE
INFORMAÇÃO
Operações com a notação O
 A regra O(f(n)) + O(g(n)) = O(max(f(n),g(n))) pode 
ser usada para calcular o tempo de execução de uma 
sequência de trechos de um programa
 Suponha 3 trechos: O(n), O(n2) e O(nlogn)
 Qual o tempo de execução do algoritmo como um todo?
 Lembre-se que o tempo de execução é a soma dos tempos de 
cada trecho
 O(n) + O(n2) + O(nlogn) = max(O(n), O(n2), O(nlogn)) = O(n2)
48
Profa. Ariane Machado Lima
Ex: InsertionSort é O de quanto?
49
Profa. Ariane Machado Lima
Ex: InsertionSort é O(n2)
50
Profa. Ariane Machado Lima
Ex: InsertionSort é O(n2)
Também é O(nk) 
para k > 2...
5151SISTEMAS DE
INFORMAÇÃO 5151SISTEMAS DE
INFORMAÇÃO 5151SISTEMAS DE
INFORMAÇÃO 51SISTEMAS DE
INFORMAÇÃO 5151SISTEMAS DE
INFORMAÇÃO 5151SISTEMAS DE
INFORMAÇÃO 51SISTEMAS DE
INFORMAÇÃO 51SISTEMAS DE
INFORMAÇÃO 5151 51SISTEMAS DE
INFORMAÇÃO 5151SISTEMAS DE
INFORMAÇÃO 51SISTEMAS DE
INFORMAÇÃO 5151SISTEMAS DE
INFORMAÇÃO 5151SISTEMAS DE
INFORMAÇÃO 51SISTEMAS DE
INFORMAÇÃO 5151SISTEMAS DE
INFORMAÇÃO
Notação  Definição:
 (g(n)) = {f(n): existem constantes positivas c e n0 tais que 
0 ≤ cg(n) ≤ f(n), para todo n ≥ n0}
 Informalmente, dizemos que, se f(n) ∈ (g(n)), então 
f(n) cresce no mínimo tão lentamente quanto g(n).
 Note que se f(n) ∈ O(g(n))
define um limite superior
para f(n), (g(n)) define
um limite inferior
n0
funções assintoticamente não negativas
5252SISTEMAS DE
INFORMAÇÃO 5252SISTEMAS DE
INFORMAÇÃO 5252SISTEMAS DE
INFORMAÇÃO 52SISTEMAS DE
INFORMAÇÃO 5252SISTEMAS DE
INFORMAÇÃO 5252SISTEMAS DE
INFORMAÇÃO 52SISTEMAS DE
INFORMAÇÃO 52SISTEMAS DE
INFORMAÇÃO 5252 52SISTEMAS DE
INFORMAÇÃO 5252SISTEMAS DE
INFORMAÇÃO 52SISTEMAS DE
INFORMAÇÃO 5252SISTEMAS DE
INFORMAÇÃO 5252SISTEMAS DE
INFORMAÇÃO 52SISTEMAS DE
INFORMAÇÃO 5252SISTEMAS DE
INFORMAÇÃO
Notação 
5353SISTEMAS DE
INFORMAÇÃO 5353SISTEMAS DE
INFORMAÇÃO 5353SISTEMAS DE
INFORMAÇÃO 53SISTEMAS DE
INFORMAÇÃO 5353SISTEMAS DE
INFORMAÇÃO 5353SISTEMAS DE
INFORMAÇÃO 53SISTEMAS DE
INFORMAÇÃO 53SISTEMAS DE
INFORMAÇÃO 5353 53SISTEMAS DE
INFORMAÇÃO 5353SISTEMAS DE
INFORMAÇÃO 53SISTEMAS DE
INFORMAÇÃO 5353SISTEMAS DE
INFORMAÇÃO 5353SISTEMAS DE
INFORMAÇÃO 53SISTEMAS DE
INFORMAÇÃO 5353SISTEMAS DE
INFORMAÇÃO
Notação 
≤? c ?
5454SISTEMAS DE
INFORMAÇÃO 5454SISTEMAS DE
INFORMAÇÃO 5454SISTEMAS DE
INFORMAÇÃO 54SISTEMAS DE
INFORMAÇÃO 5454SISTEMAS DE
INFORMAÇÃO 5454SISTEMAS DE
INFORMAÇÃO 54SISTEMAS DE
INFORMAÇÃO 54SISTEMAS DE
INFORMAÇÃO 5454 54SISTEMAS DE
INFORMAÇÃO 5454SISTEMAS DE
INFORMAÇÃO 54SISTEMAS DE
INFORMAÇÃO 5454SISTEMAS DE
INFORMAÇÃO 5454SISTEMAS DE
INFORMAÇÃO 54SISTEMAS DE
INFORMAÇÃO 5454SISTEMAS DE
INFORMAÇÃO
Notação 
≤? c ?
- c n2 – 2n >= 0( )
5555SISTEMAS DE
INFORMAÇÃO 5555SISTEMAS DE
INFORMAÇÃO 5555SISTEMAS DE
INFORMAÇÃO 55SISTEMAS DE
INFORMAÇÃO 5555SISTEMAS DE
INFORMAÇÃO 5555SISTEMAS DE
INFORMAÇÃO 55SISTEMAS DE
INFORMAÇÃO 55SISTEMAS DE
INFORMAÇÃO 5555 55SISTEMAS DE
INFORMAÇÃO 5555SISTEMAS DE
INFORMAÇÃO 55SISTEMAS DE
INFORMAÇÃO 5555SISTEMAS DE
INFORMAÇÃO 5555SISTEMAS DE
INFORMAÇÃO 55SISTEMAS DE
INFORMAÇÃO 5555SISTEMAS DE
INFORMAÇÃO
Notação 
≤
- c n2 – 2n >= 0( )
n2 – 2n >= 0
?
5656SISTEMAS DE
INFORMAÇÃO 5656SISTEMAS DE
INFORMAÇÃO 5656SISTEMAS DE
INFORMAÇÃO 56SISTEMAS DE
INFORMAÇÃO 5656SISTEMAS DE
INFORMAÇÃO 5656SISTEMAS DE
INFORMAÇÃO 56SISTEMAS DE
INFORMAÇÃO 56SISTEMAS DE
INFORMAÇÃO 5656 56SISTEMAS DE
INFORMAÇÃO 5656SISTEMAS DE
INFORMAÇÃO 56SISTEMAS DE
INFORMAÇÃO 5656SISTEMAS DE
INFORMAÇÃO 5656SISTEMAS DE
INFORMAÇÃO 56SISTEMAS DE
INFORMAÇÃO 5656SISTEMAS DE
INFORMAÇÃO
Notação 
≤
- c n2 – 2n >= 0( )
n2 – 2n >= 0
5757SISTEMAS DE
INFORMAÇÃO 5757SISTEMAS DE
INFORMAÇÃO 5757SISTEMAS DE
INFORMAÇÃO 57SISTEMAS DE
INFORMAÇÃO 5757SISTEMAS DE
INFORMAÇÃO 5757SISTEMAS DE
INFORMAÇÃO 57SISTEMAS DE
INFORMAÇÃO 57SISTEMAS DE
INFORMAÇÃO 5757 57SISTEMAS DE
INFORMAÇÃO 5757SISTEMAS DE
INFORMAÇÃO 57SISTEMAS DE
INFORMAÇÃO 5757SISTEMAS DE
INFORMAÇÃO 5757SISTEMAS DE
INFORMAÇÃO 57SISTEMAS DE
INFORMAÇÃO 5757SISTEMAS DE
INFORMAÇÃO
Notação 
n0
Ex: Qualquer algoritmo de ordenação é (n). Por quê?
5858SISTEMAS DE
INFORMAÇÃO 5858SISTEMAS DE
INFORMAÇÃO 5858SISTEMAS DE
INFORMAÇÃO 58SISTEMAS DE
INFORMAÇÃO 5858SISTEMAS DE
INFORMAÇÃO 5858SISTEMAS DE
INFORMAÇÃO 58SISTEMAS DE
INFORMAÇÃO 58SISTEMAS DE
INFORMAÇÃO 5858 58SISTEMAS DE
INFORMAÇÃO 5858SISTEMAS DE
INFORMAÇÃO 58SISTEMAS DE
INFORMAÇÃO 5858SISTEMAS DE
INFORMAÇÃO 5858SISTEMAS DE
INFORMAÇÃO 58SISTEMAS DE
INFORMAÇÃO 5858SISTEMAS DE
INFORMAÇÃO
Notação 
n0
Ex: Qualquer algoritmo de ordenação é (n). 
Porque no mínimo tem que conferir cada posição do array…
Mas é sempre interessante dar uma avaliação mais precisa
59
Profa. Ariane Machado Lima
Ex: InsertionSort é de quanto?
60
Profa. Ariane Machado Lima
Ex: InsertionSort é (n2)
(por conta do pior caso)
6161SISTEMAS DE
INFORMAÇÃO 6161SISTEMAS DE
INFORMAÇÃO 6161SISTEMAS DE
INFORMAÇÃO 61SISTEMAS DE
INFORMAÇÃO 6161SISTEMAS DE
INFORMAÇÃO 6161SISTEMAS DE
INFORMAÇÃO 61SISTEMAS DE
INFORMAÇÃO 61SISTEMAS DE
INFORMAÇÃO 6161 61SISTEMAS DE
INFORMAÇÃO 6161SISTEMAS DE
INFORMAÇÃO 61SISTEMAS DE
INFORMAÇÃO 6161SISTEMAS DE
INFORMAÇÃO 6161SISTEMAS DE
INFORMAÇÃO 61SISTEMAS DE
INFORMAÇÃO 6161SISTEMAS DE
INFORMAÇÃO
Notação 
 Definição:
 (g(n)) = {f(n): existem constantes positivas c1, c2 e n0 tais 
que 0 ≤ c1g(n) ≤ f(n) ≤ c2g(n), para todo n ≥ n0}
 Informalmente, dizemos que, se f(n) ∈ (g(n)), então 
f(n) cresce tão rapidamente quanto g(n).
c2g
f
c1g
6262SISTEMAS DE
INFORMAÇÃO 6262SISTEMAS DE
INFORMAÇÃO 6262SISTEMAS DE
INFORMAÇÃO 62SISTEMAS DE
INFORMAÇÃO 6262SISTEMAS DE
INFORMAÇÃO6262SISTEMAS DE
INFORMAÇÃO 62SISTEMAS DE
INFORMAÇÃO 62SISTEMAS DE
INFORMAÇÃO 6262 62SISTEMAS DE
INFORMAÇÃO 6262SISTEMAS DE
INFORMAÇÃO 62SISTEMAS DE
INFORMAÇÃO 6262SISTEMAS DE
INFORMAÇÃO 6262SISTEMAS DE
INFORMAÇÃO 62SISTEMAS DE
INFORMAÇÃO 6262SISTEMAS DE
INFORMAÇÃO
Notação 
6363SISTEMAS DE
INFORMAÇÃO 6363SISTEMAS DE
INFORMAÇÃO 6363SISTEMAS DE
INFORMAÇÃO 63SISTEMAS DE
INFORMAÇÃO 6363SISTEMAS DE
INFORMAÇÃO 6363SISTEMAS DE
INFORMAÇÃO 63SISTEMAS DE
INFORMAÇÃO 63SISTEMAS DE
INFORMAÇÃO 6363 63SISTEMAS DE
INFORMAÇÃO 6363SISTEMAS DE
INFORMAÇÃO 63SISTEMAS DE
INFORMAÇÃO 6363SISTEMAS DE
INFORMAÇÃO 6363SISTEMAS DE
INFORMAÇÃO 63SISTEMAS DE
INFORMAÇÃO 6363SISTEMAS DE
INFORMAÇÃO
Notação 
6464SISTEMAS DE
INFORMAÇÃO 6464SISTEMAS DE
INFORMAÇÃO 6464SISTEMAS DE
INFORMAÇÃO 64SISTEMAS DE
INFORMAÇÃO 6464SISTEMAS DE
INFORMAÇÃO 6464SISTEMAS DE
INFORMAÇÃO 64SISTEMAS DE
INFORMAÇÃO 64SISTEMAS DE
INFORMAÇÃO 6464 64SISTEMAS DE
INFORMAÇÃO 6464SISTEMAS DE
INFORMAÇÃO 64SISTEMAS DE
INFORMAÇÃO 6464SISTEMAS DE
INFORMAÇÃO 6464SISTEMAS DE
INFORMAÇÃO 64SISTEMAS DE
INFORMAÇÃO 6464SISTEMAS DE
INFORMAÇÃO
Notação 
6565SISTEMAS DE
INFORMAÇÃO 6565SISTEMAS DE
INFORMAÇÃO 6565SISTEMAS DE
INFORMAÇÃO 65SISTEMAS DE
INFORMAÇÃO 6565SISTEMAS DE
INFORMAÇÃO 6565SISTEMAS DE
INFORMAÇÃO 65SISTEMAS DE
INFORMAÇÃO 65SISTEMAS DE
INFORMAÇÃO 6565 65SISTEMAS DE
INFORMAÇÃO 6565SISTEMAS DE
INFORMAÇÃO 65SISTEMAS DE
INFORMAÇÃO 6565SISTEMAS DE
INFORMAÇÃO 6565SISTEMAS DE
INFORMAÇÃO 65SISTEMAS DE
INFORMAÇÃO 6565SISTEMAS DE
INFORMAÇÃO
Notação 
c2g
f
c1g
66
Profa. Ariane Machado Lima
Então InsertionSort é  (n2)
(por conta do pior caso)
6767SISTEMAS DE
INFORMAÇÃO 6767SISTEMAS DE
INFORMAÇÃO 6767SISTEMAS DE
INFORMAÇÃO 67SISTEMAS DE
INFORMAÇÃO 6767SISTEMAS DE
INFORMAÇÃO 6767SISTEMAS DE
INFORMAÇÃO 67SISTEMAS DE
INFORMAÇÃO 67SISTEMAS DE
INFORMAÇÃO 6767 67SISTEMAS DE
INFORMAÇÃO 6767SISTEMAS DE
INFORMAÇÃO 67SISTEMAS DE
INFORMAÇÃO 6767SISTEMAS DE
INFORMAÇÃO 6767SISTEMAS DE
INFORMAÇÃO 67SISTEMAS DE
INFORMAÇÃO 6767SISTEMAS DE
INFORMAÇÃO
Exercício
6868SISTEMAS DE
INFORMAÇÃO 6868SISTEMAS DE
INFORMAÇÃO 6868SISTEMAS DE
INFORMAÇÃO 68SISTEMAS DE
INFORMAÇÃO 6868SISTEMAS DE
INFORMAÇÃO 6868SISTEMAS DE
INFORMAÇÃO 68SISTEMAS DE
INFORMAÇÃO 68SISTEMAS DE
INFORMAÇÃO 6868 68SISTEMAS DE
INFORMAÇÃO 6868SISTEMAS DE
INFORMAÇÃO 68SISTEMAS DE
INFORMAÇÃO 6868SISTEMAS DE
INFORMAÇÃO 6868SISTEMAS DE
INFORMAÇÃO 68SISTEMAS DE
INFORMAÇÃO 6868SISTEMAS DE
INFORMAÇÃO
Exercício
6969SISTEMAS DE
INFORMAÇÃO 6969SISTEMAS DE
INFORMAÇÃO 6969SISTEMAS DE
INFORMAÇÃO 69SISTEMAS DE
INFORMAÇÃO 6969SISTEMAS DE
INFORMAÇÃO 6969SISTEMAS DE
INFORMAÇÃO 69SISTEMAS DE
INFORMAÇÃO 69SISTEMAS DE
INFORMAÇÃO 6969 69SISTEMAS DE
INFORMAÇÃO 6969SISTEMAS DE
INFORMAÇÃO 69SISTEMAS DE
INFORMAÇÃO 6969SISTEMAS DE
INFORMAÇÃO 6969SISTEMAS DE
INFORMAÇÃO 69SISTEMAS DE
INFORMAÇÃO 6969SISTEMAS DE
INFORMAÇÃO
Exercício
= (1) → constante!!!
7070SISTEMAS DE
INFORMAÇÃO 7070SISTEMAS DE
INFORMAÇÃO 7070SISTEMAS DE
INFORMAÇÃO 70SISTEMAS DE
INFORMAÇÃO 7070SISTEMAS DE
INFORMAÇÃO 7070SISTEMAS DE
INFORMAÇÃO 70SISTEMAS DE
INFORMAÇÃO 70SISTEMAS DE
INFORMAÇÃO 7070 70SISTEMAS DE
INFORMAÇÃO 7070SISTEMAS DE
INFORMAÇÃO 70SISTEMAS DE
INFORMAÇÃO 7070SISTEMAS DE
INFORMAÇÃO 7070SISTEMAS DE
INFORMAÇÃO 70SISTEMAS DE
INFORMAÇÃO 7070SISTEMAS DE
INFORMAÇÃO
Exercício
= (1) → constante!!!
Prove que = ( )
7171SISTEMAS DE
INFORMAÇÃO 7171SISTEMAS DE
INFORMAÇÃO 7171SISTEMAS DE
INFORMAÇÃO 71SISTEMAS DE
INFORMAÇÃO 7171SISTEMAS DE
INFORMAÇÃO 7171SISTEMAS DE
INFORMAÇÃO 71SISTEMAS DE
INFORMAÇÃO 71SISTEMAS DE
INFORMAÇÃO 7171 71SISTEMAS DE
INFORMAÇÃO 7171SISTEMAS DE
INFORMAÇÃO 71SISTEMAS DE
INFORMAÇÃO 7171SISTEMAS DE
INFORMAÇÃO 7171SISTEMAS DE
INFORMAÇÃO 71SISTEMAS DE
INFORMAÇÃO 7171SISTEMAS DE
INFORMAÇÃO
Exercício
= (1) → constante!!!
Prove que = ( )
0 <= c1 <= <= c2 para n >= n0
Existem c1, c2 e n0 
constantes positivas tal que
Existem c1, c2 e n0 
constantes positivas tal que
7272SISTEMAS DE
INFORMAÇÃO 7272SISTEMAS DE
INFORMAÇÃO 7272SISTEMAS DE
INFORMAÇÃO 72SISTEMAS DE
INFORMAÇÃO 7272SISTEMAS DE
INFORMAÇÃO 7272SISTEMAS DE
INFORMAÇÃO 72SISTEMAS DE
INFORMAÇÃO 72SISTEMAS DE
INFORMAÇÃO 7272 72SISTEMAS DE
INFORMAÇÃO 7272SISTEMAS DE
INFORMAÇÃO 72SISTEMAS DE
INFORMAÇÃO 7272SISTEMAS DE
INFORMAÇÃO 7272SISTEMAS DE
INFORMAÇÃO 72SISTEMAS DE
INFORMAÇÃO 7272SISTEMAS DE
INFORMAÇÃO
Exercício
= (1) → constante!!!
Prove que = ( )
0 <= c1 <= <= c2 para n >= n0
Existem c1, c2 e n0 
constantes positivas tal que
Existem c1, c2 e n0 
constantes positivas tal que
Ex: c1 = c2 = n0 = 1
 c1 = 0.5, c2 = 2, n0 = 0.1 (não podem ser 0…)
7373SISTEMAS DE
INFORMAÇÃO 7373SISTEMAS DE
INFORMAÇÃO 7373SISTEMAS DE
INFORMAÇÃO 73SISTEMAS DE
INFORMAÇÃO 7373SISTEMAS DE
INFORMAÇÃO 7373SISTEMAS DE
INFORMAÇÃO 73SISTEMAS DE
INFORMAÇÃO 73SISTEMAS DE
INFORMAÇÃO 7373 73SISTEMAS DE
INFORMAÇÃO 7373SISTEMAS DE
INFORMAÇÃO 73SISTEMAS DE
INFORMAÇÃO 7373SISTEMAS DE
INFORMAÇÃO 7373SISTEMAS DE
INFORMAÇÃO 73SISTEMAS DE
INFORMAÇÃO 7373SISTEMAS DE
INFORMAÇÃO
Exercício
= (1) → constante!!!
n logn = ? (n2) – Prove
?
7474SISTEMAS DE
INFORMAÇÃO 7474SISTEMAS DE
INFORMAÇÃO 7474SISTEMAS DE
INFORMAÇÃO 74SISTEMAS DE
INFORMAÇÃO 7474SISTEMAS DE
INFORMAÇÃO 7474SISTEMAS DE
INFORMAÇÃO 74SISTEMAS DE
INFORMAÇÃO 74SISTEMAS DE
INFORMAÇÃO 7474 74SISTEMAS DE
INFORMAÇÃO 7474SISTEMAS DE
INFORMAÇÃO 74SISTEMAS DE
INFORMAÇÃO 7474SISTEMAS DE
INFORMAÇÃO 7474SISTEMAS DE
INFORMAÇÃO 74SISTEMAS DE
INFORMAÇÃO 7474SISTEMAS DE
INFORMAÇÃO
Exercício
= (1) → constante!!!
n logn = ? (n2) – Prove
n logn = O(n2), pois existem constantes positivas c e n0 tais que:
0 <= n logn <= cn2, para todo n >= n0
Isso vale para c = ?, n0 = ? 
O
7575SISTEMAS DE
INFORMAÇÃO 7575SISTEMAS DE
INFORMAÇÃO 7575SISTEMAS DE
INFORMAÇÃO 75SISTEMAS DE
INFORMAÇÃO 7575SISTEMAS DE
INFORMAÇÃO 7575SISTEMAS DE
INFORMAÇÃO 75SISTEMAS DE
INFORMAÇÃO 75SISTEMAS DE
INFORMAÇÃO 7575 75SISTEMAS DE
INFORMAÇÃO 7575SISTEMAS DE
INFORMAÇÃO 75SISTEMAS DE
INFORMAÇÃO 7575SISTEMAS DE
INFORMAÇÃO 7575SISTEMAS DE
INFORMAÇÃO 75SISTEMAS DE
INFORMAÇÃO 7575SISTEMAS DE
INFORMAÇÃO
Exercício
= (1) → constante!!!
n logn = ? (n2) – Prove
n logn = O(n2), pois existem constantes positivas c e n0 tais que:
0 <= n logn <= cn2, para todo n >= n0
Isso vale para c = 1, n0 = 2 
O
7676SISTEMAS DE
INFORMAÇÃO 7676SISTEMAS DE
INFORMAÇÃO 7676SISTEMAS DE
INFORMAÇÃO 76SISTEMAS DE
INFORMAÇÃO 7676SISTEMAS DE
INFORMAÇÃO 7676SISTEMAS DE
INFORMAÇÃO 76SISTEMAS DE
INFORMAÇÃO 76SISTEMAS DE
INFORMAÇÃO 7676 76SISTEMAS DE
INFORMAÇÃO 7676SISTEMAS DE
INFORMAÇÃO 76SISTEMAS DE
INFORMAÇÃO 7676SISTEMAS DE
INFORMAÇÃO 7676SISTEMAS DE
INFORMAÇÃO 76SISTEMAS DE
INFORMAÇÃO 7676SISTEMAS DE
INFORMAÇÃO
Exercício
= (1) → constante!!!
n2 = ? (n logn) – Prove
O
?
7777SISTEMAS DE
INFORMAÇÃO 7777SISTEMAS DE
INFORMAÇÃO 7777SISTEMAS DE
INFORMAÇÃO 77SISTEMAS DE
INFORMAÇÃO 7777SISTEMAS DE
INFORMAÇÃO 7777SISTEMAS DE
INFORMAÇÃO 77SISTEMAS DE
INFORMAÇÃO 77SISTEMAS DE
INFORMAÇÃO 7777 77SISTEMAS DE
INFORMAÇÃO 7777SISTEMAS DE
INFORMAÇÃO 77SISTEMAS DE
INFORMAÇÃO 7777SISTEMAS DE
INFORMAÇÃO 7777SISTEMAS DE
INFORMAÇÃO 77SISTEMAS DE
INFORMAÇÃO 7777SISTEMAS DE
INFORMAÇÃO
Exercício
= (1) → constante!!!
n2 = ? (n logn) – Prove
n2 = Ω(n logn), pois 
O
?
7878SISTEMAS DE
INFORMAÇÃO 7878SISTEMAS DE
INFORMAÇÃO 7878SISTEMAS DE
INFORMAÇÃO 78SISTEMAS DE
INFORMAÇÃO 7878SISTEMAS DE
INFORMAÇÃO 7878SISTEMAS DE
INFORMAÇÃO 78SISTEMAS DE
INFORMAÇÃO 78SISTEMAS DE
INFORMAÇÃO 7878 78SISTEMAS DE
INFORMAÇÃO 7878SISTEMAS DE
INFORMAÇÃO 78SISTEMAS DE
INFORMAÇÃO 7878SISTEMAS DE
INFORMAÇÃO 7878SISTEMAS DE
INFORMAÇÃO 78SISTEMAS DE
INFORMAÇÃO 7878SISTEMAS DE
INFORMAÇÃO
Exercício
= (1) → constante!!!
n2 = ? (n logn) – Prove
n2 = Ω(n logn), pois existem constantes positivas c e n0 tais que:
0 <= c n logn <= n2, para todo n >= n0
Isso vale para c = ?, n0 = ? 
O
7979SISTEMAS DE
INFORMAÇÃO 7979SISTEMAS DE
INFORMAÇÃO 7979SISTEMAS DE
INFORMAÇÃO 79SISTEMAS DE
INFORMAÇÃO 7979SISTEMAS DE
INFORMAÇÃO 7979SISTEMAS DE
INFORMAÇÃO 79SISTEMAS DE
INFORMAÇÃO 79SISTEMASDE
INFORMAÇÃO 7979 79SISTEMAS DE
INFORMAÇÃO 7979SISTEMAS DE
INFORMAÇÃO 79SISTEMAS DE
INFORMAÇÃO 7979SISTEMAS DE
INFORMAÇÃO 7979SISTEMAS DE
INFORMAÇÃO 79SISTEMAS DE
INFORMAÇÃO 7979SISTEMAS DE
INFORMAÇÃO
Exercício
= (1) → constante!!!
n2 = ? (n logn) – Prove
n2 = Ω(n logn), pois existem constantes positivas c e n0 tais que:
0 <= c n logn <= n2, para todo n >= n0
Isso vale para c = 1, n0 = 2 
O
Ω
8080SISTEMAS DE
INFORMAÇÃO 8080SISTEMAS DE
INFORMAÇÃO 8080SISTEMAS DE
INFORMAÇÃO 80SISTEMAS DE
INFORMAÇÃO 8080SISTEMAS DE
INFORMAÇÃO 8080SISTEMAS DE
INFORMAÇÃO 80SISTEMAS DE
INFORMAÇÃO 80SISTEMAS DE
INFORMAÇÃO 8080 80SISTEMAS DE
INFORMAÇÃO 8080SISTEMAS DE
INFORMAÇÃO 80SISTEMAS DE
INFORMAÇÃO 8080SISTEMAS DE
INFORMAÇÃO 8080SISTEMAS DE
INFORMAÇÃO 80SISTEMAS DE
INFORMAÇÃO 8080SISTEMAS DE
INFORMAÇÃO
Exercício
= (1) → constante!!!
Ω
O
Obs: Prove que n logn NÃO é Ω(n2) 
8181SISTEMAS DE
INFORMAÇÃO 8181SISTEMAS DE
INFORMAÇÃO 8181SISTEMAS DE
INFORMAÇÃO 81SISTEMAS DE
INFORMAÇÃO 8181SISTEMAS DE
INFORMAÇÃO 8181SISTEMAS DE
INFORMAÇÃO 81SISTEMAS DE
INFORMAÇÃO 81SISTEMAS DE
INFORMAÇÃO 8181 81SISTEMAS DE
INFORMAÇÃO 8181SISTEMAS DE
INFORMAÇÃO 81SISTEMAS DE
INFORMAÇÃO 8181SISTEMAS DE
INFORMAÇÃO 8181SISTEMAS DE
INFORMAÇÃO 81SISTEMAS DE
INFORMAÇÃO 8181SISTEMAS DE
INFORMAÇÃO
Exercício
= (1) → constante!!!
Ω
O
Obs: Prove que n logn NÃO é Ω(n2) 
Se fosse, então existiriam constantes positivas c e n0 tais que:
0 <= cn2 <= n logn, para todo n >= n0
Se fosse verdade, 0 <= cn < = logn => c <= logn /n para todo n >= n0
Mas lim n→∞ logn / n = 0, MAS c deve ser positiva! CONTRADIÇÃO 
8282SISTEMAS DE
INFORMAÇÃO 8282SISTEMAS DE
INFORMAÇÃO 8282SISTEMAS DE
INFORMAÇÃO 82SISTEMAS DE
INFORMAÇÃO 8282SISTEMAS DE
INFORMAÇÃO 8282SISTEMAS DE
INFORMAÇÃO 82SISTEMAS DE
INFORMAÇÃO 82SISTEMAS DE
INFORMAÇÃO 8282 82SISTEMAS DE
INFORMAÇÃO 8282SISTEMAS DE
INFORMAÇÃO 82SISTEMAS DE
INFORMAÇÃO 8282SISTEMAS DE
INFORMAÇÃO 8282SISTEMAS DE
INFORMAÇÃO 82SISTEMAS DE
INFORMAÇÃO 8282SISTEMAS DE
INFORMAÇÃO
Exercício
= (1) → constante!!!
Ω
O
Obs: Prove que n logn NÃO é Ω(n2) 
Se fosse, então existiriam constantes positivas c e n0 tais que:
0 <= cn2 <= n logn, para todo n >= n0
Se fosse verdade, quem poderia ser esse c e n0?
8383SISTEMAS DE
INFORMAÇÃO 8383SISTEMAS DE
INFORMAÇÃO 8383SISTEMAS DE
INFORMAÇÃO 83SISTEMAS DE
INFORMAÇÃO 8383SISTEMAS DE
INFORMAÇÃO 8383SISTEMAS DE
INFORMAÇÃO 83SISTEMAS DE
INFORMAÇÃO 83SISTEMAS DE
INFORMAÇÃO 8383 83SISTEMAS DE
INFORMAÇÃO 8383SISTEMAS DE
INFORMAÇÃO 83SISTEMAS DE
INFORMAÇÃO 8383SISTEMAS DE
INFORMAÇÃO 8383SISTEMAS DE
INFORMAÇÃO 83SISTEMAS DE
INFORMAÇÃO 8383SISTEMAS DE
INFORMAÇÃO
Exercício
= (1) → constante!!!
Ω
O
Obs: Prove que n logn NÃO é Ω(n2) 
Se fosse, então existiriam constantes positivas c e n0 tais que:
0 <= cn2 <= n logn, para todo n >= n0
Se fosse verdade, 0 <= cn < = logn => c <= logn /n para todo n >= n0
Mas lim n→∞ logn / n = 0, MAS c deve ser positiva! CONTRADIÇÃO 
8484SISTEMAS DE
INFORMAÇÃO 8484SISTEMAS DE
INFORMAÇÃO 8484SISTEMAS DE
INFORMAÇÃO 84SISTEMAS DE
INFORMAÇÃO 8484SISTEMAS DE
INFORMAÇÃO 8484SISTEMAS DE
INFORMAÇÃO 84SISTEMAS DE
INFORMAÇÃO 84SISTEMAS DE
INFORMAÇÃO 8484 84SISTEMAS DE
INFORMAÇÃO 8484SISTEMAS DE
INFORMAÇÃO 84SISTEMAS DE
INFORMAÇÃO 8484SISTEMAS DE
INFORMAÇÃO 8484SISTEMAS DE
INFORMAÇÃO 84SISTEMAS DE
INFORMAÇÃO 8484SISTEMAS DE
INFORMAÇÃO
Exercício
= (1) → constante!!!
Ω
O
FAÇAM AS PROVAS FORMAIS PARA OS DEMAIS!!!!
(Inclusive para o que NÃO É)
8585SISTEMAS DE
INFORMAÇÃO 8585SISTEMAS DE
INFORMAÇÃO 8585SISTEMAS DE
INFORMAÇÃO 85SISTEMAS DE
INFORMAÇÃO 8585SISTEMAS DE
INFORMAÇÃO 8585SISTEMAS DE
INFORMAÇÃO 85SISTEMAS DE
INFORMAÇÃO 85SISTEMAS DE
INFORMAÇÃO 8585 85SISTEMAS DE
INFORMAÇÃO 8585SISTEMAS DE
INFORMAÇÃO 85SISTEMAS DE
INFORMAÇÃO 8585SISTEMAS DE
INFORMAÇÃO 8585SISTEMAS DE
INFORMAÇÃO 85SISTEMAS DE
INFORMAÇÃO 8585SISTEMAS DE
INFORMAÇÃO
https://www.ime.usp.br/~pf/analise_de_algoritmos/aulas/Oh.html
Além de explicações, há 3 listas de exercícios. FAÇAM! (Cai na 
prova...)
Material extra sobre O,   
https://www.ime.usp.br/~pf/analise_de_algoritmos/aulas/Oh.html
8686SISTEMAS DE
INFORMAÇÃO 8686SISTEMAS DE
INFORMAÇÃO 8686SISTEMAS DE
INFORMAÇÃO 86SISTEMAS DE
INFORMAÇÃO 8686SISTEMAS DE
INFORMAÇÃO 8686SISTEMAS DE
INFORMAÇÃO 86SISTEMAS DE
INFORMAÇÃO 86SISTEMAS DE
INFORMAÇÃO 8686 86SISTEMAS DE
INFORMAÇÃO 8686SISTEMAS DE
INFORMAÇÃO 86SISTEMAS DE
INFORMAÇÃO 8686SISTEMAS DE
INFORMAÇÃO 8686SISTEMAS DE
INFORMAÇÃO 86SISTEMAS DE
INFORMAÇÃO 8686SISTEMAS DE
INFORMAÇÃO
Referências
 Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest & Clifford 
Stein. Algoritmos - Tradução da 2a. Edição Americana. Editora Campus, 
2002 (Capítulo 3).
 Michael T. Goodrich & Roberto Tamassia. Estruturas de Dados e 
Algoritmos em Java. Editora Bookman, 4a. Ed. 2007 (Capítulo 4).
 Nívio Ziviani. Projeto de Algoritmos com implementações em C e Pascal. 
Editora Thomson, 2a. Edição, 2004 (Seção 1.3).
 Notas de aula dos professores Marcos Chaim, Cid de Souza, Cândida da 
Silva e Delano M. Beder.
 Notas de aula dos professores Fátima L. S. Nunes e Norton T. Roman
	Slide 1
	Slide 2
	Slide 3
	Slide 4
	Slide 5
	Slide 6
	Slide 7
	Slide 8
	Slide 9
	Slide 10
	Slide 11
	Slide 12
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Slide 17
	Slide 18
	Slide 19
	Slide 20
	Slide 22
	Slide 23
	Slide 24
	Slide 25
	Slide 26
	Slide 27
	Slide 28
	Slide 29
	Slide 30
	Slide 31
	Slide 32
	Slide 33
	Slide 34
	Slide 35
	Slide 36
	Slide 37
	Slide 38
	Slide 39
	Slide 40
	Slide 41
	Slide 42
	Slide 43
	Slide 44
	Slide 45
	Slide 46
	Slide 47
	Slide 48
	Slide 49
	Slide 50
	Slide 51
	Slide 52
	Slide 53
	Slide 54
	Slide 55
	Slide 56
	Slide 57
	Slide 58
	Slide 59
	Slide 60
	Slide 61
	Slide 62
	Slide 63
	Slide 64
	Slide 65
	Slide 66
	Slide 67
	Slide 68
	Slide 69
	Slide 70
	Slide 71
	Slide 72
	Slide 73
	Slide 74
	Slide 75
	Slide 76
	Slide 77
	Slide 78
	Slide 79
	Slide 80
	Slide 81
	Slide 82
	Slide 83
	Slide 84
	Slide 85
	Slide 86