Análise de Algoritmos (intro)

Prévia do material em texto

04/05/2020
1
ANÁLISE DE
ALGORITMOS
Aspectos Teóricos da 
Computação
Prof. Leandro Fernandes
Baseado nos materiais de
- Souza, Silva, Lee, Rezende, Miyazawa (Unicamp), - Ribeiro (FCUP) e - Mariani (UFSC)
Motivações 
para realizar 
Análise de 
Algoritmos
• Provar a “corretude” de um algoritmo.
• Estimar a quantidade de recursos 
(tempo, memória) necessária a 
execução do algoritmo (tarefa da análise 
de complexidade).
• Aprender técnicas e ideias gerais sobre 
o projeto de algoritmos.
• Estratégias: divisão e conquista, algoritmos 
gulosos, programação dinâmica, ...
• Compreender melhor um tema 
recorrente, que é a natureza recursiva 
de vários problemas diferentes.
• Entender a dificuldade intrínseca a 
inúmeros problemas, que implica na 
inexistência de soluções eficientes para 
eles.
1
2
04/05/2020
2
Os custos de um algoritmo ...
• Pode se relacionar a diversos 
fatores:
• Tempo de execução
• Utilização de memória principal
• Utilização de disco
• Consumo de energia
• etc...
• Medidas importantes em outros 
contextos:
• Legibilidade do código
• Custo de implementação
• Portabilidade
• Extensibilidade
• etc...
Análise de Complexidade de Algoritmos
Problemas 
Tratáveis e 
Intratáveis
• Dizemos que um algoritmo resolve um 
determinado problema quando, para 
qualquer entrada, produz uma resposta 
correta.
• Observe que mesmo sendo capaz de resolver 
o problema, um algoritmo pode não ser 
aceitável em termos práticos por demandar 
muito espaço e/ou tempo.
• Um problema é considerado intratável se não 
existir um algoritmo para ele cuja demanda 
de recursos computacionais seja razoável.
3
4
04/05/2020
3
Algoritmos
O que é um algoritmo 
(computacional)?
• Informalmente, um algoritmo é um 
procedimento computacional bem 
definido que:
• recebe um conjunto de valores como 
entrada,
• produz um conjunto de valores como 
saída,
• através de uma sequência de passos 
em um modelo computacional.
• Equivalentemente, um algoritmo é 
uma ferramenta para resolver um 
problema computacional. Este 
problema define a relação precisa 
que deve existir entre a entrada e a 
saída do algoritmo.
Exemplos de problemas e suas instâncias
Problema: Teste de Primalidade
• Tarefa: Determinar se um dado 
número é primo.
• Entrada: 9411461
• Saída: é primo.
• Entrada: 8411461
• Saída: não é primo.
Problema: Ordenação
• Tarefa: Um vetor 𝐴[1…𝑛] é 
crescente se 𝐴[1] ≤ ⋯ ≤ 𝐴[𝑛]. 
Rearranjar um vetor 𝐴[1…𝑛] de 
modo que fique crescente.
• Entrada:
1 n
[33|55|33|44|33|22|11|99|22|55|77]
• Saída:
1 n
[11|22|22|33|33|33|44|55|55|77|99]Uma instância de um problema é um 
conjunto de valores que servem como 
entrada para ele
5
6
04/05/2020
4
Problemas reais de interesse atual...
• Calcular as rotas dos caminhões de entrega de uma 
distribuidora de produtos no estado de São Paulo, 
minimizando os custos de transporte (vehicle routing).
• Calcular o número mínimo de containers necessários 
para transportar um conjunto de caixas com produtos 
(bin packing 3D).
• Calcular a localização e a quantidade mínima de antenas 
de celulares de modo a garantir a cobertura de sinal 
uma certa região geográfica (facility location).
• Dentre vários outros... É importante identificar quando estamos 
lidando com algum problema NP-Difícil.
Algoritmos e Tecnologia
Condição ideal:
• Os computadores têm 
velocidade de processamento e 
capacidade de memória 
infinitos.
• Neste caso, qualquer algoritmo 
é igualmente bom e, por 
conseguinte, esta disciplina seria 
inútil.
O mundo real:
• Há computadores com 
velocidade de processamento na 
ordem de bilhões de instruções 
por segundo e trilhões de bytes 
em memória.
• Mas ainda assim há um limite na 
velocidade de processamento e 
de memória nos computadores.
• Desta forma faz muita diferença ter um bom algoritmo. ô.Ô
7
8
04/05/2020
5
Algoritmos e Tecnologia
• Problema: Ordenação de um vetor de 𝑛 elementos.
• Considere dois computadores, C1 e C2, tal que:
• C1 executa 1 bilhão de instruções por segundo (10
9);
• C2 executa 10 milhões de instruções por segundo (10
7). 
• Suponha dois algoritmos de ordenação:
• Algoritmo 1: implementado por um excelente programador em linguagem de 
máquina (ultrarrápida) para rodar em C1. O código resultante executa 2𝑛
2 instruções.
• Algoritmo 2: implementado por um programador mediano, em linguagem de alto 
nível e usando um compilador “meia-boca” para rodar em C2. O código resultante 
executa 50𝑛 log 𝑛 instruções.
• O que esperar quando ordenamos um vetor de um milhão de elementos? 
Algoritmos e Tecnologia
Algo1 (ling. ultrarrápida) em C1 (+veloz)
• Dados:
• A1: executa 2𝑛
2 instr.
• C1: realiza 10
9 instr/s
• Tempo:
• 𝐴1 =
2(106)2 𝑖𝑛𝑠𝑡𝑟
109 𝑖𝑛𝑠𝑡𝑟/𝑠
= 2. 103𝑠
Algo2 (mediano, poo) em C2 (+lenta)
• Dados:
• A2: executa 50𝑛 log 𝑛 instr.
• C2: realiza 10
7 instr/s
• Tempo:
• 𝐴2 =
50.106 log 106 𝑖𝑛𝑠𝑡𝑟
107 𝑖𝑛𝑠𝑡𝑟/𝑠
= 30𝑠
• Com 10 milhões de números e utilizando o computador mais rápido (C1), o 
algoritmo A1 demoraria 2,3 dias processando, enquanto o algoritmo A2
levaria apenas 20 minutos para concluir esse mesmo trabalho.
9
10
04/05/2020
6
Os custos de um algoritmo ...
• Consideremos um computador com velocidade de 1 THz (terahertz)
• i.e, 1024 vezes mais rápido que um computador de 1 GHz
f(n) n = 20 n = 40 n = 60 n = 80 n = 100
n 2,0x10−11 seg 4,0x10−11 seg 6,0x10−11 seg 8,0x10−11 seg 1,0x10−10 seg
n2 4,0x10−10 seg 1,6x10−9 seg 3,6x10−9 seg 6,4x10−9 seg 1,0x10−8 seg
n3 8,0x10−9 seg 6,4x10−8 seg 2,2x10−7 seg 5,1x10−7 seg 1,0x10−6 seg
n5 2,2x10−6 seg 1,0x10−4 seg 7,8x10−4 seg 3,3x10−3 seg 1,0x10−2 seg
2n 1,0x10−6 seg 1,0 seg 13,3 dias 1,3x105 séc 1,4x1011 séc
3n 3,4x10−3 seg 140,7 dias 1,3x107 séc 1,7x1019 séc 5,9x1028 séc
Muito investimento, pouco retorno!
• Considere o tempo como um elemento fixo, quanto mais podemos 
computar aumentando a velocidade de processamento da máquina?
• A hipótese é perfeitamente plausível, afinal o dia só tem 24 horas!
f(n) Comp. atual 100x mais rápido 1000x mais rápido
n N1 100 x N1 1000 x N1
n2 N2 10 x N2 31,6 x N2
n3 N3 4,64 x N3 10 x N3
n5 N4 2,5 x N4 3,98 x N4
2n N5 N5 + 6,64 N5 + 9,97
3n N6 N6 + 4,19 N6 + 6,29
11
12
04/05/2020
7
Algoritmos e Tecnologia (Conclusões)
• O uso de um algoritmo adequado pode levar a ganhos extraordinários 
de desempenho.
• Isso pode ser tão importante quanto o projeto de hardware.
• A melhora obtida pode ser tão significativa que não poderia ser 
obtida simplesmente com o avanço da tecnologia.
• As melhorias nos algoritmos produzem avanços em outros 
componentes básicos das aplicações (pense nos compiladores, 
buscadores na internet, datamining, visão computacional, games, 
simuladores, etc).
Curvas de 
funções e 
taxas de 
crescimento
0
2
4
6
8
10
12
14
16
18
20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
cte
log n
n½
n
n . log n
n²
n³
13
14
04/05/2020
8
Funções e Taxas de crescimento (por grupos)
0
2
4
6
8
10
12
14
16
18
20
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Funções sublineares
cte
log n
n½
n
0
10
20
30
40
50
60
70
80
90
100
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
Funções Superlineares
n
n . log n
n²
n³
15