Projeto e Análise de Algoritmos

Prévia do material em texto

PPGI/200
9
Prof. Lucídio Cabral - Estrutura de Dados e Complexidade de Algoritmo
s
1
Crescimento de Funções
Análise de AlgoritmosAnálise de Algoritmos
– tempo de processamento em função dos dados de 
entrada;
– espaço de memória total requerido para os dados; 
– comprimento total do código;
– correcta obtenção do resultado pretendido;
– robustez (como comporta-se com as entradas 
inválidas ou não previstas).
– quantidade de "trabalho" necessária para a sua 
execução, expressa em função das operações 
fundamentais, as quais variam de acordo com o 
algoritmo, e em função do volume de dados.
Complexidade
• Porquê o estudo da Complexidade?
– Performance 
• Escolher entre vários algoritmos o mais eficiente 
para implementar;
• Desenvolver novos algoritmos para problemas que 
já têm solução; 
• Desenvolver algoritmos mais eficientes (melhorar os 
algoritmos), devido ao aumento constante do 
"tamanho" dos problemas a serem resolvidos.
– Complexidade Computacional - torna possível 
determinar se a implementação de determinado 
algoritmo é viável.
Complexidade
• Tipos de Complexidade
– Espacial 
• Este tipo de complexidade representa, por exemplo, o 
espaço de memória usado para executar o algoritmo. 
– Temporal 
• Este tipo de complexidade é o mais usado podendo 
dividir-se em dois grupos: 
– Tempo (real) necessário à execução do algoritmo.
(como podemos medir?)
– Número de instruções necessárias à execução.
• Medidas de Análise 
– Devem ser independentes da tecnologia 
(hardware/software)
– Modelos Matemáticos simplificados baseados nos fatores 
relevantes:
• Tempo de Execução 
Uma função que relaciona o tempo de execução com o 
tamanho de entrada: 
t = F(n)
– Conjunto de operações a serem executadas.
– Custo associado à execução de cada operação.
• Ocupação de Espaço em Memória
Analise de Algoritmos
Complexidade
• Exemplo 
– Sejam 5 algoritmos A1 a A5   para resolver um mesmo 
problema, de complexidades diferentes. (Supomos que 
uma operação leva 1 ms para ser efetuada.)  
– Tk(n) é a complexidade ou seja o número de operações 
que o algoritmo efetua para n entradas
n A1 
T1(n)= n
A2 
T2(n)=nlog n
A3 
T3(n)=n2
A4 
T4(n)=n3
A5 
T5(n)=2n
16 0.016s 0.064s 0.256s 4s 1m4s
32 0.032s 0.16s 1s 33s 46 Dias
512 0.512s 9s 4m22s 1 Dia 13h 10137 Séculos
 
tempo necessário para o algoritmo em função de n entradas
Operações primitivas
• Atribuição de valores a variáveis
• Chamadas de métodos
• Operações aritméticas
• Comparação de dois números
• Acesso a elemento de um array
• Seguir uma referência de objeto (acesso a 
objeto)
• Retorno de um método
Complexidade de 
Algoritmos
• Complexidade de pior caso – big-Oh g(n)
• Complexidade de melhor caso – big-Omega g(n)
– de uso bem menos freqüente
– em algumas situações específicas
• Complexidade de caso médio – big-Theta g(n)
– menos utilizada apesar de importante
– difícil conhecer a distribuição de probabilidades das diferentes 
entradas
Notações assintóticas
 Limite assintótico apertado ou exato
 Limite assintótico superior
 Limite assintótico inferior
  Limite superior que não é 
 assintoticamente apertado
 Limite inferior que não é 
 assintoticamente apertado
 
Por que as notações assintóticas são importantes?
• Elas fornecem uma caracterização simples da eficiência de um 
algoritmo.
• Elas permitem a comparaçãode desempenho entre vários algoritmos.
• Para valores elevados de componentes/entradas, as constantes 
multiplicativas e termos de baixa ordem de um tempo de execução 
exato são dominados pelo efeito do tamanho de entrada (o número 
de componentes).
– O tempo de execução de uma algoritmo sobre uma entrada particular, é o número de operações 
primitivas ou “passos” executados.
– O tamanho da entrada depende problema sendo estudado. Mas na maioria dos casos este é o 
número de itens na entrada, por exemplo: o número total de bits.
 
 Resumindo, em geral, quando observamos tamanhos de entrada 
suficientemente grandes para tornar a ordem de crescimento do 
tempo de execução relevante para um algoritmo, nós estamos 
estudando a eficiência assintótica de um algoritmo.
 E um algoritmo que é assintoticamente mais eficiente será 
efetivamente a melhor escolha. Isto pode não ser verdade para 
todas as entradas consideradas pequenas!
Limite assintótico 
apertado ou exato
OBS:
Limite assintótico 
apertado ou exato
Eg.
Limite assintótico apertado 
ou exato
Eg.
Limite assintótico superior
Limite assintótico superior
Qual melhor algoritmo?
• Sejam A e B dois algoritmos que o 
resolvem o problema P, cujos tempos de 
execução são 
TA(n) e TB(n) 
• comportamento assintótico – tamanho da 
entrada arbitrariamente grande
– caracterizado pela notação O (big O)
Diagrama
Definição do Big-Oh
Ordens mais comuns
Fonte: Sahni, "Data Structures, Algorithms and Applications in C++"
log n
n
n2
2n
n
f
n log n
1
(linear)
(quadrática)
(exponencial)
(logarítmica)
(constante)
Alguns conceitos
• T (n) = O (1) : constante 
• T (n) = O (log log n) : super-rápido
• T (n) = O (log n) : logarítmico – muito bom 
• T (n) = O (n) : linear – toda a entrada é visitada
• T (n) = O (n log n) : limite de muitos problemas
• T (n) = O (n2) : quadrático 
• T (n) = O (nk) : polinomial no tamanho da entrada
• T (n) = O (kn), O (n!), O (nn) : exponencial – ruim! 
Teoremas
1. Comportamento assintótico da soma de duas 
funções cujos comportamentos assintóticos 
particulares são conhecidos:
 Se f1(n) = O(g1(n)) e f2(n) = O(g2(n)), então:
 f1(n) + f2(n) = O(max(g1(n)) , g2(n)))
2. O(k f(n)) = O(f(n))
3. O(f(n)) O(g(n)) = O(f(n) g(n))
Eficiência de um Algoritmo, mais um 
exemplo
Três algoritmo para calcular 
1 + 2 + … n para um n > 0
Eficiência de um Algoritmo
Número de operações necessárias
 O(n) O(n2) O(1)
A notação 
f(n) = 8n + 128  é O (n2)?
f(n)  c.n2 ?
• Seja c =1
8n + 128  n2, então
0  n2 – 8n – 128
0  (n – 16)(n+8)  n0 = 16
 c =1, no = 16, f (n)  c.n2 para todo n  n0 
A notação 
• A função atua como um limite superior 
assintótico da função f
– f = n2 -1  f = (n2)
– f = n2 -1  f = (n3) 
– f = 403  f = (1)
– f = 5+2logn +3log2n  f = 
(log2n)
– f = 5+2 log n +3log2n  f = (n)
– f = 5.2n +5n10  f = (2n)
Limite assintótico inferior
Limite superior que não é 
 assintoticamente apertado 
Limite inferior que não é 
 assintoticamente apertado 
Notações assintóticas em equações 
Relações de Funções Assintóticas
Limites podem ser usados para 
determinar a ordem de complexidade
 c então f (n) =  ( g (n)) se c > 0
se lim f (n) / g (n) = 0 or c > 0 então f (n) =  ( g(n)) 
 or c > 0então f (n) =  ( g (n))n 
Exemplo usando limites



 22
3
2
3
23
3lim5lim35lim
,que dado )(35
n
n
n
n
n
nn
nnn
nnn
Regra de L’Hopital
Se f(x) e g(x) são ambas funções diferenciáveis 
com derivadas f’(x) e g’(x), respectivamente, e 
se 
existe direita a limite o que sempre
)('
)('lim
)(
)(lim
então )(lim)(lim
xg
xf
xg
xf
xfxg
xx
xx




Exemplos usando limites
0
1
/1lim
)'(
)'(loglim
HopitalL' de Regra a Use?loglimloglim
,que dado )(log
 103lim10lim310lim
,que dado )(310
2
2
33
3
3
3
33









n
n
n
n
n
n
nn
nOnn
n
n
n
n
n
nn
nnnn
e
n
e
n
e
n
e
nnn
Exemplo usando limites
lg ( )
lg ln
ln
lg )' ln
ln
lim lg lim (lg )'
'
lim
ln
n O n
n n n n
n
n
n
n nn n n

 



  
     
2 2
1
2
0
 ( '= 1
nln2
 
Exemplo usando limites
n O
e
e e
n kn
k k n k
k
n n
n n n n
n
k
n n
k
n
n
k
n n n k


 
 


  
   

 

 
)' ( ln
lim lim
ln
lim ( )
ln
... lim !
ln
ln
ln ln
n( )2
2
2 2 2
2 2 2
1
2 2 2 2
0
2
2 2
1
2
2
 
onde k é uma constante inteira positiva
 
( )'= ln2 
	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 21
	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