PAA-ICOMP-UFAM
Projeto e Análise de Algoritmos
Aulas 1 e 2
Universidade Federal do Amazonas
Instituto de Computação
PAA-ICOMP-UFAM
A idade das coisas
• Universo: Estima-se 13 bilhões (pode ser mais,
pode ser menos...).
• Terra: 4,54 bilhões de anos (pode ser menos,
pode ser mais...)
• Sol: 5 bilhões de anos e mais 3 a 6
bilhões de vida.
PAA-ICOMP-UFAM
Por que análise de algoritmos ?
• O exemplo de fibonacci dado, que rodou em
cerca de 80 segundos para a entrada de 50
elementos, rodaria em cerca de 63 mil anos
para entrada 100.
• Rodaria em [Link].335.113 anos para
entrada 150!
• Isso dá cerca de 210 mil vezes a idade da
terra!
PAA-ICOMP-UFAM
Mais alguns dados…
• Cerca de 70 mil vezes a idade do universo
• Estima-se que em 6,6 bilhões de anos o Sol vai
“engolir a Terra”
• Em 3 a 10 bilhões de anos, a Via Láctea vai colidir
com Andrômeda! Não se sabe o que vai acontecer
conosco...
• Alumínio, plástico, baterias de computador se
decompõem em cerca de mil anos.
• Isso quer dizer que nosso programa teria pouca
chance de terminar.
PAA-ICOMP-UFAM
Tempos para calcular fibonacci
Table
n F. doubling F. matrix F. doubling, naïve F. matrix, naïve dynamic prog. recursive
1 5 414 1 042 4 197 887 10 4
5 5 989 3 677 4 787 3 147 172 219
10 6 283 4 952 5 022 4 154 370 3 113
20 6 542 5 923 5 234 4 985 763 394 000
40 6 818 6 880 5 433 5 715 1 552 5 980 000 000
50 6 806 7 742 5 486 6 446 2 023
100 7 279 9 225 5 904 7 717 4 472
200 8 006 11 700 6 556 9 969 10 640
1 000 14 660 50 870 13 130 48 230 118 000
10 000 466 400 3 519 000 538 400 4 382 000 8 700 000
100 000 20 800 000 130 600 000 51 640 000 330 700 000 819 700 000
1 000 000 846 100 000 4 724 000 000 5 182 000 000 28 310 000 000 82 000 000 000
3 981 072 7 654 000 000
PAA-ICOMP-UFAM
Escolhas menos dramáticas
• O exemplo de fibonacci é extremo e parece
pouco útil.
• Muitas vezes, a troca de um algoritmo por um
mais eficiente pode resultar em economia de
tempo e dinheiro para empresas.
• Erros na escolha do algoritmo certo geram
prejuizos.
PAA-ICOMP-UFAM
Por que projeto de algoritmos ?
• Aprendemos a solucionar problemas de maneira
empírica
• Contudo, há certos padrões no desenvolvimento de
soluções que podem ser repetidos e aplicados na
resolução de novos problemas
• Uso de técnicas de projeto pode aumentar a
velocidade para encontrar soluções, ajudar a
resolver problemas que antes não saberíamos
resolver ou ainda ajudar a encontrar soluções
melhores
PAA-ICOMP-UFAM
Algoritmos
• Um algoritmo: A essência de um
procedimento computacional composto por
instruções seqüenciais passo a passo
• Um programa: Implementação de um
algoritmo em uma dada linguagem de
programação
• Estrutura de dados: forma de organizar os
dados necessários à solução de um problema
PAA-ICOMP-UFAM
Solução Algoritmica
Instância de Algoritmo
Entrada Saída
relacionada
atendendo a
à Entrada
especificação
– O Algoritmo descreve ações sobre a instância de
entrada
– Existem infinitos algoritmos corretos para um
mesmo problema algorítmico
PAA-ICOMP-UFAM
Examplo: Ordenação
ENTRADA SAÍDA
sequência de números uma permutação da
sequência de entradas
a1, a2, a3,….,an b1,b2,b3,….,bn
Ordenação
2 5 4 10 7 2 4 5 7 10
Corretude Tempo de Execução
Para qualquer entrada dada, o Depende de:
algortimo termina com saída • número de elementos (n)
• o quão (parcialmente)
• b1, b2, b3, …., bn, onde ordenada está a lista
• b1 < b2 < b3 < …. < bn • solução algoritmica
PAA-ICOMP-UFAM
Problema Algoritmico
Especificação Especificação
da ? da Saída como
Entrada função da
Entrada
– Existe um número infinito de instâncias da entrada que
satisfazem a especificação. Por exemplo:
• Uma sequência finita, ordenada, não decrescente de números
naturais:
– 1, 20, 908, 909, 100000, 1000000000.
– 3.
PAA-ICOMP-UFAM
Ordenação por Inserção
A 3 4 6 8 9 7 2 5 1
1 j n
i
“insira A[j] na sequência
ordenada A[1..j-1]”
para j=2 até n
faça pivot:=A[j]
i ← j-1
enquanto i>0 e A[i]>pivot faça
A[i+1] ← A[i]
i--;
fim-enquanto
A[i+1] ← pivot;
PAA-ICOMP-UFAM
Análise de Algoritmos
• Eficiência:
– Tempo de execução
– Espaço (memória) usado
• Eficiência como função do tamanho da
entrada
PAA-ICOMP-UFAM
Modelos de Computação
• O que deve ser contabilizado ?
• Modelo RAM
– Instruções (considerando tempo constante):
• Aritiméticas (+, -, *, etc.)
• Atribuição
• Comparação
• Controle (desvios, chamadas de procedimento, etc.)
PAA-ICOMP-UFAM
Análise: Ordenação por Inserção
• Determinar o tempo de execução como função do tamanho
da entrada
para j=2 até n n-1 vezes
faça pivot:=A[j]
i ← j-1
enquanto i>0 e A[i]>pivot faça Para cada uma das
n-1 vezes, tj vezes
A[i+1] ← A[i]
i--;
fim-enquanto
A[i+1] ← pivot;
PAA-ICOMP-UFAM
Análise: Ordenação por Inserção
• Determinar o tempo de execução com função do tamanho da
entrada
para j=2 até n n
faça pivot:=A[j] n-1
i ← j-1 n-1
n
enquanto i>0 e A[i]>pivot faça ∑ j =2 t j
n
A[i+1] ← A[i] ∑nj =2 (t j − 1)
i--; ∑ j =2 (t j − 1)
fim-enquanto
A[i+1] ← pivot; n-1
PAA-ICOMP-UFAM
Melhor/Pior/Médio
• Melhor Caso
– elementos já ordenados
– todos os testes falham, o loop interno nunca é
executado
– neste caso, tj=1 e a operação é executada n vezes
n
∑t j = t 2 + t3 + … + t n = 1 + 1 + … + 1 = n − 1
– Portanto aj =complexidade
2
de tempo é dada por
f(n)=n-1
PAA-ICOMP-UFAM
Melhor/Pior/Médio
• Melhor Caso
– elementos já ordenados
– tj=1, T(n) =C1 n, ou seja, tempo linear.
• Pior caso: elementos em ordem inversa
– tj=j, T(n) = C2 n2, ou seja, tempo quadrático
• Tempo médio:
– tj=j/2, T(n) = C2 n2, ou seja, tempo quadrático
PAA-ICOMP-UFAM
Melhor/Pior/Médio (2)
– Determinar o tempo de execução para diferentes
instancias de tamanho n:
6n Pior Caso
Tempo de Execução
5n
Caso Médio
4n
3n Melhor Caso
2n
1n
Instâncias
PAA-ICOMP-UFAM
Melhor/Pior/Médio (3)
– Para instâncias de todos os tamanhos:
Pior Caso
worst-case
6n average-case
Caso Médio
de Execução
time
5n
Melhor Caso
best-case
Running
4n
Tempo
3n
2n
1n
1 2 3 4 5 6 7 8 9 10 11 12 …..
Input instance
Tamanho size
da Entrada
PAA-ICOMP-UFAM
Melhor/Pior/Médio (4)
• O pior caso é geralmente usado:
– Estabelece um limite superior na complexidade de
tempo do algoritmo
– Para alguns algoritmos o pior caso é bastante
freqüente
– Frequentemente o caso médio é tão ruim quando
o pior caso
– Encontrar o caso médio pode ser muito difícil
PAA-ICOMP-UFAM
Funções de Crescimento (2)
1,00E+155
1,00E+143
1,00E+131
1,00E+119 n
log n
1,00E+107
sqrt n
1,00E+95 n log n
100n
1,00E+83 n^2
T(n)
n^3
1,00E+71
2^n
1,00E+59
1,00E+47
1,00E+35
1,00E+23
1,00E+11
1,00E-01
2 4 8 16 32 64 128 256 512 1024
n
PAA-ICOMP-UFAM
O que é razoável em computação?
função/
10 20 50 100 300
n
1/10,000 1/2,500 1/400 1/100 9/100
n2 segundos segundos segundos segundos segundos
Polinomial
1/10 3.2 5.2 2.8 28.1
n5 segundos segundos minutos horas dias
400
1/1000 1 35.7 Séculos de
2n trilhões de
Exponencial
segundos segundos anos
séculos
75 dígitos
2.8 3.3 trilhões Seculos de Séculos de Séculos de
nn horas de anos 70 dígitos 185 dígitos 728 dígitos
PAA-ICOMP-UFAM
Exemplo 2: Busca
ENTRADA SAÍDA
• sequência de números • índice do número or NIL
• um número (cosulta)
a1, a2, a3,….,an; q j
2 5 4 10 7; 5 2
2 5 4 10 7; 9 NIL
PAA-ICOMP-UFAM
Busca (2)
j=1
while j<=length(A) and A[j]!=q
do j++
if j<=length(A) then return j
else return NIL
n Pior caso: f(n)=n, caso-médio: n/2
n Não se pode fazer melhor ! Este é um limite
inferior para o problema de busca em uma
seqüência arbritrária.
PAA-ICOMP-UFAM
Exemplo 2: Busca
ENTRADA SAÍDA
• sequência de números ordenada • o índice do número
não-descendente encontrado ou NIL
• um número (cosulta)
a1, a2, a3,….,an; q j
2 4 5 7 10; 5 2
2 4 5 7 10; 9 NIL
PAA-ICOMP-UFAM
Busca binária
n Idéia: Divisão e conquista, uma das técnicas
chaves para projeto de algoritmos
left=1
right=length(A)
do
j=(left+right)/2
if A[j]==q then return j
else if A[j]>q then right=j-1
else left=j+1
while left<=right
return NIL
PAA-ICOMP-UFAM
Busca Binária – Análise
• Quantas vezes o laço é executado ?
– A cada interação o número de posições n é
cortado ao meio
– Quantas vezes se corta ao meio n para se chegar a
1?
– lg n
PAA-ICOMP-UFAM
Análise Assintótica
• Objetivo: simplificar a análise de complexidade de
tempo eliminando “detalhes” que podem ser
afetados por fatores de implementação ou hardware
– 3n2 → n2
• Comportamento assintótico: como o tempo de
execução do algoritmo cresce com o tamanho da
entrada.
PAA-ICOMP-UFAM
Notação Assintótica
• Notação O (O - Notation)
– Limite assintótico superior
– f(n) = O(g(n)), se existem
constantes positivas c e n0, f(n) ≤
c g(n) para n ≥ n0
Tempo de execução
c ⋅ g ( n)
f (n )
– f(n) e g(n) são funções sobre
inteiros não negativos
• Usada para análise do pior caso
n0 Tamanho da Entrada
PAA-ICOMP-UFAM
Notação Assintótica (2)
• Notação Ω
– limite assintótico inferior
– f(n) = Ω(g(n)) se existem
constantes positivas c e n0, tais
Tempo de Execução
que c g(n) ≤ f(n) para n ≥ n0
f (n )
• Usada para descrever o melhor c ⋅ g ( n)
caso de tempos de execução ou
limites inferiores de problemas
algorítmicos n0 Tamanho da Entrada
– [Link]., o limite inferior para busca
em lista não ordenada é Ω(n).
PAA-ICOMP-UFAM
Notação Assintótica (3)
• Regra prática: Remover termos de menor
ordem e fatores constantes.
– 50 n log n é O(n log n)
– 7n - 3 é O(n)
– 8n2 log n + 5n2 + n é O(n2 log n)
• Nota: Mesmo que 50 n log n seja O(n5),
costuma-se utilizar aproximações de menor
ordem possível !!!
PAA-ICOMP-UFAM
Notação Assintótica (4)
• Notaçao Θ
– Limite assintótico máximo e
mínimo
– f(n) = Θ(g(n)) se existem
constantes c1, c2, e n0, tais que c1
Tempo de Execução
c 2 ⋅ g (n )
g(n) ≤ f(n) ≤ c2 g(n) para n ≥ n0 f (n )
• f(n) = Θ(g(n)) se, e somente se, c 1 ⋅ g (n )
f(n) = Ο(g(n)) e f(n) = Ω(g(n))
• O(f(n)) é frequente confundido
com Θ(f(n)) n0 Tamanho da Entrada
PAA-ICOMP-UFAM
Notação Assintótica (5)
• Notação o : f(n)=o(g(n))
– Para todo c positivo, deve existir n0 , tal que f(n) ≤
c g(n) para n ≥ n0
– Usada para comparação de tempos de execução.
Se f(n)=o(g(n)), dizemos que g(n) domina f(n).
• Notação ω:f(n)=ω(g(n))
– Análoga a função o com relação à Ω
PAA-ICOMP-UFAM
Notação Assintótica (6)
• Analogia com número reais
– f(n) = O(g(n)) ≅ f≤g
– f(n) = Ω(g(n)) ≅ f≥g
– f(n) = Θ(g(n)) ≅ f=g
– f(n) = o(g(n)) ≅ f<g
– f(n) = ω(g(n)) ≅ f>g
• Abuso de notação:
– f(n) = O(g(n)) indica que f(n) ∈O(g(n))
PAA-ICOMP-UFAM
Exercícios
• Verifique se as afirmativas são corretas:
• No pior caso, o algoritmo de inserção é
2
Θ(n )
2 2 n = O(2 n )
n +1 n
2 = O(2 )
O(n 2 ) + O(n 2 ) = O(n 2 )
O ( n) × O ( n) = O ( n)