Análise de Algoritmos e Notação O()

Prévia do material em texto

Roteiro da Aula 14 
 
Agenda 
 
• Análise de algoritmos 
• Notação O( ) 
• Uma introdução aos algoritmos de ordenação 
 
 
 
Análise de algoritmos 
Problemas frequentemente podem ser resolvidos de várias formas diferentes: 
• De frente para trás, de trás para frente, por iteração ou recursão, Lists ou Dicionários, resposta 
precisa vs. estimativa, etc. 
• Exemplos: algoritmos de ordenação, busca, contagem, etc. 
 
 
Como avaliar/comparar alternativas? 
• Frequentemente estamos interessados no desempenho em tempo de execução. 
� Tempo gasto e quantidade de memória necessária 
• Também devem ser levados em conta a facilidade de desenvolvimento, testes e manutenção. 
• A natureza dos dados de entrada tem influência sobre o desempenho do algoritmo? (Os dados já 
estão ordenados? Em ordem crescente? Em ordem decrescente?) 
• Esteja certo de que a esforço necessário para implementar algoritmos complexos vale a pena. 
 
 
Brainstorm: Quais algoritmos poderiam ser usados para contar o número de pessoas nessa sala? 
• Contar um a um; Esse método não é muito apropriado para contar um grande número de pessoas, 
digamos o número de manifestantes presentes em uma passeata ou torcedores em um estádio. 
• Recursão: Várias pessoas contando em paralelo; 
• E se eu estiver disposto a aceitar alguma imprecisão na medida? Contar em uma pequena área e 
extrapolar para o restante. 
• “Todos pensem em um número entre 1 e 10! Quantos pensaram no número quatro?” 
Se a probabilidade de alguém escolher um número é uniforme, o número total de pessoas é a 
probabilidade do quatro multiplicada por dez. 
 
 
 
Avaliando o desempenho 
Empiricamente – medindo tempos com um cronômetro 
• Resultados reais, medidos na prática 
• É necessário escrever o código e testá-lo antes de poder medi-lo. 
• Sujeito a variações (hardware, sistema operacional, atividade concorrente, etc.) 
 
 
Matematicamente – analisando o algoritmo 
• É possível analisar um algoritmo sem implementá-lo. 
• Ambiente de execução abstrato, não vinculado a um hardware ou sistema operacional específico. 
• Os resultados empíricos podem não corresponder àqueles previstos (especialmente para conjuntos de 
entrada pequenos) 
 
 
 
Contagem de operações 
def CemF(tempC): 
 return tempC*9.0/5.0 + 32 
 
 
Se cada operação custar R$ 0,01 
• Multiplicação, divisão, soma e return. 
• Total = R$ 0,04 
• O valor de entrada tem influência sobre o custo do algoritmo? Não, qualquer temperatura leva o 
mesmo tempo para ser convertida. 
 
 
 
Mais contagens de operações 
def media(v): 
 soma = 0 
 for i in range(len(v)): 
 soma += v[i] 
 return float(soma)/len(v) 
 
 
Contagem de operações 
• Fora do laço: 8 operações (inicialização da referência v, inicialização da soma, inicialização de i, 
cast, 2*determinação do tamanho do List, divisão e return) 
• Dentro do laço: 3 operações (teste da condição, soma, incremento de i) 
• Total = 3n + 8 
 
 
Como os dados de entrada influenciam o desempenho do algoritmo? 
• Dobre o tamanho do vetor – como varia o tempo necessário para processar o algoritmo? 
 
 
 
Mais contagens de operações 
def obtemExtremos(v): 
 min = max = v[0] 
 for i in range(1, len(v)): 
 if v[i] > max: max = v[i] 
 
 for i in range(1, len(v)): 
 if v[i] < min: min = v[i] 
 
 return min, max 
 
 
• Dentro do laço: teste da variável de controle, comparação, atribuição, incremento da variável de 
controle → 4 por iteração * N iterações 
• 2 laços 
• Fora do laço: inicialização da variável de controle (duas vezes), inicialização de min e max 
• 4 + 8n 
 
 
 
Comparando algoritmos 
Contagem de operações 
• CemF (4) 
• media (3n + 8) 
• obtemExtremos (8n + 4) 
• obtemExtremos sempre levará mais tempo do que media? Talvez. Mas isso não é garantido, e não 
estamos interessados em comparar dois algoritmos usando essa técnica. Nosso interesse é enquadrar 
o algoritmo em uma categoria. Como o tempo de processamento varia em função do crescimento do 
número de dados? 
 
 
Considere o padrão de crescimento 
• Se media leva 2ms para processar 1000 elementos, qual é a estimativa de tempo para 2000 ou 10000 
elementos? 
• E se aplicarmos o mesmo raciocínio a obtemExtremos, qual é a estimativa de tempo? 
 
 
 
A notação O() 
Estimativa do custo de processamento 
• Usa somente o maior termo, ignora os demais, despreza todos os coeficientes. 
• Tempo = 3n + 6 → O(n) 
• Tempo = 10n – 2 → O(n) 
• Tempo = nn −2
2
1
 → O(n2) 
• Tempo = 2n + n3 → O(2n) 
 
 
 
Descreve o crescimento da curva de tempo de processamento do algoritmo 
• Intuição: evite os detalhes quando eles não interessam, e eles não interessam quando o tamanho da 
entrada (n) é grande o suficiente. 
 
 
Mais formalmente: 
• O(f(n)) é uma estimativa do tempo máximo necessário ao processamento do algoritmo 
� Tempo(n) <= ( )nfC ⋅ para alguma constante C e um valor suficientemente grande 
de n. 
 
 
 
Usando a notação ( )O para estimar tempos de processamento 
Para um algoritmo ( )nO : 
• 5.000 elementos gastam 3.2 segundos 
• 10.000 elementos gastariam 6.4 segundos 
• 20.000 elementos gastariam ...? 
 
 
Para um algoritmo ( )2nO : 
• 5.000 elementos gastam 2.4 segundos 
• 10.000 elementos gastariam 9.6 segundos 
• 20.000 elementos gastariam ...? 
 
 
 
Pior caso, melhor caso, caso médio 
Alguns algoritmos têm um tempo variável de execução. 
def busca(nomes, chave): 
 for i in range(len(nomes)): 
 if nomes[i] == chave: return True 
 return False 
 
 
O que acontece se a chave for o primeiro elemento do List? E o último? E o do meio? O que acontece se a 
chave não for encontrada? 
 
 
Melhor caso 
• O algoritmo é extremamente rápido em algumas situações. Essa análise frequentemente não traz 
muitos ganhos. 
 
 
Pior caso 
• Limite superior do quanto o algoritmo pode ser ruim 
 
 
Caso médio 
• Média de todas as entradas possíveis. Pode ser difícil determinar com precisão. 
 
 
 
Analisando algoritmos recursivos 
def fatorial(n): 
 if n == 0: return 1 
 return n * fatorial(n-1) 
 
 
( )nT é o tempo gasto para processar a entrada n 
( )



−+
=
)1(1
1
nT
nT 
 
 
Essa é uma relação recorrente 
 
 
 
Resolvendo recorrências 
Substituições sucessivas para expandir a recorrência 
)3(111
)2(11
)1(1)(
−+++=
−++=
−+=
nT
nT
nTnT
 
 
 
Generalizando 
)(1*)( inTinT −+= 
 
 
se n é 0 
em caso contrário 
Resolva para ni = 
)(1
)0()(
nOn
TnnT
⇒+=
+=
 
 
 
 
Outro exemplo 
def moveTorre(n, ori, dest, tmp): 
 if n > 0: 
 moveTorre(n-1, ori, tmp, dest) 
 moveUmDisco(ori, dest) 
 moveTorre(n-1, tmp, dest, ori) 
 
 
Estabelece a recorrência 
( )



−+
=
)1(2
1
nTK
nT 
 
 
 
Resolvendo a recorrência 
Substituições sucessivas 
...
)3(8)421(
))3(2(4)21(
)2(4)21(
))2(2(2
)1(2)(
−+++=
−+++=
−++=
−++=
−+=
nTK
nTKK
nTK
nTKK
nTKnT
 
 
 
Generalizando 
)(2)12(
)(2)2...421()( 1
inTK
inTKnT
ii
ii
−+−=
−+++++= −
 
 
 
Resolvendo para ni = 
)2(12)1(
)0(2)12()(
nn
nn
OK
TKnT
⇒−+=
+−=
 
 
 
 
Estimativa de tempos de execução em uma máquina que execute 106 instruções 
por segundo. 
se n é 0 
em caso contrário 
N O(logN) O(N) O(NlogN) O(N
2
) 
10 0,000003 0,000010 0,000033 0,000100 
100 0,000007 0,000100 0,000664 0,010000 
1000 0,000010 0,001000 0,009966 1,000000 
10000 0,000013 0,010000 0,132877 1,7 min 
100000 0,000017 0,100000 1,660964 2,78 hr 
1000000 0,000020 1,000000 19,931569 11,6dias 
1000000000 0,000030 16,7 min 8,3 hr 321 séculos 
 
 
 
Padrão de crescimento