Aula 2 de Algoritmos avançados

Prévia do material em texto

Algoritmos Avançados – aula 2 
Análise de Algoritmo - Notação O (Parte II) 
Objetivos 
Objetivos - O aluno deverá ser capaz de: 
 
O aluno deverá ser capaz de: 
 
- Conhecer o conceito de Análise de Algoritmo; 
- Conhecer sobre o Elemento da Análise Assintótica - Notação O 
- Conhecer sobre a Notação O. 
- Conhecer sobre a função e operações com a Notação O. 
Algoritmos Avançados – aula 2 
O que é Analise de Algoritmos 
 
A análise de algoritmos estuda a correção e o desempenho de algoritmos. 
 Em outras palavras, a análise de algoritmos procura respostas para 
perguntas do seguinte tipo: 
- Este algoritmo resolve o meu problema? 
- Quanto tempo o algoritmo consome para processar uma 'entrada' de 
 tamanho n? 
Além disso, a análise de algoritmos estuda certos paradigmas (como 
divisão e conquista, programação dinâmica, busca local, aproximação, etc.) 
que se mostraram úteis na criação de algoritmos para vários problemas 
computacionais. 
 
Notação O - Notação Assintótica 
 
Para valores suficientemente pequenos de n, qualquer algoritmo custa 
pouco para ser executado, mesmo os algoritmos ineficientes; 
A análise de algoritmos é realizada para valores grandes de n 
considerando-se o comportamento assintótico das funções de custo; 
3 
Análise de Algoritmo 
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; 
correta obtenção do resultado pretendido; 
robustez (como comporta-se com as entradas inválidas ou não previstas). 
 
Análise de Algoritmos é medição de complexidade de algoritmo 
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. 
 
Algoritmos Avançados – aula 2 
4 
Porque 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. 
Algoritmos Avançados – aula 2 
5 
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. 
 
 
Algoritmos Avançados – aula 2 
6 
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 
 
Algoritmos Avançados – aula 2 
7 
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)=n
2 
A4 
T4(n)=n
3 
A5 
T5(n)=2
n 
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 
Algoritmos Avançados – aula 2 
8 
 
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 
 
Algoritmos Avançados – aula 2 
9 
Exemplo em pseudocódigo 
arrayMax(A, n): 
Entrada: array A com n>=1 elementos inteiros 
Saida: o maior elemento em A 
 
tmpMax <- A[0] 
for i<-1 to n-1 do 
 if tmpMax < A[i] then 
 tmpMax <- A[i] 
return tmpMax 
 
Algoritmos Avançados – aula 2 
10 
Algoritmo em operações primitivas 
tmpMax <- A[0] 2 
 
for i <- 1 to n-1 do 1+n (comparação i<n) 
 Corpo do ciclo 
if tmpMax < A[i] then 4(n-1) ou 6 (n-1), se trocar max 
tmpMax <- A[i] 
return tmpMax 1 
 
 
Total1= 2+1+n+4(n-1)+1= 5n (melhor caso) 
Total2= 2+1+n+6(n-1)+1= 7n -2 (pior caso) 
 
 
Algoritmos Avançados – aula 2 
11 
Simplificamos a análise 
Este nível de detalhe é necessário? 
 
Na analise de algoritmos é importante concentrar-se na taxa de 
crescimento do tempo de execução como uma função do tamanho de 
entrada n, obtendo-se um quadro geral do comportamento. 
 
 Assim para o exemplo basta saber que o tempo de execução de 
algoritmo cresce proporcionalmente a n. 
 
(O tempo real seria n*fator constante, que depende de SW e HW). 
Algoritmos Avançados – aula 2 
2016/8/23 EDA - Prof. Paulemir Campos 12 
Comportamento Assintótico de Funções 
A análise de algoritmos para solucionar um problema de 
tamanho n é realizada para valores grandes de n. 
Para tanto, estuda-se o comportamento assintótico das 
funções de custo ou de complexidade do algoritmo. 
O comportamento assintótico de f(n) representa o limite 
do custo quando n cresce. 
Algoritmos Avançados – aula 2 
2016/8/23 EDA - Prof. Paulemir Campos 13 
Comportamento Assintótico de Funções 
Definição: Uma função f(n) domina 
assintoticamente outra função g(n) se existem duas 
constantes positivas c e m tais que, para n  m, 
temos 
 
 |g(n)|  c.|f(n)| 
Algoritmos Avançados – aula 2 
14 
Notação Assintótica 
Notação O (big O) 
Definição: Considere uma função f(n) não negativa para todos os inteiros 
n≥0. 
 Dizemos que “f(n) é O(g(n))” e escrevemos f(n) = O(g(n)), se existem 
um inteiro n0 e uma constante c>0, tais que para todo o inteiro n≥n0, f(n) 
≤ cg(n) 
 
Caracteriza o comportamento assintótico de uma função, estabelecendo um 
limite superior quanto à taxa de crescimento da função em relação ao 
crescimento de n. 
Permite ignorar fatores constantes e termos de menor ordem, centrando-se 
nos componentes que mais afetam o crescimento de uma função. 
Algoritmos Avançados – aula 2 
15 
Diagrama 
Definição do Grande O 
Algoritmos Avançados – aula 2 
16 
Operações com a Notação O 
Algumas delas são: 
f(n) = O(f(n)) 
c . f(n) = O(f(n)), com c pertencente a Z*+ 
O(f(n)) + O(f(n)) = O(f(n)) 
O(O(f(n))) = O(f(n)) 
O(f(n))+O(g(n)) = O(max(f(n),g(n))) 
O(f(n)).O(g(n)) = O(f(n).g(n)) 
f(n).O(g(n))=O(f(n).g(n)) 
Algoritmos Avançados – aula 2 
17 
Operações com a Notação O 
Exemplo: 
Obtenha a complexidade de tempo em notação O de alguns algoritmos 
dada pelas expressões matemáticas seguintes: 
 
O(n) + O(n2) + O(n . log n), com n>0 
= O(max(O(n),O(n2))) + O(n . log n) 
= O(n2) + O(n . log n) 
= O(max(O(n2),O(n . log n))) 
= O(n2), n>0. 
Algoritmos Avançados – aula 2 
18 
Operações com a Notação O 
Obtenção de 
O(max(O(n2),O(n . 
log n))) 
graficamente. 
f, g 
n > 0 
n 
g(n) = n . log n 
f(n) = n2 
Algoritmos Avançados – aula 2 
19 
Constantes Multiplicativas versus Notação Assintótica 
Por questão de simplificação, na obtençãode uma 
notação assintótica, deve-se desprezar constantes e 
adições. 
Geralmente por isso, a notação assintótica não serve 
para comparar dois algoritmos, mas sim, nos fornece 
uma ideia da complexidade de execução de um em 
relação ao outro. 
Algoritmos Avançados – aula 2 
20 
Exemplo: 
 
Um algoritmo F possui complexidade de tempo f(n) = 
100 . n, isto é, O(n) e um outro algoritmo G é dado por 
g(n) = 2.n2, ou seja, O(n2). Qual desses dois algoritmos 
é melhor para resolver um problema de tamanho n? 
Constantes Multiplicativas versus Notação Assintótica 
Algoritmos Avançados – aula 2 
21 
Resposta: 
 
Depende! Note que para valores menores do que 50 
(n<50), o algoritmo G [O(n2)] é melhor, g(n) = 2.n2 (É 
dominado assintoticamente por f(n) = 100.n). 
 
Por outro lado, para valores maiores ou iguais a 50 (n  
50), o algoritmo F [O(n)] é melhor, f(n) = 100.n (É 
dominado assintoticamente por g(n)= 2.n2). 
Algoritmos Avançados – aula 2 
22 
Classes de Comportamento Assintótico 
As principais classes de problemas possuem as 
seguintes funções de complexidade: 
 
f(n)=O(1): São algoritmos de complexidade constante. 
 
O uso desses algoritmos independem do tamanho de n. 
Neste caso, as instruções do algoritmo são executadas 
um número fixo de vezes. 
Algoritmos Avançados – aula 2 
23 
Classes de Comportamento Assintótico 
f(n)=O(log n): São algoritmos de complexidade 
logarítmica. 
Este tempo de execução ocorre tipicamente em algoritmos 
que resolvem um problema transformando-o em 
problemas menores. 
 
f(n)=O(n): São algoritmos de complexidade linear. 
Em geral, um pequeno trabalho é realizado sobre cada 
elemento de entrada. 
Algoritmos Avançados – aula 2 
24 
Classes de Comportamento Assintótico 
f(n)=O(n .log n): 
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 junta-se as soluções. 
 
f(n)=O(n2): São algoritmos de complexidade quadrática. 
Geralmente isto ocorre quando há processamento com 
um laço dentro do outro. São úteis quando n é 
relativamente pequeno. 
Algoritmos Avançados – aula 2 
25 
Classes de Comportamento Assintótico 
f(n)=O(n3): São algoritmos de complexidade cúbica. 
Úteis apenas para resolver pequenos problemas. 
 
f(n)=O(2n): São algoritmos de complexidade 
exponencial. 
Tais algoritmos geralmente não são úteis para resolver 
problemas do ponto de vista prático. Ocorrem em 
problemas quando se usa “força bruta” para resolvê-los. 
Algoritmos Avançados – aula 2 
26 
Comparação entre Funções de Complexidade 
Segundo Garey e Johnson (1979, pág. 7), temos: 
OBS.: Um algoritmo linear executa em 1s um milhão de operações. 
Algoritmos Avançados – aula 2 
27 
Notação Assintótica 
Terminologia de classes mais comuns de funções: 
 
Logarítmica - O(log n) 
Linear - O(n) 
Quadrática - O(n2) 
Polinomial – O(nk), com k≥1 
Exponencial – O(an), com a>1 
 
 
Algoritmos Avançados – aula 2 
28 
Ordens mais comuns 
log n 
n 
n2 
2n 
n 
f 
n log n 
1 
(linear) 
(quadrática) 
(exponencial) 
(logarítmica) 
(constante) 
Algoritmos Avançados – aula 2 
29 
Técnicas de Análise de Algoritmos 
Determinar a ordem de tempo de execução de um 
algoritmo (notação O) é em geral mais simples do 
que encontrar a expressão matemática exata da 
função de complexidade. 
Algoritmos Avançados – aula 2 
30 
Técnicas de Análise de Algoritmos 
Tentando tornar mais simples a tarefa de obter tal 
expressão matemática, Aho, Hopcroft e Ullman 
(1983) enumeraram alguns princípios a serem 
seguidos: 
1. Operação de atribuição, leitura ou escrita são 
consideradas como O(1). 
 Exceções: Chamada de função em comando de 
atribuição e atribuições que envolvem vetores de 
tamanho arbitrariamente grandes. 
Algoritmos Avançados – aula 2 
31 
Técnicas de Análise de Algoritmos 
2. O tempo de execução de uma sequência de 
comandos é determinado pelo maior tempo de 
execução de qualquer comando dessa sequência 
(operação dominante). 
3. O tempo de execução de um comando de 
decisão é composto pelo tempo de execução dos 
comandos executados dentro do comando 
condicional mais o tempo para avaliar a condição, 
que é O(1). 
Algoritmos Avançados – aula 2 
32 
Técnicas de Análise de Algoritmos 
4. O tempo para executar um laço é a soma do tempo de 
execução do corpo do laço mais o tempo de avaliar a 
condição de parada (geralmente é O(1)), multiplicado pelo 
número de iterações do laço. 
5. Quando o algoritmo possui procedimentos não recursivos, 
o tempo de execução de cada procedimento deve ser 
computado separadamente um a um, iniciando com os 
procedimentos que não chamam outros procedimentos. 
Algoritmos Avançados – aula 2 
2016/8/23 EDA - Prof. Paulemir Campos 33 
Técnicas de Análise de Algoritmos 
5. (Continuação) Depois, avalia-se os procedimentos 
que chamam os procedimentos que não chamam 
outros procedimentos, utilizando os tempos dos 
procedimentos já avaliados. Este processo é repetido 
até chegar no algoritmo principal. 
Algoritmos Avançados – aula 2 
34 
Técnicas de Análise de Algoritmos 
6. Quando o algoritmo possui procedimentos 
recursivos, para cada procedimento é associada uma 
função de complexidade f(n) desconhecida, onde n 
mede o tamanho dos argumentos para o 
procedimento. Outra opção é determinar o número 
total de chamadas recursivas, calcular a 
complexidade de uma dessas chamadas recursivas 
(sem considerar outras chamadas), e efetuar esse 
produto. 
Algoritmos Avançados – aula 2 
35 
Técnicas de Análise de Algoritmos 
Exemplo: Obtenha a função de complexidade de 
tempo e também em notação O do algoritmo 
abaixo: 
 
inteiro Fatorial(inteiro i){ // i  0 
 se i=<1 então retorne (1) 
 senão retorne (i * Fatorial(i-1)) 
} 
 
Algoritmos Avançados – aula 2 
36 
Técnicas de Análise de Algoritmos 
Resposta: 
a) Obtenção da função de complexidade de tempo. 
- Esse procedimento recursivo é chamado n vezes; 
- A complexidade de uma chamada é constante, 
isto é, O(1). Pois, para n  1, apenas uma 
atribuição é executada; e para n > 1 apenas um 
produto é efetuado. 
 
Algoritmos Avançados – aula 2 
37 
Técnicas de Análise de Algoritmos 
Resposta: 
a) (Continuação) 
- Logo, temos um produto de n por 1. Assim, 
f(n)=n é a função de complexidade de tempo 
desse algoritmo recursivo. 
b) Como f(n) = n é a função de complexidade de 
tempo desse algoritmo, então, trata-se de um 
algoritmo polinomial de ordem O(n). 
Algoritmos Avançados – aula 2