CCF140-2
6 pág.

CCF140-2


DisciplinaAnálise de Algoritmos191 materiais713 seguidores
Pré-visualização2 páginas
14 
 
 
CCF140 Analise de Algoritmos 
 
Comportamento Assintótico de Funções 
Voltando ao custo de execução de um algoritmo, para pequenas instâncias ( n 
pequeno), qualquer algoritmo custa pouco para ser executado, mesmo os ineficientes. 
Logo, a análise de algoritmos é realizada para valores grandes de n, isto é, estuda-se 
o comportamento assintótico das funções de custo, observe a comparação abaixo 
onde desprezamos constantes multiplicativas e termos de menor ordem: 
 N = 100 N=1000 N=104 N=106 N=109 
log(n) 2 3 4 6 9 
n 100 1000 10000 106 109 
nlog(n) 200 3000 40000 6×106 9×109 
n2 104 106 108 1012 1018 
100n2+15n 1,0015×106 1,00015×108 
 \u22481010 \u22481012 \u22481020 
2n \u22481,26×1030 \u22481,07×10304 ? ? ? 
O comportamento assintótico de f(n) representa o limite do comportamento do custo 
quando n cresce. 
Observe o comportamento assintótico das funções f(n) = 2n, n3, n2, nlg(n), n e lg(n) 
 
 
Knuth sugeriu uma notação para dominação assintótica pois a análise de algoritmos 
precisa de uma matemática que associa n2 com: (3/2)n2 , 9999n2 , n2/1000 , 
n2+100n, etc. Esse tipo de matemática é "assintótico" (pois está interessado 
somente em valores grandes de n). 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. 
 
 
 
 15 
 
 
 
 Ordem O 
Antes de dar uma definição do conceito de ordem, convém restringir a atenção a 
funções assintoticamente não-negativas, ou seja, funções f tais que f(n) \u2265 0 para todo 
n suficientemente grande. (Mais explicitamente: f é assintoticamente não-negativa se 
existe n0 tal que f(n) \u2265 0 para todo n maior que n0.) 
Definição 1: 
Dadas funções assintoticamente não-negativas f e g, dizemos que f está na ordem O 
de g, e escrevemos f = O(g), se 0 \u2264 f(n) \u2264 c \u2022 g(n) para algum c positivo e para 
todo n suficientemente grande. 
Ou seja, existe um número positivo c e um número n0 tais que f(n) \u2264 c \u2022 g(n) para 
todo n maior que n0. 
Exemplos: 
 i) se f(n) \u2264 999g(n) para todo n \u2265 100 então f = O(g). (a recíproca não é 
verdadeira) 
 ii) vamos mostrar que n2/2 \u2013 3n = O(n2). 
 queremos provar que, par algum par de constantes positivas c e n0, temos: 
0 \u2264 n2/2 \u2013 3n \u2264 cn2, para todo n \u2265 n0 
 dividindo ambos os lados por n2, procuramos encontrar c e n0 tais que: 
0 \u2264 1/2 \u2013 3/n \u2264 c, para todo n \u2265 n0 
 como a função 1/2 \u2013 3/n nunca é maior que 1/2 e é positiva para n \u2265 7, então 
c = 1/2 e n0 = 7 certificam que n2/2 \u2013 3n = O(n2). 
Obs.: esse não é o único par de constantes que garante a pertinência de 
n2/2 \u2013 3n = O(n2); existem infinitos pares. 
iii) suponha que f(n) = (3/2)n2 + (7/2)n \u2013 4 e que g(n) = n2. 
A tabela a seguir sugere f(n) \u2264 2g(n) para n \u2265 6 e portanto temos f(n) = O(g(n)). 
n f(n) g(n) 
0 -4 0 
1 1 1 
2 9 4 
3 20 9 
4 34 16 
5 51 25 
6 71 36 
7 94 49 
8 120 64 
É fácil verificar que, de fato, f(n) = O(g(n)) com um cálculo grosseiro: 
f(n) \u2264 2n2 + 4n2 = 6n2 = 6g(n) para todo n. 
 
 
 
 16 
 
 
Ordem \u2126\u2126\u2126\u2126 
A expressão &quot;f = O(g)&quot; tem o mesmo sentido que &quot;f < g&quot;. Agora precisamos de um 
conceito como &quot;f > g&quot;. 
Definição 2: 
Dadas funções assintoticamente não-negativas f e g, dizemos que f está na ordem \u2126 
de g, e escrevemos que f = \u2126(g), se f(n) > c \u2022 g(n) > 0 para algum c positivo e para 
todo n suficientemente grande. 
Ou seja, existe um número positivo c e um número n0 tais que f(n) > c · g(n) para 
todo n maior que n0. 
Exemplos: 
 i) se f(n) > g(n)/100000 para todo n > 888 então f = \u2126(g). ( a recíproca não é 
verdadeira!) 
ii) vamos mostrar que n2/2 \u2013 3n = \u2126(n2). 
 queremos provar que, par algum par de constantes positivas c e n0, temos: 
0 < cn2 < n2/2 \u2013 3n , para todo n > n0 
 dividindo ambos os lados por n2, queremos encontrar c e n0 tais que: 
0 < c < 1/2 \u2013 3/n, para todo n > n0 
note que para n < 6 temos 1/2 \u2013 3/n < 0. 
Como c deve ser uma constante positiva teremos n0 > 7. 
Más, 1/2 \u2013 3/n < 0 cresce monotonicamente para n > 7, então 
 c = 1/2 \u2013 3/7 = 1/14 e n0 = 7 certificam que n2/2 \u2013 3n = O(n2). 
 
 
Qual a relação entre O e \u2126 ? 
Não é difícil verificar que: 
f = O ( g ) se e somente se g = \u2126 ( f ). 
 
 
 
 
 
 
 
 17 
 
 
Ordem \u398\u398\u398\u398 
Além dos conceitos com sentido de &quot;f < g&quot; e de &quot;f > g&quot;, precisamos de um que 
seja como &quot;f = g&quot;. 
Definição 3: 
Dizemos que f e g estão na mesma ordem \u398 e escrevemos f = \u398(g) se f = O(g) 
e f = \u2126(g). 
Ou seja, f = \u398(g) significa que c1 g(n) < f(n) < c2 g(n) para algum c1 positivo, algum 
c2 positivo, e para todo n suficientemente grande. 
Exemplos: 
 i) as funções abaixo pertencem todas à ordem \u398(n2): 
n2 , (3/2)n2 , 9999n2 , n2/1000 , n2+100n . 
ii) finalmente, vamos mostrar que n2/2 \u2013 3n = \u398(n2). 
Já mostramos que n2/2 \u2013 3n = O(n2) e que n2/2 \u2013 3n = \u2126(n2) logo 
 n2/2 \u2013 3n = \u398(n2). 
Más, 
quais seriam as constantes positivas c1, c2 e n0 que garantem que n2/2 \u2013 3n = \uf051(n2) ? 
A resposta é simples: 
os valores de c1 e de c2 são, respectivamente, os mesmos que garantiram que a 
função estava em \u2126(n2) e O(n2), ou seja, c1 = 1/14 e c2 = 1/2 o valor de n0 deve 
ser o maior entre os dois valores de n0 utilizados na demonstração de pertinência a 
\u2126(n2) e O(n2), ou seja, n0 = Max{7,7} = 7. 
 
 
 
 
 
 
 
 
 
 
 
 18 
 
 
Classes de comportamento assintótico 
A maioria dos algoritmos possui um parâmetro que afeta o tempo de execução de 
forma mais significativa, usualmente o número de itens a ser processado. Este 
parâmetro pode ser o número de registros de um arquivo a ser ordenado, ou o 
número de nós de um grafo. 
As principais classes de problemas possuem as funções de complexidade, descritas 
em notação \u398, como: 
1. f(n) = \u398(1) estes algoritmos são ditos de complexidade constante. O uso do 
algoritmo independente do tamanho de n. Neste caso as instruções do algoritmo 
são executadas um número fixo de vezes. 
2. f(n) = \u398(lgn) um algoritmo de complexidade \u398 (lgn) é dito ter complexidade 
logarítmica. Este tempo de execução ocorre tipicamente em algoritmos que 
resolvem um problema transformando-o em problemas menores. Nestes casos, o 
tempo de execução pode ser considerado como sendo menor do que uma 
constante grande. Quando n é mil e a base do logaritmo é 2, 10log2 \u2248n , quando n 
é um milhão 20log2 \u2248n . Para dobrar o valor de lgn temos que considerar o 
quadrado de n. A base do logaritmo pouco muda estes valores: compare para n 
igual a um milhão temos 6log10 \u2248n . 
3. f(n) = \u398(n) estes algoritmos tem complexidade linear, em geral um pequeno 
trabalho é realizado sobre cada elemento de entrada. Esta é a melhor situação 
possível para um algoritmo que tem que processar n elementos de entrada ou 
produzir n elementos de saída. Cada vez que n dobra de tamanho o tempo de 
execução dobra. 
4. f(n) = \u398(nlgn) este tempo de execução ocorre tipicamente em algoritmos que 
resolvem um problema quebrando-o em problemas menores, resolvendo cada um 
deles independentemente e depois ajuntando as soluções. Quando n é um milhão 
e a base do logaritmo é 2, nlgn é cerca de 20 milhões. Quando n é dois milhões, 
nlgn é cerca de 42 milhões, pouco mais que o dobro. 
5. f(n) = \u398(n2) um algoritmo com esta complexidade é dito ter complexidade 
quadrática. Os algoritmos dessa ordem ocorrem quando os itens de dados são 
processados aos pares, muitas vezes em um laço dentro do outro. Quando n é mil, 
o número de operações é da ordem de 1 milhão. Sempre que n dobra o tempo de 
execução é multiplicado por 4. Algoritmos deste tipo são úteis para resolver 
problemas de tamanhos relativamente