+ +Análise+Assintótica (1)

Prévia do material em texto

Análise Assintótica 
Análise assintótica de algoritmos 
Muitas vezes precisamos otimizar códigos para aumentar a robustez e velocidade de 
sistemas. 
O que vem a ser análise assintótica? 
Fazer uma análise assintótica é se preocupar com valores grandes de entrada para o 
processamento do algoritmo, com o intuito de calcular o tempo total de processamento e 
viabilidade para determinados casos. 
Muitas vezes com isso podemos ser capazes de saber se é necessária a utilização de outra 
metodologia ou ferramenta para a realização de uma tarefa. 
 
16:05:22 
Análise Assintótica 
Importante: 
mesmo sendo uma área de extrema importância na informática, não é comum à maioria 
dos ‘profissionais’ do mercado atual praticá-la. Alguns dos motivos para isso são: 
• profissionais com boa capacidade desse tipo de análise são caros para a maioria das 
empresas; 
• gerentes de projeto não veem o tempo gasto para isso como um tempo útil e preferem 
ver resultados imediatos 
• Profissionais estudam essa disciplina no ensino superior apenas como uma disciplina 
complementar e também preferem matérias mais práticas ou mais fáceis (visto 
que, no geral, matemática é uma disciplina complexa) 
16:05:23 
Análise Assintótica 
Pensar assintoticamente requer uma visão mais além do projeto, visualizando até onde o 
sistema pode chegar. 
Na análise assintótica, temos o conceito de notação assintótica, que é a 
representação matemática criada por Paul Bachmann no século XIX. Nela, temos 
três notações comuns para classificar as ordens das funções, essas ordens 
determinam a equivalência das funções, ou seja podemos ter uma função que seja 
to tipo n², essa função é equivalente à função 400n². São equivalentes assintoticamente 
falando, lembrando que sempre nos preocupamos com valores de entrada grandes 
para n. 
As três principais classificações de ordem são: Ordem O, Ordem Omega e Ordem 
Theta. 
16:05:23 
Análise Assintótica 
Notação Assintótica: Notação O ou Big O. 
• Análise assintótica dos programas: mede como f(n) se comporta conforme n aumenta 
indefinidamente; 
• Uma função f(n) é O(g(n)) (notação f(n) = O(g(n))) se existem duas constantes positivas c e 
m tais que f(n) ≤ c.g(n), para todo n ≥ m; 
• f(n) = O(g(n)): g(n) é limite superior para f(n); 
16:05:23 
Análise Assintótica 
Funções de complexidade frequentes 
16:05:24 
Análise Assintótica 
Notação Assintótica: Notação Ω 
Uma função g(n) é Ω(f(n)), notação g(n) = Ω(f(n)), se existem duas constantes positivas c e 
m tais que g(n) ≥ c.f(n), para todo n ≥ m; 
• g(n) = Ω(f(n)): f(n) é limite inferior para g(n) (tempo mínimo do algoritmo); 
16:05:24 
Análise Assintótica 
Notação Assintótica: Notação Θ 
Uma função g(n) é Θ(f(n)), notação g(n) = Θ(f(n)), se existem três constantes positivas 
c1, c2 e m tais que 0 ≤ c1.f(n) ≤ g(n) ≤ c2.f(n), para todo n ≥ m; 
• g(n) = Θ(f(n)): f(n) é limite restrito para g(n) ou limite assintótico firme; 
16:05:24 
Análise Assintótica 
Notação Assintótica: Notações o e ω 
Uma função g(n) é o(f(n)), notação g(n) = o(f(n)), se, para qualquer constante c > 0, 
temos 0 ≤ g(n) < c.f(n), para todo n ≥ m; 
 
Uma função g(n) é ω(f(n)), notação g(n) = ω(f(n)), se, para qualquer constante c > 0, 
temos 0 ≤ c.f(n) < g(n), para todo n ≥ m; 
16:05:26 
Análise Assintótica 
Analogia com os números reais: 
 
𝐹 𝑛 = 𝑂 𝑔 𝑛 ≅ 𝐹 ≤ 𝑔 
𝐹 𝑛 = Ω 𝑔 𝑛 ≅ 𝐹 ≥ 𝑔 
𝐹 𝑛 = 𝜃 𝑔 𝑛 ≅ 𝐹 = 𝑔 
𝐹 𝑛 = 𝑜 𝑔 𝑛 ≅ 𝐹 < 𝑔 
𝐹 𝑛 = 𝜔 𝑔 𝑛 ≅ 𝐹 > 𝑔 
 
16:05:26 
Análise Assintótica 
Resumo: 
 Análise assintótica: ordens O, Omega e Theta 
A análise de algoritmos faz exatamente o contrário: ignora os valores pequenos e concentra-
se nos valores enormes de n. Para valores enormes de n, as funções 
 
n2 , (3/2)n2 , 9999n2 , n2/1000 , n2+100n , etc. 
 
crescem todas com a mesma velocidade e portanto são todas "equivalentes". 
Esse tipo de matemática, interessado somente em valores enormes de n, é 
chamado assintótico. 
Nessa matemática, as funções são classificadas em "ordens“; todas as funções de uma 
mesma ordem são "equivalentes". As cinco funções acima, por exemplo, pertencem à 
mesma ordem. 
16:05:26 
Análise Assintótica 
Exemplos: 
 
Verifique se as afirmativas são corretas. No pior caso, o algoritmo de inserção é O(g(n)). 
a. 2𝑛+1 ≤ 𝑂(2𝑛) 
2𝑛+1 ≤ 𝑂(2𝑛) 
2𝑛 ∗ 21 ≤ 𝑐 ∗ 2𝑛 
𝑐 ∗ 2𝑛 ≥ 2𝑛 ∗ 21 
𝑐 ≥ 
2𝑛 ∗ 2
2𝑛
 
𝑐 ≥ 2 
𝑓 𝑛 ≤ 𝑐 ∗ 𝑔(𝑛), para todo n ≥ m; 
Resposta: Verdadeiro, pois existe um 𝑐 ≥ 2 que atende as necessidades do problema. 
16:05:27 
Análise Assintótica 
Exemplos: 
 
Verifique se as afirmativas são corretas. No pior caso, o algoritmo de inserção é O(g(n)). 
𝑓 𝑛 ≤ 𝑐 ∗ 𝑔(𝑛), para todo n ≥ m; a. 22𝑛 ≤ 𝑂(2𝑛) 
22𝑛 ≤ 𝑂(2𝑛) 
22𝑛 ≤ 𝑐 ∗ 2𝑛 
𝑐 ∗ 2𝑛 ≥ 22𝑛 
𝑐 ≥ 
22𝑛
2𝑛
 
𝑐 ≥
2𝑛 ∗ 2𝑛
2𝑛
 
𝑐 ≥ 2𝑛 
Resposta: Falso, pois não existe uma constante 𝑐 que atende as necessidades do problema. 
16:05:27 
Análise Assintótica 
Exemplos: 
 
Verifique se as afirmativas são corretas. No pior caso, o algoritmo de inserção é O(g(n)). 
𝑓 𝑛 ≤ 𝑐 ∗ 𝑔(𝑛), para todo n ≥ m; a. 𝑂 𝑛2 +𝑂 𝑛2 = 𝑂 𝑛2 
𝐶1𝑛
2 + 𝐶2𝑛
2 ≤ 𝐶3𝑛
2 
(𝐶1+𝐶2)𝑛
2 ≤ 𝐶3𝑛
2 
Resposta: Verdadeiro, pois existe um 𝑐 que atende as necessidades do problema. 
16:05:27 
Análise Assintótica 
Dominação assintótica: É a função que foi comparada e ganhou mais vezes. 
16:05:28 
Análise Assintótica 
Exemplos: 
16:05:28 
3𝑛2 + 5𝑛 = 𝑂(𝑛2) 
3𝑛2 + 5𝑛 ≤ 𝐶. 𝑛2 
3𝑛2 + 5𝑛
𝑛2
≤ 𝐶 
3+ 
5𝑛
𝑛2
≤ 𝐶 
Falso 
Análise Assintótica 
Verifica_algo(int n) 
{ int x, y 
 for (𝑥 = 0; 𝑥 < 𝑛; 𝑥 + +) 
 for(𝑦 = 0; 𝑦 < 𝑛; 𝑦 + +) 
 {faz_algo} 
} 
 1
𝑛−1
𝑦=0
𝑛−1
𝑥=0
 1. 1
𝑛−1
𝑦=0
= 𝑛 − 1 + 0 + 1 = 𝑛 
2. 𝑛
𝑛−1
𝑥=0
= 𝑛 ∗ 1 = 𝑛(
𝑛−1
𝑥=0
𝑛 − 1 + 0 + 1) = 𝒏𝟐 
𝑶(𝒏𝟐) 
16:05:28 
Análise Assintótica 
Exemplo: 
𝑓 𝑛 = 21,7𝑛 𝑓 𝑛 = 𝑂 2𝑛 ? ? ? 
21,7𝑛 ≤ 𝑐 ∗ 2𝑛 
21,7𝑛/2𝑛 ≤ 𝑐 
𝑐 ≥
21,7𝑛
2𝑛
 
𝑐 ≥
21,7𝑛
2𝑛
 
𝑐 ≥ 21,7𝑛 ∗ 2−𝑛 
𝑐 ≥ 2𝑛(1,7−1) 
𝒄 ≥ 𝟐𝟎,𝟕𝒏 
Falsa: não existe uma constante 
positiva c / 𝟐𝟏,𝟕𝒏 ≤ 𝒄 ∗ 𝟐𝒏 para n > m. 
16:05:28 
Análise Assintótica 
16:05:29 
Fórmulas de somatórios: 
 𝒊 =
𝒏 𝒏+ 𝟏
𝟐
𝒏
𝒊=𝟏
 
 𝒊𝟐 =
𝒏 𝒏 + 𝟏 (𝟐𝒏 + 𝟏)
𝟔
𝒏
𝒊=𝟏
 
 𝟏 = 𝒏 − 𝟏 + 𝟏 = 𝒏
𝒏
𝒊=𝟏
 
 𝒄𝒋 =
𝒄𝒋+𝟏 − 𝟏
𝒄 − 𝟏
𝒏
𝒋=𝟎
 
Análise Assintótica 
Exemplo: 
 
For(x=0; x< n; x++){ 
 for(y=0; y<x , y++){ 
 for(z=y; z<x; z++) 
 faz_algo 
 } 
 } 
} 
Resposta: 
 
𝑛−1
𝑥=0
 
 𝑥−1
𝑦=0
 1
𝑥−1
𝑧=𝑦
 
 1
𝑥−1
𝑧=𝑦
 𝑥−1 
𝑦=0
𝑛−1
𝑥=0
 
 1 = 𝑥 − 1 − 𝑦 + 1 = 𝒙 − 𝒚
𝑥−1
𝑧=𝑦
 
 𝑥 − 𝑦 =
 𝑥−1
𝑦=0
𝑛−1
𝑥=0
 𝑥 − 𝑦
 𝑥−1
𝑦=0
 𝑥−1
𝑦=0
= 𝑥 1− 𝑦
 𝑥−1
𝑦=0
 𝑥−1
𝑦=0
 
 (𝑥2 −
𝑥2 + 𝑥
2
)
𝑛−1
𝑥=0
=
𝑛 − 1 ∗ 𝑛 − 1 + 1 ∗ (2 ∗ 𝑛 − 1 + 1)
6
+
𝑛 𝑛 − 1
4
 = O(𝒏𝟑) 
16:05:29 
Análise Assintótica 
Exemplo: 
 
For(i=1; i<= n; i=i+1){ 
 for(z=0; z<i , z++){ 
 faz_algo 
 } 
} 
16:05:29 
Análise Assintótica 
16:05:30 
𝑃𝑒𝑠𝑞𝑢𝑖𝑠𝑎 𝑛 ; 
𝑖𝑓 𝑛 ≤ 1 
𝑡ℎ𝑒𝑛 𝐼′ 𝑛𝑠𝑝𝑒𝑐𝑖𝑜𝑛𝑒 𝑜 𝑒𝑙𝑒𝑚𝑒𝑛𝑡𝑜′ 
𝑒𝑙𝑠𝑒 𝑏𝑒𝑔𝑖𝑛 
 𝑃𝑎𝑟𝑎 𝑐𝑎𝑑𝑎 𝑢𝑚 𝑑𝑜𝑠𝑛 𝑒𝑙𝑒𝑚𝑒𝑛𝑡𝑜𝑠 𝑖′ 𝑛𝑠𝑝𝑒𝑐𝑖𝑜𝑛𝑒 𝑒𝑙𝑒𝑚𝑒𝑛𝑡𝑜′′ 
 𝑃𝑒𝑠𝑞𝑢𝑖𝑠𝑎
𝑛
3
; 
 𝑒𝑛𝑑; 
 𝒄𝒊
𝒏
𝒊=𝟎
= 
𝒄𝒏+𝟏 − 𝟏
𝒄 − 𝟏
 
𝑻 𝒏 = 𝒏 + 𝒕(
𝒏
𝟑
) 
𝑻 𝟏 = 𝟏 
𝑹𝒆𝒔𝒑𝒐𝒔𝒕𝒂 =
𝟑𝒏
𝟐
−
𝟏
𝟐
 
Análise Assintótica 
16:05:30 
𝑣𝑒𝑟𝑖𝑓𝑖𝑐𝑎 𝑎𝑙𝑔𝑜 (𝑖𝑛𝑡 𝑛){ 
 𝑖𝑛𝑡 𝑥, 𝑦, 
 𝑖𝑓 (𝑛 > 0){ 
 𝑓𝑜𝑟 𝑦 = 0, 𝑦 < 3; 𝑦 + + 
 𝑉𝑒𝑟𝑖𝑓𝑖𝑐𝑎 𝑎𝑙𝑔𝑜 
𝑛
4
, 
 𝑓𝑜𝑟 𝑥 = 1, 𝑥 ≤ 𝑛; 𝑥 + + } 
 𝑓𝑎𝑧 𝑎𝑙𝑔𝑜; } 
 
𝑻 𝒏 = 𝟑𝑻
𝒏
𝟒
 + 𝒏 
𝑻 𝟏 = 𝟎 
 𝑇(
𝑛
4
)
2
𝑦=0
+ 1
𝑛
𝑥=1
 
𝑹𝒆𝒔𝒑𝒐𝒔𝒕𝒂 = −𝟒𝒏(
𝒏𝒍𝒐𝒈𝟒𝟑 − 𝐧
𝐧
) 
Análise Assintótica 
16:05:30 
𝑓𝑜𝑟 𝑗 = 0; 𝑗 < 𝑛; 𝑗 + + 
 𝑓𝑜𝑟 𝑖 = 1; 𝑖 < 𝑛 ; 𝑖 = 𝑖 + 𝑖 
 𝑓𝑎𝑧 𝑎𝑙𝑔𝑜; } 
 } 
} 
 
 1 = log2 𝑛 − 1 + 1
log2 𝑛−1
𝑖=1
𝑛−1
𝑗=0
 
𝑖 = 1, 2, 4, 8, 16, …… . . 
 
 20, 21 , 22 , 23. … . . 
 
log2 1, log2 2, log2 3, log2 4 
 log2 𝑛
𝑛−1
𝑗=0
 log2 𝑛 1
𝑛−1
𝑗=0
 log2 𝑛 𝑛 − 1 + 1 = 𝑛 log2 𝑛 
Análise Assintótica 
16:05:31 
Análise Assintótica 
16:05:31 
Análise Assintótica 
16:05:31 
Análise Assintótica 
16:05:31 
Análise Assintótica 
ZIVIANI, N. Projeto de Algoritmos: com implementações em Pascal e C, 2a edição, Cengage 
Learning, 2009. 
Bibliografia 
16:05:31 
Recorrência 
16:05:32