Buscar

Análise de Algoritmos

Prévia do material em texto

25/03/2012
1
Prof. Debora Medeiros
UTFPR – Universidade Tecnológica Federal do Paraná
*Slides baseados no material do Prof. Thiago A. S. Pardo (USP)
� Algoritmo está pronto/disponível
� É importante determinar os recursos necessários
▪ Tempo
▪ Memória
� Qual o principal quesito? Por que?
2
� Um algoritmo que soluciona um determinado problema
� mas requer o processamento de um ano, não deve ser usado
� O que dizer de uma afirmação como a abaixo?
� “Desenvolvi um novo algoritmo chamado TripleX que leva 14,2 
segundos para processar 1.000 números, enquanto o método 
SimpleX leva 42,1 segundos”
▪ Você trocaria o SimpleX que roda em sua empresa pelo TripleX?
3
� A afirmação tem que ser examinada, pois há diversos fatores
envolvidos
� Características da máquina em que o algoritmo foi testado
▪ Quantidade de memória
� Linguagem de programação
� Implementação pouco cuidadosa do algoritmo SimpleX vs. “super” 
implementação do algoritmo TripleX
� Quantidade de dados processados
▪ Se o TripleX é mais rápido para processar 1.000 números, ele também é 
mais rápido para processar quantidades maiores de números, certo?
4
� Comparar algoritmos de forma independente de
� Hardware
� Linguagem de programação
� Habilidade do programador
� Comparar algoritmos e não programas
� Área conhecida como “análise/complexidade de algoritmos”
5
� Sabe-se que
� Processar 10.000 números leva mais tempo do que 1000 
números
� Cadastrar 10 pessoas em um sistema leva mais tempo do que 
cadastrar 5
� Etc.
� Estimar a eficiência de um algoritmo em função do 
tamanho do problema
� Assume-se que “n” é o tamanho do problema, ou número de 
elementos que serão processados
� E calcula-se o número de operações que serão realizadas sobre 
os n elementos
6
25/03/2012
2
� O melhor algoritmo é aquele que requer menos 
operações sobre a entrada, pois é o mais rápido
� O tempo de execução do algoritmo pode variar em diferentes 
máquinas, 
� mas o número de operações é uma boa medida de desempenho 
de um algoritmo
� De que operações estamos falando?
� Toda operação leva o mesmo tempo?
7
� TripleX
� entrada de tamanho n
▪ n2+n operações
� Pensando em termos de função: f(n)=n2+n
� SimpleX
� entrada de tamanho n
▪ 1.000n operações
� g(n)=1.000n
8
� Faça os cálculos do desempenho de cada algoritmo para 
cada tamanho de entrada
9
Tamanho da 
entrada (n)
1 10 100 1.000 10.000
f(n)=n2+n
g(n)=1.000n
� Faça os cálculos do desempenho de cada algoritmo para 
cada tamanho de entrada
� A partir de n=1.000, f(n) mantém-se maior e cada vez 
mais distante de g(n)
� Diz-se que f(n) cresce mais rápido do que g(n)
10
Tamanho da 
entrada (n)
1 10 100 1.000 10.000
f(n)=n2+n 2 110 10.100 1.001.000 100.010.000
g(n)=1.000n 1.000 10.000 100.000 1.000.000 10.000.000
� Deve-se preocupar com a eficiência de algoritmos 
quando o tamanho de n for grande
� comparar 2 algoritmos
� determinar as taxas de crescimento de cada um
� o algoritmo com menor taxa de crescimento rodará mais rápido
quando o tamanho do problema for grande
11
� Notações que usaremos na análise de algoritmos
� T(n) = O(f(n)) (lê-se big-oh, big-o ou “da ordem de”) se existirem 
constantes c e n0 tal que T(n) ≤ c * f(n) quando n ≥ n0
▪ A taxa de crescimento de T(n) é menor ou igual à taxa de 
f(n)
12
25/03/2012
3
� Permite comparar a taxa de crescimento das 
funções correspondentes aos algoritmos
� Não faz sentido comparar pontos isolados das 
funções, já que podem não corresponder ao 
comportamento assintótico
13
� Para 2 algoritmos quaisquer, considere as funções de 
eficiência correspondentes 1.000n e n2
� A primeira é maior do que a segunda para valores pequenos de n
� A segunda cresce mais rapidamente e eventualmente será uma função 
maior, sendo que o ponto de mudança é n=1.000
� Existe uma constante c e um ponto n0 a partir do qual T(n) é menor ou 
igual a c*f(n)
▪ No nosso caso, T(n)=1.000n, f(n)=n2, c=1 e n0=1.000(ou, ainda, c=100 e 
n0=10)
▪ Dizemos que 1.000n=O(n2)
14
� As mais comuns
15
Função Nome
c constante
log n logarítmica
log2n log quadrado
n linear
n log n
n2
quadrática
n3 cúbica
2n
an
exponencial
16
n
tempo
� Apesar de às vezes ser importante, não se costuma 
incluir constantes ou termos de menor ordem em taxas 
de crescimento
� Queremos medir a taxa de crescimento da função
▪ torna os “termos menores” irrelevantes
� As constantes também dependem do tempo exato de cada 
operação
▪ como ignoramos os custos reais das operações, ignoramos também as 
constantes
� Não se diz que T(n) = O(2n2) ou que
T(n) = O(n2+n)
� Diz-se apenas T(n) = O(n2)
17
� Instruções simples
� soma, multiplicação, comparação, atribuição, etc.
� Por simplicidade e viabilidade da análise, assume-se que
� cada instrução demora exatamente uma unidade de 
tempo para ser executada
� Obviamente, em situações reais, isso pode não ser 
verdade: 
▪ a leitura de um dado em disco pode demorar mais do que uma 
soma
� Operações complexas, como inversão de matrizes e ordenação 
de valores, não são realizadas em uma única unidade de tempo, 
obviamente: devem ser analisadas em partes
18
25/03/2012
4
� Considera-se somente o algoritmo e suas entradas (de 
tamanho n)
� Para uma entrada de tamanho n, pode-se calcular 
Tmelhor(n), Tmédia(n) e Tpior(n), ou seja, o melhor tempo de 
execução, o tempo médio e o pior, respectivamente
� Obviamente, Tmelhor(n) ≤ Tmédia(n) ≤ Tpior(n)
� Atenção: para mais de uma entrada, essas funções 
teriam mais de um argumento
19
� Geralmente, utiliza-se somente a análise do pior caso Tpior(n), pois ela 
fornece os limites para todas as entradas, incluindo particularmente 
as entradas ruins
� Logicamente, muitas vezes, o tempo médio pode ser útil, 
principalmente em sistemas executados rotineiramente
▪ Por exemplo: em um sistema de cadastro de alunos como usuários de uma 
biblioteca, o trabalho difícil de cadastrar uma quantidade enorme de 
pessoas é feito somente uma vez; depois, cadastros são feitos de vez em 
quando apenas
� Dá mais trabalho calcular o tempo médio
� O melhor tempo não tem muita utilidade
20
� Supondo que as operações simples demoram uma 
unidade de tempo para executar, considere o programa 
abaixo para calcular o resultado de
Início
declare soma_parcial numérico;
soma_parcial � 0;
para i�1 até n faça
soma_parcial�soma_parcial+i*i*i;
escreva(soma_parcial);
Fim
21
� Supondo que as operações simples demoram uma 
unidade de tempo para executar, considere o programa 
abaixo para calcular o resultado de
Início
declare soma_parcial numérico;
soma_parcial � 0;
para i�1 até n faça
soma_parcial�soma_parcial+i*i*i;
escreva(soma_parcial);
Fim
22
1 unidade de tempo
4 unidades (1 da soma, 2 
das multiplicações e 1 da 
atribuição) executada n 
vezes (pelo comando 
“para”) = 4n unidades
1 unidade para inicialização de i, 
n+1 unidades para testar se i≤n e n 
unidades para incrementar i = 2n+2
1 unidade para escrita
� Supondo que as operações simples demoram uma 
unidade de tempo para executar, considere o programa 
abaixo para calcular o resultado de
Início
declare soma_parcial numérico;
soma_parcial � 0;
para i�1 até n faça
soma_parcial�soma_parcial+i*i*i;
escreva(soma_parcial);
Fim
23
1 unidade de tempo
4 unidades (1 da soma, 2 
das multiplicações e 1 da 
atribuição) executada n 
vezes (pelo comando 
“para”) = 4n unidades
1 unidade para inicialização de i, 
n+1 unidades para testar se i≤n e n 
unidades para incrementar i = 2n+2
1 unidade para escrita
Custo total: somando 
tudo, tem-se 6n+4 
unidades de tempo, ou 
seja, a função é O(n)
� Ter que realizar todos esses passos paracada algoritmo 
(principalmente algoritmos grandes) pode se tornar 
uma tarefa cansativa
� Em geral, como se dá a resposta em termos do big-oh, 
costuma-se desconsiderar as constantes e elementos 
menores dos cálculos
� No exemplo anterior
▪ A linha soma_parcial�0 é insignificante em termos de tempo
▪ É desnecessário ficar contando 2, 3 ou 4 unidades de tempo na 
linha soma_parcial�soma_parcial+i*i*i
▪ O que realmente dá a grandeza de tempo desejada é a repetição 
na linha para i����1 até n faça
24
25/03/2012
5
� Repetições
� O tempo de execução de uma repetição é pelo 
menos o tempo dos comandos dentro da 
repetição (incluindo testes) vezes o número de 
vezes que é executada
25
� Repetições aninhadas
� A análise é feita de dentro para fora
� O tempo total de comandos dentro de um grupo de repetições 
aninhadas é o tempo de execução dos comandos multiplicado 
pelo produto do tamanho de todas as repetições
� O exemplo abaixo é O(n2)
para i�0 até n faça
para j�0 até n faça
faça k�k+1;
26
� Comandos consecutivos
� É a soma dos tempos de cada um, o que pode significar o 
máximo entre eles
� O exemplo abaixo é O(n2), apesar da primeira repetição ser O(n)
para i�0 até n faça
k�0;
para i�0 até n faça
para j�0 até n faça
faça k�k+1;
27
� Se... então... senão
� Para uma cláusula condicional, o tempo de execução nunca é 
maior do que o tempo do teste mais o tempo do maior entre os 
comandos relativos ao então e os comandos relativos ao senão
� O exemplo abaixo é O(n)
se i<j
então i�i+1
senão 
para k�1 até n faça
i�i*k;
28
29
MAX(A)
max � A[1]
for i � 2 to n //n=|A|
if max < A[i]
max � A[i]
return max
MAX(A)
max � A[1]
for i � 2 to n //n=|A|
if max < A[i]
max � A[i]
return max
� n-1 comparações
30
25/03/2012
6
MAX(A)
max � A[1]
for i � 2 to n //n=|A|
if max < A[i]
max � A[i]
return max
� n-1 comparações
� O(n)
31
BUSCA_SEQ(A,val)
for i � 1 to n //n=|A|
if A[i] = val
return i
return FALSE
32
BUSCA_SEQ(A,val)
for i � 1 to n //n=|A|
if A[i] = val
return i
return FALSE
� Pior caso :
33
BUSCA_SEQ(A,val)
for i � 1 to n //n=|A|
if A[i] = val
return i
return FALSE
� Pior caso :
� n comparações: O(n)
34
BUSCA_SEQ(A,val)
for i � 1 to n //n=|A|
if A[i] = val
return i
return FALSE
� Pior caso :
� n comparações: O(n)
� Melhor caso:
35
BUSCA_SEQ(A,val)
for i � 1 to n //n=|A|
if A[i] = val
return i
return FALSE
� Pior caso :
� n comparações: O(n)
� Melhor caso:
� 1 comparação: O(1)
36
25/03/2012
7
BUSCA_SEQ(A,val)
for i � 1 to n //n=|A|
if A[i] = val
return i
return FALSE
� Pior caso :
� n comparações: O(n)
� Melhor caso:
� 1 comparação: O(1)
� Caso médio:
37
BUSCA_SEQ(A,val)
for i � 1 to n //n=|A|
if A[i] = val
return i
return FALSE
� Pior caso :
� n comparações: O(n)
� Melhor caso:
� 1 comparação: O(1)
� Caso médio:
� 1p1 + 2p2 + … + npn
38
BUSCA_SEQ(A,val)
for i � 1 to n //n=|A|
if A[i] = val
return i
return FALSE
� Pior caso :
� n comparações: O(n)
� Melhor caso:
� 1 comparação: O(1)
� Caso médio:
� 1p1 + 2p2 + … + npn
� Assumir pi = 1/n
39
BUSCA_SEQ(A,val)
for i � 1 to n //n=|A|
if A[i] = val
return i
return FALSE
� Pior caso :
� n comparações: O(n)
� Melhor caso:
� 1 comparação: O(1)
� Caso médio:
� 1p1 + 2p2 + … + npn
� Assumir pi = 1/n
� 1/n(1 + 2 + … + n) //PA
40
BUSCA_SEQ(A,val)
for i � 1 to n //n=|A|
if A[i] = val
return i
return FALSE
� Pior caso :
� n comparações: O(n)
� Melhor caso:
� 1 comparação: O(1)
� Caso médio:
� 1p1 + 2p2 + … + npn
� Assumir pi = 1/n
� 1/n(1 + 2 + … + n) //PA
=(1+n)n/2n
= (n+1)/2
41
BUSCA_SEQ(A,val)
for i � 1 to n //n=|A|
if A[i] = val
return i
return FALSE
� Pior caso :
� n comparações: O(n)
� Melhor caso:
� 1 comparação: O(1)
� Caso médio:
� 1p1 + 2p2 + … + npn
� Assumir pi = 1/n
� 1/n(1 + 2 + … + n) //PA
=(1+n)n/2n
= (n+1)/2
� O(n)
42
25/03/2012
8
� Chamadas a sub-rotinas
� Uma sub-rotina deve ser analisada primeiro e 
depois ter suas unidades de tempo incorporadas 
ao programa/sub-rotina que a chamou
43
� Sub-rotinas recursivas
� Se a recursão é um “disfarce” da repetição (e, portanto, a recursão está 
mal empregada, em geral), basta analisá-la como tal
� O exemplo é obviamente O(n)
44
sub-rotina fatorial(n: numérico)
início
declare aux numérico;
se n≤1
então aux�1
senão aux�n*fatorial(n-1); 
retorne aux;
fim
Eliminando
a recursão
sub-rotina fatorial(n: numérico)
início
declare aux numérico;
aux�1;
enquanto n>1 faça
aux�aux*n;
n�n-1;
retorne aux;
fim
� Sub-rotinas recursivas
� Em muitos casos 
▪ (incluindo casos em que a recursividade é bem empregada)
▪ é difícil transformá-la em repetição
▪ Solução: análise de recorrência
▪ Recorrência: equação ou desigualdade que descreve uma função em 
termos de seu valor em entradas menores
▪ Caso típico: algoritmos de dividir-e-conquistar
▪ desmembram o problema em vários subproblemas
� semelhantes ao problema original, mas menores em tamanho,
▪ resolvem os subproblemas recursivamente
▪ combinam essas soluções criando uma solução para o problema original
▪ Exemplos?
45
� Exemplo: potência de um número
Início
declare ac, a, i e n numéricos;
ler a e n;
ac�1;
i�0;
enquanto i<n faça
ac�ac*a;
i�i+1;
Fim
46
sub-rotina potencia(a: numérico, n: numérico)
início
declare aux numérico;
se n=1 retorne (a)
se n é par
aux�potencia(a,n/2)
retorne(aux*aux)
senão
aux�potencia(a,(n-1)/2);
retorne (aux*aux*a)
fim
� Alguns métodos para resolver recorrências
� Método da substituição
� Método da árvore de recursão
� Método mestre
47
� Alguns métodos para resolver recorrências
� Método da substituição
� Método da árvore de recursão
� Método mestre
48
25/03/2012
9
� Método da árvore de recursão
� Esboça-se uma árvore que, nível a nível, representa as recursões 
sendo chamadas
� Em seguida, em cada nível/nó da árvore, são acumulados os 
tempos necessários para o processamento
▪ No final, tem-se a estimativa de tempo do problema
49
� T(n)=aT(n/b)+f(n)
▪ a: número de subproblemas
▪ n/b: tamanho do subproblema
▪ f(n): trabalho independente da recursão
50
▪ a: 1 (subproblema)
▪ b: n/2 (tamanho do subproblema)
▪ T(n) = 1T(n/2) + O(1)
51
� Árvore de recursão
▪ T(n) = 1T(n/2) + c
52
T(n)
� Árvore de recursão
▪ T(n) = 1T(n/2) + c
53
c
T(n/2)
� Árvore de recursão
▪ T(n) = 1T(n/2) + c
54
c
c
T(n/4)
25/03/2012
10
� Árvore de recursão
▪ T(n) = 1T(n/2) + c
55
c
c
c
O(1)
� Árvore de recursão
▪ T(n) = 1T(n/2) + c
56
c
c
c
h=lg n
O(1)
� Árvore de recursão
▪ T(n) = 1T(n/2) + c
57
c
c
c
h=lg n
Total = O(lgn)
O(1)
� A análise assintótica é uma ferramenta fundamental ao projeto, 
análise ou escolha de um algoritmo específico para uma dada 
aplicação
� No entanto, deve-se ter sempre em mente que essa análise 
“esconde” fatores assintoticamente irrelevantes, mas que em alguns 
casos podem ser relevantes na prática, particularmente se o 
problema de interesse se limitar a entradas (relativamente) pequenas
� Por exemplo, um algoritmo com tempo de execução da ordem de 10100n é 
O(n), assintoticamente melhor do que outro com tempo 10 n log n, o que 
nos faria, em princípio, preferir o primeiro
� No entanto, 10100 é o número estimado por alguns astrônomos como um 
limite superior para a quantidade de átomos existente no universo 
observável!
58
59
� Estime quantas unidades de tempo são necessárias para rodar o 
algoritmo abaixo
Início
declare i e j numéricos;
declare Avetor numérico de n posições;
i�1;
enquanto i≤n faça
A[i]�0;
i�i+1;
para i�1 até n faça
para j�1 até n faça
A[i]�A[i]+i+j;
Fim

Outros materiais

Materiais relacionados

Perguntas relacionadas

Materiais recentes

26 pág.

Perguntas Recentes