Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 1
Projeto e Análise de Algoritmos
Celso Carneiro Ribeirohttp://www.inf.puc-rio.br/~celso
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 2
Parte 2
Análise de Algoritmos
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 3
Análise de algoritmos
• Motivação• Análise de algoritmos• Complexidade de pior caso• Notação “O”• Aplicações• Algoritmos polinomiais• Comparação de algoritmos• Algoritmos recursivos• Algoritmos não-polinomiais• Algoritmos pseudo-polinomiais
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 4
Motivação
• Problema:– Alunos cursam disciplinas.– Cada disciplina tem uma prova.– Há um único horário em que são marcadas provas em cada
dia.– Provas de duas disciplinas diferentes não podem ser
marcadas para o mesmo dia se há alunos que cursam as duas disciplinas.
• Montar um calendário de provas:– satisfazendo as restrições de conflito e …– … minimizando o número de dias necessários para realizar
todas as provas.
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 5
Motivação
• Modelagem por conjuntos:
A
B
C
D
E
F
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 6
Motivação
• Os alunos que fazem apenas uma disciplina influem na modelagem? – Não!
• O número de alunos que cursam simultaneamente um par de disciplinas influi na modelagem? – Não!– E se o objetivo fosse minimizar o número de alunos
“sacrificados”?– Neste caso, sim!
• Este modelo pode ser simplificado?
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 7
Motivação
• Simplificação tratando-se apenas as interseções:
A
B
C
D
E
F
A
B
C
D
E
F
Considerar apenas as interseções não-vazias.
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 8
Motivação
• Simplificação com a utilização de um grafo de conflitos:
A
B
C
D
E
F
disciplinas → nós conflitos → arestas
A
B
C
D
E
F
A
B C F
E
D
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 9
Motivação
• Simplificação com a utilização de um grafo de conflitos:
A
B
C
D
E
F A
B C F
E
D
disciplinas → nós conflitos → arestas
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 10
Modelo de dados
• As provas de um par de disciplinas não podem ser marcadas simultaneamente se existe uma aresta entre os nós que representam estas duas disciplinas.
• Outros modelos de dados: listas, árvores, conjuntos, circuitos
• Como representar em computador o modelo de dados chamado grafo?– Matriz de incidência (nó-aresta)– Matriz de adjacência (nó-nó)
Grafo = [ nós, arestas ]
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 11
Matriz de incidência
• n nós e m arestas• Memória utilizada: nm
000110000001100000011011100010100001100001
nxmA
A
B
C
D
E
F
A
B
D
E
FC
ab
cde
fg
a b c d e f g
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 12
Matriz de adjacência
• Memória utilizada: n2
010100101000010001100011000101001110
nxnB
A
B
C
D
E
F
A
B
D
E
FC
ab
cde
fg
A B C D E F
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 13
Listas de adjacências
• Estas matrizes são duas “estruturas de dados” que representam o mesmo modelo de dados (grafo).
• Outra estrutura de dados para grafos são as listas de adjacências.
A
B
D
E
FC
ab
cde
fg
FEDCBA B C D
A CB A FA ED FE C
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 14
Motivação
• Como montar um calendário satisfazendo as restrições de conflito?
• Marcar para o primeiro dia qualquer combinação de disciplinas sem conflitos: A, B, C, D, E, F, AE, AF, BD, BE, BF, CD, CE, DF, BDF
B C
E
D
F
A
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 15
Motivação
• Como montar um calendário satisfazendo as restrições de conflito?
• Marcar para o primeiro dia qualquer combinação de disciplinas sem conflitos: A, B, C, D, E, F, AE, AF, BD, BE, BF, CD, CE, DF, BDF
B C
E
D
F
A
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 16
Motivação
• Como montar um calendário satisfazendo as restrições de conflito?
• Marcar para o primeiro dia qualquer combinação de disciplinas sem conflitos: A, B, C, D, E, F, AE, AF, BD, BE, BF, CD, CE, DF, BDF
B C
E
D
F
A
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 17
Motivação
• Como montar um calendário satisfazendo as restrições de conflito?
• Marcar para o primeiro dia qualquer combinação de disciplinas sem conflitos: A, B, C, D, E, F, AE, AF, BD, BE, BF, CD, CE, DF, BDF
B C
E
D
F
A
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 18
Motivação
• Como montar um calendário satisfazendo as restrições de conflito?
• Marcar para o primeiro dia qualquer combinação de disciplinas sem conflitos: A, B, C, D, E, F, AE, AF, BD, BE, BF, CD, CE, DF, BDF
B C
E
D
F
A
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 19
Motivação
• Como montar um calendário satisfazendo as restrições de conflito?
• Marcar para o primeiro dia qualquer combinação de disciplinas sem conflitos: A, B, C, D, E, F, AE, AF, BD, BE, BF, CD, CE, DF, BDF
B C
E
D
F
A
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 20
Motivação
• Como montar um calendário satisfazendo as restrições de conflito?
• Marcar para o primeiro dia qualquer combinação de disciplinas sem conflitos: A, B, C, D, E, F, AE, AF, BD, BE, BF, CD, CE, DF, BDF
B C
E
D
F
A
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 21
Motivação
• Como montar um calendário satisfazendo as restrições de conflito?
• Marcar para o primeiro dia qualquer combinação de disciplinas sem conflitos: A, B, C, D, E, F, AE, AF, BD, BE, BF, CD, CE, DF, BDF
B C
E
D
F
A
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 22
Motivação
• Como montar um calendário satisfazendo as restrições de conflito?
• Marcar para o primeiro dia qualquer combinação de disciplinas sem conflitos: A, B, C, D, E, F, AE, AF, BD, BE, BF, CD, CE, DF, BDF
B C
E
D
F
A
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 23
Motivação
• Como montar um calendário satisfazendo as restrições de conflito?
• Marcar para o primeiro dia qualquer combinação de disciplinas sem conflitos: A, B, C, D, E, F, AE, AF, BD, BE, BF, CD, CE, DF, BDF
B C
E
D
F
A
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 24
Motivação
• Como montar um calendário satisfazendo as restrições de conflito?
• Marcar para o primeiro dia qualquer combinação de disciplinas sem conflitos: A, B, C, D, E, F, AE, AF, BD, BE, BF, CD, CE, DF, BDF
B C
E
D
F
A
• Escolher por exemplo o par de disciplinas B e E para o primeiro dia e retirá-las do grafo.
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 25
Motivação
• Como montar um calendário satisfazendo as restrições de conflito?
• Marcar para o primeiro dia qualquer combinação de disciplinas sem conflitos: A, B, C, D, E, F, AE, AF, BD, BE, BF, CD, CE, DF, BDF
C
D
F
A
• Escolher por exemplo o par de disciplinas B e E para o primeiro dia e retirá-las do grafo.
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 26
Motivação
• Marcar para o segundo dia qualquer combinação de disciplinas sem conflitos: A, C, D, F, AF, CD, DF
C
D
F
A
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 27
Motivação
• Marcar para o segundo dia qualquer combinação de disciplinas sem conflitos: A, C, D, F, AF, CD, DF
C
D
F
A
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 28
Motivação
• Marcar para o segundo dia qualquer combinação de disciplinas sem conflitos: A, C, D, F, AF, CD, DF
C
D
F
A
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 29
Motivação
• Marcar para o segundo dia qualquer combinação de disciplinas sem conflitos: A, C, D, F, AF, CD, DF
C
D
F
A
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 30
Motivação
• Marcar para o segundo dia qualquer combinação de disciplinas sem conflitos: A, C, D, F, AF, CD, DF
C
D
F
A
• Escolher por exemplo o par de disciplinas D e F para o segundo dia e retirá-las do grafo.
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 31
Motivação
• Marcar para o segundo dia qualquer combinação de disciplinas sem conflitos: A, C, D, F, AF, CD, DF
C
A
• Escolher por exemplo o par de disciplinas D e F para o segundo dia e retirá-las do grafo.
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 32
Motivação
• Marcar A ou C para o terceiro dia e a que sobrar para o quarto dia:
C
A
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 33
Motivação
• A solução assim construída utiliza quatro dias: B-E no primeiro dia, D-F no segundo dia, A no terceiro e C no quarto:
B C
E
D
F
A
• Uma solução com quatro dias corresponde a colorir os nós do grafo de conflitos com quatro cores!
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 34
Motivação
• Esta solução utiliza o menor número possível de dias? ou ...• É possível montar uma solução com menos dias? ou ...• É possível colorir o grafo de conflitos com três cores?
B C
E
D
F
A
• É impossível colorir o grafo de conflitos com menos de três cores! (por que?)
Sim!
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 35
Motivação
• Como montar um escalonamento com o menor número possível de dias?
• Recordando: um subconjunto independente de um grafo é um subconjunto de nós sem nenhuma aresta entre eles.
• Logo, um conjunto de disciplinas que forma um subconjunto independente dos nós do grafo de conflitos pode ter suas provas marcadas para o mesmo dia.
• Os nós deste subconjunto independente podem receber a mesma cor.
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 36
Motivação
• Quanto mais disciplinas forem marcadas para o primeiro dia, menos disciplinas sobram para os dias seguintes e, portanto, serão necessários menos dias para realizar as provas das disciplinas restantes.
• Então, marcar para o primeiro dia as provas das disciplinas correspondentes a um subconjunto independente máximo.
• Retirar os nós correspondentes a estas disciplinas do grafo de conflitos.
• Continuar procedendo da mesma maneira, até as provas de todas as disciplinas terem sido marcadas.
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 37
Motivação
• Subconjunto independente máximo no grafo de conflito?BDF
B C
E
D
F
A
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 38
Motivação
• Subconjunto independente máximo no grafo de conflito?BDF
B C
E
D
F
A
• Eliminar os nós B, D e F do grafo de conflitos.
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 39
Motivação
• Subconjunto independente máximo no grafo de conflito?BDF
C
EA
• Eliminar os nós B, D e F do grafo de conflitos.
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 40
Motivação
• Subconjunto independente máximo no grafo de conflito?CE
C
EA
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 41
Motivação
• Subconjunto independente máximo no grafo de conflito?CE
C
EA
• Eliminar os nós C e E do grafo de conflitos.
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 42
Motivação
• Subconjunto independente máximo no grafo de conflito?CE
A
• Eliminar os nós C e E do grafo de conflitos.
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 43
Motivação
• Subconjunto independente máximo no grafo de conflito?A
A
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 44
Motivação
• Subconjunto independente máximo no grafo de conflito?A
A
• Eliminar o nó A do grafo de conflitos.• Solução completa (todos nós coloridos).
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 45
Motivação
• A solução encontrada usa o número mínimo de cores para colorir o grafo, logo o número de dias para aplicar todas as provas é mínimo:
B C
E
D
F
A
• Foi proposto um algoritmo para colorir um grafo com o menor número de cores.
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 46
Motivação
• O passo básico deste algoritmo corresponde a determinar um subconjunto independente máximo.
• Entretanto, este subproblema a ser resolvido a cada iteração (já é um problema NP-completo por si só, ou seja, cada subproblema) é computacionalmente difícil.
• Além deste procedimento ser computacionalmente difícil, é possível garantir que este algoritmo sempre encontra a solução ótima com o número mínimo de cores?– Ou demonstrar que sim, ou dar um contra-exemplo.
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 47
Motivação
• Considerando-se o grafo abaixo, qual solução seria encontrada pelo algoritmo?
DC E F
G
BA
LK
H JII
E
H
D
Os oito nós externos formam um subconjunto independente de cardinalidade máxima e podem todos ser coloridos com a mesma cor.
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 48
Motivação
• Considerando-se o grafo abaixo, qual solução seria encontrada pelo algoritmo?
Os oito nós externos formam um subconjunto independente de cardinalidade máxima e podem todos ser coloridos com a mesma cor.
DC E F
G
BA
LK
H JII
E
H
D
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 49
Motivação
• Considerando-se o grafo abaixo, qual solução seria encontrada pelo algoritmo?
DC E F
G
BA
LK
H JII
E
H
DEsta solução é ótima, ou é possível colorir este grafo com menos cores?
Sim: o grafo pode ser colorido com apenas duas cores.
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 50
Motivação
• Considerando-se o grafo abaixo, qual solução seria encontrada pelo algoritmo?
Esta solução é ótima, ou é possível colorir este grafo com menos cores?
DC E F
G
BA
LK
H JI
Sim: o grafo pode ser colorido com apenas duas cores
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 51
Motivação
• O algoritmo proposto nem sempre encontra a solução ótima (isto é, uma solução com o número mínimo de cores).
• Este algoritmo é então um algoritmo aproximado ou uma heurística para o problema de coloração de grafos.
• Algoritmos exatos vs. algoritmos aproximados:– qualidade da solução– tempo de processamento
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 52
Algoritmo
Seqüência precisa, não-ambígua de passos elementares que levam à solução de um problema.
• Definição informal, imprecisa! • Definição formal: máquina de Turing• Especificação: português
português estruturadopseudo linguagemlinguagem de
programação
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 53
Algoritmo
Passo 0: k 1Passo 1: alocar o maior número possível de provas no dia k
sem conflitoPasso 2: eliminar estas provas do grafo (nós, arestas) Passo 3: fazer k k+1 e voltar ao passo 1
• Subproblema resolvido a cada iteração: alocar o maior número possível de provas sem conflito
• Conjunto independente de cardinalidade máxima
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 54
Análise de algoritmos
• Como avaliar a eficiência de um algoritmo?
• Dados dois algoritmos para a resolução de um mesmo problema, qual é o mais eficiente?
• Quando um problema pode ser considerado como bem resolvido?
Objetivos e questões básicas:
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 55
Problema do caixeiro viajante
anosnanosn
segundossoluçãoumasoluçõesn
1680228021
10:2
!1 9
• n cidades, distâncias cij
• Obter a rota de menor comprimento que parte de uma cidade, visita uma vez cada cidade e retorna à cidade inicial.– Cada solução é uma permutação circular das n cidades.
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 56
Como escolher um algoritmo?
• Algoritmo mais fácil de entender, implementar, documentar
• Algoritmo mais rápido ou eficiente
• Eficiência é uma medida objetiva:
– Memória
– I/O
– Comunicação
– Acesso a memória secundária
– Tempo → problemas grandes (crescimento assintótico)
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 57
Como escolher um algoritmo?
• É impossível processar um algoritmo/programa para todas as entradas (dados) possíveis.
• Desenvolver medidas do tempo de processamento que resumam seu comportamento para todas as entradas possíveis.
• Considerar a eficiência de um algoritmo como sendo a quantidade de tempo que usa, medida como função do tamanho da entrada.
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 58
Enfoques
• Benchmark – considerar uma pequena coleção de entradas “típicas” e considerá-la como representativa dos possíveis dados de entrada.
• Métodos analíticos – agrupar as entradas possíveis de acordo com seu tamanho
– Ordenação: n
– Matriz: m,n
– Grafo: m,n
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 59
Enfoques
• Usar uma função T(n) para representar o número de unidades de tempo utilizadas pelo algoritmo/programa quando aplicado a um problema cujo tamanho da entrada é n
– T(n) = cn
– T(n) = d + en + fn2
– T(n) número de instruções
número de operações elementares
tempo de CPU
• O tempo de processamento depende dos dados da própria entrada, não apenas do seu tamanho!
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 60
Enfoques
• T(n) = tempo {MÉDIO, MÍNIMO, MÁXIMO} de processamento calculado sobre todas as entradas de tamanho n
– Médio: mais difícil, mais realista
– Mínimo: pouca informação
– Máximo: conservador
ordenação 1 2 3 4 5 6
n=6 6 5 4 3 2 1
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 61
Exemplo: Ordenação por seleção
A[1] A[2] … A[n]
para i = 1 até n-1 façainício
smaller i para j=i+1 até n faça
se A[j] < A[smaller] então smaller j; temp A[smaller]
A[smaller] A[i] A[i] tempfim
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 62
Análise
• Contar como operações as linhas de código, executando-se atribuições, comparações,…
casopiorinfavorávelmaiscaso
jsmaller
insetestetotalinpara
smallertestetotalnpara
,1)1(,0
1)1(:)(1)(1)1( :
1 :)(1)(1 :
52
112
)(
)1(2
)1(156)(
)(3)1(234)(
)1(31)1(311)(
)1(3:
2
1
1
1
1
nnnT
nnnnT
innnnT
ninnnT
ntemp
n
i
n
i
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 63
Comparação de dois algoritmos22)(100)( nnTennT BA
n 50 – Algoritmo Bn 50 – Algoritmo A
TB(n)=2n2
TA(n)=100n
0
5000
10000
15000
20000
20 40 60 80 100
• Para n 50, a vantagem do algoritmo A sobre o algoritmo B cresce com n.• A função T(n) determina o maior problema que pode ser resolvido com este algoritmo
(em determinado tempo de computação)
milisegundos
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 64
Comparação de dois algoritmos
Quando a velocidade dos computadores aumenta, maiores aumentos no tamanho dos maiores problemas que podem ser resolvidos são observados para programas cujo tempo de processamento cresce mais lentamente.
Segundos Maior problema que pode ser resolvido
Alg. A Alg. B1 10 22
10 100 70
100 1000 223
1000 10000 707
Procurar algoritmos com menores taxas de crescimento!
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 65
Comparação de dois algoritmos
• O tempo de processamento de um dado algoritmo para uma entrada particular ainda depende– do computador– do compilador
• Mesmo conhecendo-se algoritmo/programa/máquina/ compilador, ainda é difícil prever o tempo de processamento de um programa
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 66
Notação O
• Número de instruções de máquina geradas por um computador• Número de instruções de máquina executadas (por segundo)
por um determinado computador
T(n) = 100n → T(n) = O(n)“Alguma constante vezes n”
• Também esconde o fato de que instruções diferentes executam em tempos diferentes.
Descrever o tempo de processamento de um programa usando a notação O, que “esconde” fatores tais como:
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 67
Notação O
T(n) = O(f(n)) se existe um inteiro n0 e uma constante c > 0 tal que T(n) ≤ c.f(n) para qualquer n ≥ n0
100)(
4,1412
)1(212
)()()1()(
2
022
2222
22
nOnT
cnnnn
nnnnnn
nOnTnnT
para
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 68
Notação O
Constantes e termos de menor grau não importam:
0110
012
21
1
1)()(
)(
aaaacnnOnT
anananananT
kk
k
kk
kk
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 69
Notação O
))(()(
2,1002
lim
22
0lim
0
3
3
nhOnfnhOngngOnf
cnn
OnnT
ngOnhngngnh
nn
nn
n
:dadeTransitivi
ou
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 70
Notação O
No caso geral, obter T(n) de forma exata pode ser muito difícil. Esta tarefa pode ser muito simplificada se, em vez de obter-se T(n), procura-se uma expressão O(f(n)) como limitante superior de T(n).
Ordenação por seleção: T(n) = O(n2)
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 71
Notação O
5.73
3
222
2
100
1002
42
112
nOnOnO
nOnOnOnT
nnnT
Limite mais justo: menor grau constante = 1
T(n) = O(n2)
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 72
Notação O
n
n
nO
nOO
nO
nO
nnOnO
nOO
!2
log
log1
3
2
Constante
Logarítmico
Linear
nlogn
Quadrático
Cúbico
Exponencial
Fatorial
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 73
Notação O
Expressões na notação O podem freqüentemente ser adicionadas:
nfOnTnT
nfOnfHipótese
nfOnT
nfOnT
121
12
22
11
)()(
)(:
)(
)(
Aplicação: programas que podem ser decompostos em duas partes
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 74
Exemplo 1Expressões na notação O podem freqüentemente ser adicionadas:
vezesnnOOO
OOOOO
nOnTnTnTnT
11
11111
)( 2321
ler npara i = 1 até n faça
para j = 1 até n façaA[i,j] 0
para i=1 até n façaA[i,i] 1
1)(1 OnT
22 )( nOnT
nOnT )(3
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 75
Exemplo 2 - Fatorial
Ler ni 2fact 1enquanto i ≤ n façainicio
fact fact * ii i+1
fimEscreva fact
)()(1).1(1
: 5115)(
11)221)(1(111:
13)1(35)(
1133111:
12
nOnTOnO
ONotaçãonnnT
nnTInstruções
nnnT
Linhas
ninii
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 76
Análise do tempo de processamento
• Comandos simples: O(1)– Atribuição, E/S, go to– Bloco de comandos simples consecutivos: O(1)
• Bloco for– Limites do for dão um limite superior para o número de
vezes que o bloco é executado– Caso mais simples: multiplicar a complexidade do bloco
pelo limite superior do número de vezes que é executado
Tempo de processamento ~ Complexidade
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 77
Análise do tempo de processamento
para j = 1 até n faça → n vezesA[i,j] 0 → O(1)
O(n)
para i = 1 até n faça → n vezes para j = 1 até n faça → n vezes
A[i,j] 0 → O(1)T(n) = nT’(n) = n(n.O(1)) = O(n2)
Selection sort:
smaller = i → O(1)para j = i+1 até n faça → n vezes
se A[j] < A [smaller] então smaller j; → O(1)
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 78
Análise do tempo de processamento
• i n-1 T(n)=O(1)• i < n-1 T(n)=O(1) + (n-i) · O(1) = O(n-i)• T(n)=O (max {1, n-i} )• Complexidade do algoritmo completo
2
21
1
1
1
)1(
)(
1,1max1
nOnOinO
vezesn
nOinO
OinOO
n
i
n
i
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 79
Análise do tempo de processamento
• Teste:
se <condição> então → O(1)<parte_do_então> →
O(f(n))senão
<parte_do_senão> → O(g(n))
O (max(f(n), g(n))
se A[i,i]=0 então → f(n) = n2
para i =1 a n faça para j = 1 a n faça A[i,j] 0
senão → g(n) = npara i = 1 a n faça A[i,i] 0
O(n2)
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 80
Análise do tempo de processamento
• Verificar se um elemento x pertence a um vetor A[.] (busca seqüencial) com n elementos:
A[n+1] xi 1enquanto x A[i] faça i i+1;se i = n+1 então elemento não existe;se não elemento existe;
O(1) + O(n)·O(1) + O(1) = O(n)
• Programas com chamadas de funções ou procedimentos
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 81
Análise do tempo de processamento
• Procurar algoritmos de menor complexidade• Na prática, as constantes e termos de menor grau omitidos
podem fazer uma diferença significativa• Procurar otimizar o código nos pontos críticos
618992)(
42)(2
22
nnnT
nnnTnO
B
A
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 82
Cálculo de polinômios
xPcalcularxDado
axaxaxaxP
n
nn
nnn
,01
11
P A[0]para i = 1 até n faça
P P + A[i] · (xi);
T1(n) = n · O(n) = O(n2)
P A[0]y y · x;para i 1 até n faça
P P + A[i] · yy y · x;
T2(n) = n · [O(1)+O(1)] = O(n)
O(n) mesmo?
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 83
Método de Horner
xPcalcularxDado
axaxaxaxP
n
nn
nnn
,01
11
P A[n]para i n-1 até 0 faça
P A[i] + x * P;T3(n) = n · O(1) = O(n)
nn
nnnn
nnnn
nnn
nnn
nn
n
xaxaxaaP
xaxaxaa
xaxaaxaP
xaxaa
xaaxaPaxaP
aP
2
210
32123
2123
212
12
1
Qual dos três algoritmos é melhor?
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 84
Ordenação pelo método da bolhainício chave 1;
enquanto chave=1 façainício chave 0; para i = 1 até n-1 faça início
se A[i+1] < A[i] então início temp A[i]; A[i] A[i+1]; A[i+1] temp; chave 1; fim
fimfim
fim
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 85
Ordenação pelo método da bolha
• Em cada iteração, pelo menos um elemento é colocado na posição final correta.
• No máximo, n-1 iterações
T(n) = (n-1) · [(n-1) · O(1)]T(n) = O(n2)
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 86
A[1] ... A[n]
soma 0;para i=1 até n faça soma soma + A[i];
fim-para; media soma / n; maisperto 1;
i 2;enquanto i n faça
se (A[i]–media)**2 < (A(maisperto)-media)**2 entao maisperto i;i i + 1;
fim-enquanto;
Calcular média e elemento mais próximo
T(n) = O(1) + n · O(1) + O(1) + (n-1) · O(1)T(n) = O(n)
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 87
Verificar se um inteiro é primo
prime true; i 2; enquanto i**2 n faça
se (n mod i) = 0 então;início; prime false; goto 99;
fim; senao i i + 1;fim-enquanto;
99: imprimir resultado;
T(n) = O(1) + · O(1)T(n) = O( )
nn
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 88
Pesquisa binária
x A[1] ...A[n] ? (ordenado)
min 1; max n; med (min + max)/2; enquanto max > min e A[med] x faça
início; se x > A[med] então min med + 1; se x < A[med] então max med – 1; med (min + max)/2; fim
se A[med] = x então ...senão ...
T(n) = O(1) + log n · O(1)T(n) = O(log n)
Pesquisa binária: O(log n)Pesquisa seqüencial: O(n)
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 89
maxmin medA[9] =x
fim
maxmin medA[8] < x
min maxmedA[5] < x
A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9] A[10] 2 4 5 8 10 11 13 15 17 20
Exemplo:
x = 17
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 90
max min
fim
maxmin medA[9] >x
maxmin medA[8] < x
min maxmedA[5] < x
Exemplo:
A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9] A[10] 2 4 5 8 10 11 13 15 17 20
x = 16
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 91
Algoritmos de menor complexidade
• Heapsort• Mergesort
É possível provar que este limitante é o melhor possível, isto é, estes algoritmos são ótimos!
• Problema: dados um vetor A[1] ... A[n] e um valor x, verificar se x é um elemento do vetor.
• Qual é o melhor algoritmo?
O(n log n)
Depende!!!Dados ordenados ou não?
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 92
Algoritmos de menor complexidade
• Dados ordenados:- Pesquisa binária: O(log n)
• Dados não-ordenados:- Pesquisa seqüencial: O(n)
- Ordenar + pesquisa binária: O(n log n) + O(log n) = O(n log n)
Pesquisa seqüencial é melhor!
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 93
Algoritmos de menor complexidade
• Variante:Há m elementos a serem testados
• Dados não-ordenadosPesquisa seqüencial: O(m.n)
Ordenar + pesquisa binária: O(n log n) + O(m log n) = O((n + m) log n)
• Hipótese: m n
Agora, a segunda alternativa é a mais eficiente!O(n log n) vs. O(n2)
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 94
Heap
• Tipo de dado:Fila de prioridade
Implementação:Heap
• Conjunto de elementos, cada um com uma prioridadeOperações: Inserir
Obter e eliminar o elemento com maior prioridade
• Exemplo de aplicação: heapsort
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 95
Árvore parcialmente ordenada
• Árvore binária valorada onde os rótulos satisfazem as seguintes propriedades:
1. Rótulos dos nós são elementos com uma prioridade (valor de um elemento).
2. O elemento armazenado em um nó tem prioridade maior ou igual à dos filhos deste nó.
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 96
Árvore parcialmente ordenada
• APO’s são uma boa implementação de filas de prioridade.
DeleteMax: – Substituir a raiz pelo nó mais à direita no nível mais baixo;– Reorganizar a árvore fazendo o elemento da raiz descer
até a posição apropriada.
Inserir:– Criar folha mais à esquerda possível no nível mais baixo e
subir até encontrar a posição apropriada.
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 97
Árvore parcialmente ordenada balanceada
• As folhas estão no máximo em dois níveis diferentes .• As folhas no nível mais baixo estão o mais à esquerda possível.
n nós caminho da raiz tem comprimento menor ou igual a log2 n
Heap: implementação de uma APO balanceada
16
7
18
18
9179
3 5
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 98
Heap
• Vetor A com interpretação especial para índice dos elementos
• Elementos de APOB aparecem nível a nível em A, começando da raiz, e dentro de um mesmo nível da esquerda para a direita
– O filho à esquerda do nó armazenado em A[i] será armazenado em A[2i] e seu filho à direita em A[2i+1]
18 18 7916 1 9 573
1 2 543 6 7 1098
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 99
Heap
4
1 3
2 16
8 7
9 10
14
A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9] A[10] 4 1 3 2 16 9 10 14 8 7
Construção da árvore
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 100
Heap
type IntArray = array [1...max] of integer;
procedure swap (var A: intarray;i, j: integer);var temp: integer; início temp A[i];
A[i] A[j]; A[j] temp;
fim
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 101
Heapprocedure bubbleUp (var A: intarray;i: integer);início se i > 1 AND A[i] > A[i/2] então
inícioswap (A,i,i/2);bubbleUp (A,i/2)
fimfim
procedure insert (var A: intarray; x,n: integer);início
n n + 1;A[n] x;bubbleUp (A,n)
fim T(n) = O(log n)
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 102
Heap
procedure bubbleDown (var A: intarray;i,n: integer);var filho: integer;início filho 2*i;
se filho < n então se A[filho+1] > A[filho] então filho filho + 1;se filho n então
se A[i] < A[filho] então início
swap (A,i,filho); bubbleDown (A,filho,n)
fimfim
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 103
Heap
procedure deletemax (var A: intarray; Var n: integer);início
swap (A, 1, n);n n – 1;
bubbleDown (A, 1, n)fim T(n) = O(log n)
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 104
para i = 1 até n façainsert(ai);
para i = 1 até n façadeletemax
Heapsort
• Ordenar um vetor A[1..n] em duas fases:
1. Dar ao vetor a propriedade de ser uma APO balanceada (heap).2. Repetidamente, selecionar o maior item do heap até que o vetor
fique ordenado
heap1 i (i + 1) n
(n-i) maiores elementos já ordenados
T(n) = O(n log n)O(log n)
O(log n)
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 105
Heapsort
A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9] A[10] 4 1 3 2 16 9 10 14 8 7
Construção do vetor (primeira parte, usando insert)
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 106
Heapsort
4
A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9] A[10] 4 1 3 2 16 9 10 14 8 7
Construção do vetor (primeira parte, usando insert)
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 107
Heapsort
4
1
A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9] A[10] 4 1 3 2 16 9 10 14 8 7
Construção do vetor (primeira parte, usando insert)
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 108
Heapsort
4
1 3
A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9] A[10] 4 1 3 2 16 9 10 14 8 7
Construção do vetor (primeira parte, usando insert)
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 109
Heapsort
4
1 3
2
A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9] A[10] 4 1 3 2 16 9 10 14 8 7
Construção do vetor (primeira parte, usando insert)
Atenção!!!
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 110
Heapsort
4
1 3
2 16
A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9] A[10] 4 1 3 2 16 9 10 14 8 7
Construção do vetor (primeira parte, usando insert)
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 111
Heapsort
4
1 3
2 16
A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9] A[10] 4 1 3 2 16 9 10 14 8 7
Construção do vetor (primeira parte, usando insert)
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 112
Heapsort
16
4 3
2 1
A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9] A[10]16 4 3 2 1 9 10 14 8 7
Construção do vetor (primeira parte, usando insert)
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 113
Heapsort
16
4 3
2 1 9
A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9] A[10] 16 4 3 2 1 9 10 14 8 7
Construção do vetor (primeira parte, usando insert)
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 114
Heapsort
16
4 3
2 1 9
A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9] A[10] 16 4 3 2 1 9 10 14 8 7
Construção do vetor (primeira parte, usando insert)
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 115
Heapsort
16
4 9
2 1 3
A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9] A[10] 16 4 9 2 1 3 10 14 8 7
Construção do vetor (primeira parte, usando insert)
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 116
Heapsort
16
4 9
2 1 3 10
A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9] A[10] 16 4 9 2 1 3 10 14 8 7
Construção do vetor (primeira parte, usando insert)
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 117
Heapsort
16
4 9
2 1 3 10
A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9] A[10] 16 4 9 2 1 3 10 14 8 7
Construção do vetor (primeira parte, usando insert)
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 118
Heapsort
16
4 10
2 1 3 9
A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9] A[10] 16 4 10 2 1 3 9 14 8 7
Construção do vetor (primeira parte, usando insert)
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 119
Heapsort
16
4 10
2 1 3 9
14
A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9] A[10] 16 4 10 2 1 3 9 14 8 7
Construção do vetor (primeira parte, usando insert)
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 120
Heapsort
16
4 10
2 1 3 9
14
A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9] A[10] 16 4 10 2 1 3 9 14 8 7
Construção do vetor (primeira parte, usando insert)
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 121
Heapsort
16
14 10
4 1 3 9
2
A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9] A[10] 16 14 10 4 1 3 9 2 8 7
Construção do vetor (primeira parte, usando insert)
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 122
Heapsort
16
14 10
4 1
8
3 9
2
A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9] A[10] 16 14 10 4 1 3 9 2 8 7
Construção do vetor (primeira parte, usando insert)
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 123
Heapsort
16
14 10
4 1
8
3 9
2
A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9] A[10] 16 14 10 4 1 3 9 2 8 7
Construção do vetor (primeira parte, usando insert)
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 124
Heapsort
16
14 10
8 1
4
3 9
2
A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9] A[10] 16 14 10 8 1 3 9 2 4 7
Construção do vetor (primeira parte, usando insert)
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 125
Heapsort
16
14 10
8 1
4 7
3 9
2
A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9] A[10] 16 14 10 8 1 3 9 2 4 7
Construção do vetor (primeira parte, usando insert)
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 126
Heapsort
16
14 10
8 1
4 7
3 9
2
A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9] A[10] 16 14 10 8 1 3 9 2 4 7
Construção do vetor (primeira parte, usando insert)
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 127
Heapsort
16
14 10
8 7
4 1
3 9
2
A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9] A[10] 16 14 10 8 7 3 9 2 4 1
Construção do vetor (primeira parte, usando insert)
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 128
9
2
10
3
14
8
1
4 7
Heapsort
9
2
10
3
16
14
4
8 7
1
Ordenação do vetor (segunda parte, usando deleteMax)
A[1] A[2] A[3] A[4] A[5] A[6] A[7] A[8] A[9] A[10] 16
9
2
10
3
14
8
1
4 7
14
1
2
9
3
10
8
4 7
9874321
1
2
9
3
10
8
4 7
10
1
3
2
9
8
4 7
Árvore após extrair a raizÁrvore antes de extrair a raiz
1
3
2
9
8
4 7 1
3
8
7
4 21
3
8
7
4 2
3
7
4
1 2
3
7
4
1 2
3
4
2
1
3
4
2
1
1
3
21
3
2
2
1
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 129
Heapsort
procedure heapsort (var A: intarray; n: integer);var i: integer;início heapify (A, n);
i n;enquanto i > 1 faça
deletemax (A,i);fim
O(n)
swap de A[1] e A[i];diminui n n -1
O (n log n)
heapify considera o vetor A após a leitura e o transforma em um heap,começando do nível mais baixo e subindo nível a nível.
Implementação melhor: em vez de montar um heap elemento a elemento, ler o vetor e transformá-lo após a leitura.
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 130
Heapsort
procedure heapify (var A: intarray; n: integer);var i: integer;início
para i = n/2 downto 1 façabubbleDown (A,i,n);
fim
n/2 chamadas a BubbleDown O(n log n) ou menos?
Nada a fazer no nível mais baixo, começar um nível acima: apenas os n/2 primeiros elementos podem ser afetados, pois são os que têm filhos.
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 131
Heapsort
n/4 + 1
n/2 + 1
n/2
n
• 2a metade: 0 chamada• 2º quarto: 1 chamada• 2º oitavo: 2 chamadas
4
2 3
1
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 132
Heapsort
• Zona i:
• No máximo i chamadas a bubbleDown para cada elemento na zona i
• Número de elementos na zona i:
n/8 n/4 n/2 n... 2 1 0
zona 2 zona 1
122 ii
njn
12 i
n
zona 0 4
2 3
1
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 133
Heapsort
• Zona de maior índice: log2n
• Altura: log2n
• A[1] é o único elemento na zona log2n de maior índice
nn
in
nini
ni
ii
ii
n
ii
n
ii
2.2
22
22.
?2
.
1
11
log
11
log
11
2
2
4
2 3
1
Heapify O(n)
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 134
Heapsort
1161
81
41
21
161
161
161
161
81
81
81
41
41
21
21
161
81
41
41
161
81
2
1 2i
i
i
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 135
Algoritmos polinomiais
• Diz-se que um algoritmo é polinomial quando sua complexidade de pior caso (T(n)) é limitada por um polinômio em função do tamanho da entrada (n).
• Considera-se um determinado tipo de problema como bem resolvido em termos algorítmicos quando se dispõe de um bom algoritmo para sua solução.
• Diz-se que um bom algoritmo é aquele cuja complexidade é polinomial
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 136
Algoritmos polinomiais
• A taxa de crescimento de qualquer algoritmo polinomial é menor do que a taxa de crescimento dos algoritmos não polinomiais.
P(n): polinômio em n
0)(lim!
)(lim2
)(lim nnnnn n
nPnnPnP
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 137
Algoritmos polinomiais
• Para n suficientemente grande, um algoritmo polinomial é sempre mais rápido do que um algoritmo não-polinomial.
T1(n) = na T2(n) = an
aa
anT
nT
nn
nTnT
n
n
nn
a
a
nn
1
2
2
1
1
lim)(
)1(lim
1)1(lim)(
)1(lim
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 138
Algoritmos polinomiais
n 10 100 1000n log n 33 664 9966n3 1000 106 109
2n 1024 1.27 x 1030 1.05 x 10 301
n log n 2099 1.93 x 1013 7.89 x 10 29
n! 3628800 10158 4 x 10 2567
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 139
Algoritmos polinomiais
P = {polinômios} é uma constante
P1, P2 P · P1 P P1 + P2 P P1 · P2 P
• Propriedade de fechamento:
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 140
Algoritmos polinomiais
• Melhor utilização de avanços tecnológicos
• n1: maior tamanho de problema que pode ser resolvido em um computador disponível hoje, usando um algoritmo de complexidade T(n), em determinado tempo de processamento pré-fixado.
• n10: mesma definição, em um computador 10 vezes mais rápido.
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 141
Algoritmos polinomiais
T(n10) = 10 · T(n1)
n 1012 1013
n log n 0.948 x 1011 0.87 x 1012 n3 104 2.15 x 104
2n 40 43nlog n 79 95n! 14 15
(n10)3 = 10 (n1 )3
n10 = · n13 10
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 142
Algoritmos polinomiais
• Problemas que podem ser resolvidos por algoritmos polinomiais classe
• Há muitos problemas para os quais não se conhece algoritmos polinomiais
Não existem?
Ainda não foram encontrados?
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 143
Teoria da complexidade
• Problemas NP-completos
• O que fazer quando não se conhece um algoritmo polinomial para um problema?
Desenvolver um algoritmo não-polinomial.Procurar algoritmos aproximados de complexidade polinomial.
decisão Problemas avaliação
otimização
“sim”“não”
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 144
Teoria da complexidade
NP
P-SPACE
“fáceis” (algoritmos polinomiais)
“NP-difíceis” /“NP-árduos”
P NP ?
NP-Completos
PP
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 145
Algoritmos pseudopolinomiais
A[1] ... A[n]: números inteiros [a,b]
FASE 1: Colocar cada elemento A[i] na caixa apropriada (ou seja, a caixa rotulada com i)
FASE 2: Percorrer as caixas na ordem por ordem crescente de rótulo, retirando os elementos
Exemplo: ordenação pelo método das caixas
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 146
Algoritmos pseudopolinomiais
para j = a até b façan(j) 0;
para i = 1 até n façan[a[i]] n[a[i]] + 1;
k 0;para j = a até b faça início
enquanto n[j] 0 faça início n[j] = n[j] – 1; k k + 1; a[k] j; fim
fim
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 147
Algoritmos pseudopolinomiais
T(n) = (b – a + 1) · O (1) + n · O (1) + O (1) + (b – a + 1) · O (n) · O (1) = O(n · (b – a))
Não, cuidado!!!
para : b – a + 1enquanto: n + (b – a + 1)n[j] : k : na[k] :
T(n) = O(b – a + n)
Não é um algoritmo polinomial, pois T(n) não é um polinômio apenas no tamanho da entrada.
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 148
Algoritmos pseudopolinomiais
• Selecionar dentre n objetos aqueles que serão levados em uma mochila de capacidade (peso máximo) limitada. j = 1, ..., n objetoscj “lucro”aj “peso”b “peso máximo”
Hipótese: aj b j
Exemplo: problema da mochila
njx
bxa
xc
j
n
jjj
j
n
jj
,...,1,1,01
1
: a sujeito
maximizar
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 149
Problema da mochila
• Decomposição do problema em estágios.
• Em vez de considerar uma solução (x1,x2,...,xn) completa de uma só vez, visualizar o problema como se as decisões fossem tomadas para um item de cada vez.
• Após k decisões, terão sido determinados quais dos primeiros k itens devem ser selecionados e, conseqüentemente, terão sido determinados os valores das variáveis x1,x2,...,xk.
• Neste ponto, o valor acumulado é
• O volume acumulado é
k
jj xa1j
j
k
jj xc
1
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 150
Problema da mochila
• Estágio:cada variável do problema
• Estado: volume total ocupado com as decisões já tomadas
• Decisão: selecionar ou não um item (isto é, fazer xk=1)
• Custo da decisão de selecionar o item k: aumento de ck unidades no lucro parcial acumulado
• Efeito da decisão de selecionar o item k: aumento do volume ocupado (estado) em ak unidades
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 151
Problema da mochila• Definição:
yk(u) = lucro máximo que pode ser obtido com volume total igual a u e usando apenas itens do conjunto {1,...,k}
• Quanto vale y0(0)?– y0(0) = 0 (sem objetos selecionados, o peso e o lucro são nulos)
• Definir yk(u) = - se é impossível obter um volume total igual a u apenas com itens dentre os do conjunto {1,...,k}.
• Quanto valem y0(u) e yk(0)? – y0(u) = - para u > 0 (impossível acumular peso sem itens)– yk(0) = 0 para k = 1,2,...,n (nenhum item selecionado)
• Calcular yk(u) para k = 1,...,n e u = 0,...b, a partir de y0(0).
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 152
Problema da mochila
• yk(u) = lucro máximo que pode ser obtido com volume total igual a u e usando apenas itens do conjunto {1,...,k}
• Calcular yk(u) para k = 1,...,n e u = 0,...b:
• Interpretação: há duas alternativas para se obter yk(u), dependendo do item k ser selecionado ou não– yk(u) = yk-1(u), se o item k não é usado– yk(u) = yk-1(u-ak)+ck, se o item k é usado
nkbucauyuyb;ku
kuuy
kkkk
k
,...,1;,...,0,)(),(max0,...,1,
0;0,0)(
11
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 153
Problema da mochila
• Observar que o lucro associado ao estado resultante de uma decisão depende apenas do valor desta decisão e do estado atual, mas não depende da forma como este último foi atingido.
nkbucauyuyb;ku
kuuy
kkkk
k
,...,1;,...,0,)(),(max0,...,1,
0;0,0)(
11
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 154
Problema da mochila
5,...,1},1,0{4233 :a sujeito
3223max
54321
54321
jxxxxxx
xxxxx
j
y5(4) =
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 155
Problema da mochila
5,...,1},1,0{4233 :a sujeito
3223max
54321
54321
jxxxxxx
xxxxx
j
5,...,1},1,0{233 :a sujeito
3223max
54321
54321
jxbxxxxx
xxxxx
j
y5(b) =
Valor ótimo = maxb=0,...,4 {y5(b)}
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 156
Problema da mochila
y0(4) y5(4)
y0(3) y5(3)
y0(2) y5(2)
y0(1) y5(1)
y0(0) y1(0) y2(0) y3(0) y4(0) y5(0)
u = 4
u = 3
u = 2
u = 1
u = 0
k = 0 k = 1 k = 2 k = 3 k = 4 k = 5
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 157
Problema da mochila
y0(4)
y0(3)
y0(2)
y0(1)
0 0 0 0 0 0
u = 4
u = 3
u = 2
u = 1
u = 0
k = 0 k = 1 k = 2 k = 3 k = 4 k = 5
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 158
Problema da mochila
-
-
-
-
0 0 0 0 0 0
u = 4
u = 3
u = 2
u = 1
u = 0
k = 0 k = 1 k = 2 k = 3 k = 4 k = 5
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 159
Problema da mochila
- ?
- ?
- ?
- ?
0 ?
u = 4
u = 3
u = 2
u = 1
u = 0
k = 0 k = 1 k = 2 k = 3 k = 4 k = 5
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 160
Problema da mochila
-
-
- -
- -
0 0
u = 4
u = 3
u = 2
u = 1
u = 0
k = 0 k = 1 k = 2 k = 3 k = 4 k = 5
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 161
Problema da mochila
-
- 3
- -
- -
0 0
u = 4
u = 3
u = 2
u = 1
u = 0
k = 0 k = 1 k = 2 k = 3 k = 4 k = 5
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 162
Problema da mochila
- -
- 3
- -
- -
0 0
u = 4
u = 3
u = 2
u = 1
u = 0
k = 0 k = 1 k = 2 k = 3 k = 4 k = 5
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 163
Problema da mochila
- -
- 3
- -
- -
0 0
u = 4
u = 3
u = 2
u = 1
u = 0
k = 0 k = 1 k = 2 k = 3 k = 4 k = 5
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 164
Problema da mochila
- - ?
- 3 ?
- - ?
- - ?
0 0 ?
u = 4
u = 3
u = 2
u = 1
u = 0
k = 0 k = 1 k = 2 k = 3 k = 4 k = 5
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 165
Problema da mochila
- -
- 3
- -
- -
0 0 0
u = 4
u = 3
u = 2
u = 1
u = 0
k = 0 k = 1 k = 2 k = 3 k = 4 k = 5
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 166
Problema da mochila
- -
- 3
- - -
- - -
0 0 0
u = 4
u = 3
u = 2
u = 1
u = 0
k = 0 k = 1 k = 2 k = 3 k = 4 k = 5
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 167
Problema da mochila
- -
- 3
- - -
- - -
0 0 0
2
u = 4
u = 3
u = 2
u = 1
u = 0
k = 0 k = 1 k = 2 k = 3 k = 4 k = 5
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 168
Problema da mochila
- -
- 3
- - -
- - -
0 0 0
0
2
u = 4
u = 3
u = 2
u = 1
u = 0
k = 0 k = 1 k = 2 k = 3 k = 4 k = 5
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 169
Problema da mochila
- -
- 3 3
- - -
- - -
0 0 0
0
2
u = 4
u = 3
u = 2
u = 1
u = 0
k = 0 k = 1 k = 2 k = 3 k = 4 k = 5
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 170
Problema da mochila
- - -
- 3 3
- - -
- - -
0 0 0
u = 4
u = 3
u = 2
u = 1
u = 0
k = 0 k = 1 k = 2 k = 3 k = 4 k = 5
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 171
Problema da mochila
- - -
- 3 3
- - -
- - -
0 0 0
u = 4
u = 3
u = 2
u = 1
u = 0
k = 0 k = 1 k = 2 k = 3 k = 4 k = 5
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 172
Problema da mochila
- - - ?
- 3 3 ?
- - - ?
- - - ?
0 0 0 ?
u = 4
u = 3
u = 2
u = 1
u = 0
k = 0 k = 1 k = 2 k = 3 k = 4 k = 5
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 173
Problema da mochila
- - -
- 3 3
- - -
- - -
0 0 0 0
u = 4
u = 3
u = 2
u = 1
u = 0
k = 0 k = 1 k = 2 k = 3 k = 4 k = 5
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 174
Problema da mochila
- - -
- 3 3
- - -
- - - 2
0 0 0 0
u = 4
u = 3
u = 2
u = 1
u = 0
k = 0 k = 1 k = 2 k = 3 k = 4 k = 5
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 175
Problema da mochila
- - -
- 3 3
- - - -
- - - 2
0 0 0 0
u = 4
u = 3
u = 2
u = 1
u = 0
k = 0 k = 1 k = 2 k = 3 k = 4 k = 5
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 176
Problema da mochila
- - -
- 3 3
- - - -
- - - 2
0 0 0 0
2
u = 4
u = 3
u = 2
u = 1
u = 0
k = 0 k = 1 k = 2 k = 3 k = 4 k = 5
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 177
Problema da mochila
- - -
- 3 3
- - - -
- - - 2
0 0 0 0
2
0
u = 4
u = 3
u = 2
u = 1
u = 0
k = 0 k = 1 k = 2 k = 3 k = 4 k = 5
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 178
Problema da mochila
- - -
- 3 3 3
- - - -
- - - 2
0 0 0 0
2
0
u = 4
u = 3
u = 2
u = 1
u = 0
k = 0 k = 1 k = 2 k = 3 k = 4 k = 5
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 179
Problema da mochila
- - - 5
- 3 3 3
- - - -
- - - 2
0 0 0 0
2
u = 4
u = 3
u = 2
u = 1
u = 0
k = 0 k = 1 k = 2 k = 3 k = 4 k = 5
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 180
Problema da mochila
- - - 5
- 3 3 3
- - - -
- - - 2
0 0 0 0
u = 4
u = 3
u = 2
u = 1
u = 0
k = 0 k = 1 k = 2 k = 3 k = 4 k = 5
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 181
Problema da mochila
- - - 5 ?
- 3 3 3 ?
- - - - ?
- - - 2 ?
0 0 0 0 ?
u = 4
u = 3
u = 2
u = 1
u = 0
k = 0 k = 1 k = 2 k = 3 k = 4 k = 5
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 182
Problema da mochila
- - - 5
- 3 3 3
- - - -
- - - 2
0 0 0 0 0
u = 4
u = 3
u = 2
u = 1
u = 0
k = 0 k = 1 k = 2 k = 3 k = 4 k = 5
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 183
Problema da mochila
- - - 5
- 3 3 3
- - - -
- - - 2
0 0 0 0 01
0
u = 4
u = 3
u = 2
u = 1
u = 0
k = 0 k = 1 k = 2 k = 3 k = 4 k = 5
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 184
Problema da mochila
- - - 5
- 3 3 3
- - - -
- - - 2 2
0 0 0 0 0
u = 4
u = 3
u = 2
u = 1
u = 0
k = 0 k = 1 k = 2 k = 3 k = 4 k = 5
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 185
Problema da mochila
- - - 5
- 3 3 3
- - - -
- - - 2 2
0 0 0 0 0
1
u = 4
u = 3
u = 2
u = 1
u = 0
k = 0 k = 1 k = 2 k = 3 k = 4 k = 5
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 186
Problema da mochila
- - - 5
- 3 3 3
- - - - 3
- - - 2 2
0 0 0 0 0
u = 4
u = 3
u = 2
u = 1
u = 0
k = 0 k = 1 k = 2 k = 3 k = 4 k = 5
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 187
Problema da mochila
- - - 5
- 3 3 3 3
- - - - 3
- - - 2 2
0 0 0 0 0
0
u = 4
u = 3
u = 2
u = 1
u = 0
k = 0 k = 1 k = 2 k = 3 k = 4 k = 5
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 188
Problema da mochila
- - - 5
- 3 3 3 3
- - - - 3
- - - 2 2
0 0 0 0 0
u = 4
u = 3
u = 2
u = 1
u = 0
k = 0 k = 1 k = 2 k = 3 k = 4 k = 5
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 189
Problema da mochila
- - - 5
- 3 3 3 3
- - - - 3
- - - 2 2
0 0 0 0 0
1
u = 4
u = 3
u = 2
u = 1
u = 0
k = 0 k = 1 k = 2 k = 3 k = 4 k = 5
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 190
Problema da mochila
- - - 5
- 3 3 3 3
- - - - 3
- - - 2 2
0 0 0 0 0
1
0u = 4
u = 3
u = 2
u = 1
u = 0
k = 0 k = 1 k = 2 k = 3 k = 4 k = 5
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 191
Problema da mochila
- - - 5 5
- 3 3 3 3
- - - - 3
- - - 2 2
0 0 0 0 0
1
0u = 4
u = 3
u = 2
u = 1
u = 0
k = 0 k = 1 k = 2 k = 3 k = 4 k = 5
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 192
Problema da mochila
- - - 5 5
- 3 3 3 3
- - - - 3
- - - 2 2
0 0 0 0 0
u = 4
u = 3
u = 2
u = 1
u = 0
k = 0 k = 1 k = 2 k = 3 k = 4 k = 5
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 193
Problema da mochila
- - - 5 5 ?
- 3 3 3 3 ?
- - - - 3 ?
- - - 2 2 ?
0 0 0 0 0 ?
u = 4
u = 3
u = 2
u = 1
u = 0
k = 0 k = 1 k = 2 k = 3 k = 4 k = 5
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 194
Problema da mochila
- - - 5 5
- 3 3 3 3
- - - - 3
- - - 2 2
0 0 0 0 0 0
u = 4
u = 3
u = 2
u = 1
u = 0
k = 0 k = 1 k = 2 k = 3 k = 4 k = 5
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 195
Problema da mochila
- - - 5 5
- 3 3 3 3
- - - - 3
- - - 2 2
0 0 0 0 0 0
0
u = 4
u = 3
u = 2
u = 1
u = 0
k = 0 k = 1 k = 2 k = 3 k = 4 k = 5
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 196
Problema da mochila
- - - 5 5
- 3 3 3 3
- - - - 3
- - - 2 2 2
0 0 0 0 0 0
0
u = 4
u = 3
u = 2
u = 1
u = 0
k = 0 k = 1 k = 2 k = 3 k = 4 k = 5
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 197
Problema da mochila
- - - 5 5
- 3 3 3 3
- - - - 3
- - - 2 2 2
0 0 0 0 0 0
u = 4
u = 3
u = 2
u = 1
u = 0
k = 0 k = 1 k = 2 k = 3 k = 4 k = 5
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 198
Problema da mochila
- - - 5 5
- 3 3 3 3
- - - - 3
- - - 2 2 2
0 0 0 0 0 0
0
3
u = 4
u = 3
u = 2
u = 1
u = 0
k = 0 k = 1 k = 2 k = 3 k = 4 k = 5
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 199
Problema da mochila
- - - 5 5
- 3 3 3 3
- - - - 3 3
- - - 2 2 2
0 0 0 0 0 0
0
3
u = 4
u = 3
u = 2
u = 1
u = 0
k = 0 k = 1 k = 2 k = 3 k = 4 k = 5
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 200
Problema da mochila
- - - 5 5
- 3 3 3 3
- - - - 3 3
- - - 2 2 2
0 0 0 0 0 0
u = 4
u = 3
u = 2
u = 1
u = 0
k = 0 k = 1 k = 2 k = 3 k = 4 k = 5
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 201
Problema da mochila
- - - 5 5
- 3 3 3 3
- - - - 3 3
- - - 2 2 2
0 0 0 0 0 0
0
3
u = 4
u = 3
u = 2
u = 1
u = 0
k = 0 k = 1 k = 2 k = 3 k = 4 k = 5
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 202
Problema da mochila
- - - 5 5
- 3 3 3 3 5
- - - - 3 3
- - - 2 2 2
0 0 0 0 0 0
0
3
u = 4
u = 3
u = 2
u = 1
u = 0
k = 0 k = 1 k = 2 k = 3 k = 4 k = 5
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 203
Problema da mochila
- - - 5 5
- 3 3 3 3 5
- - - - 3 3
- - - 2 2 2
0 0 0 0 0 0
u = 4
u = 3
u = 2
u = 1
u = 0
k = 0 k = 1 k = 2 k = 3 k = 4 k = 5
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 204
Problema da mochila
- - - 5 5
- 3 3 3 3 5
- - - - 3 3
- - - 2 2 2
0 0 0 0 0 0
0
3
u = 4
u = 3
u = 2
u = 1
u = 0
k = 0 k = 1 k = 2 k = 3 k = 4 k = 5
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 205
Problema da mochila
- - - 5 5 6
- 3 3 3 3 5
- - - - 3 3
- - - 2 2 2
0 0 0 0 0 0
0
3
u = 4
u = 3
u = 2
u = 1
u = 0
k = 0 k = 1 k = 2 k = 3 k = 4 k = 5
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 206
Problema da mochila
- - - 5 5 6
- 3 3 3 3 5
- - - - 3 3
- - - 2 2 2
0 0 0 0 0 0
u = 4
u = 3
u = 2
u = 1
u = 0
k = 0 k = 1 k = 2 k = 3 k = 4 k = 5
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 207
Problema da mochila
- - - 5 5 6
- 3 3 3 3 5
- - - - 3 3
- - - 2 2 2
0 0 0 0 0 0
u = 4
u = 3
u = 2
u = 1
u = 0
k = 0 k = 1 k = 2 k = 3 k = 4 k = 5
y5(4) = 6
y5(3) = 5
y5(2) = 3
y5(1) = 2
y5(0) = 0
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 208
Problema da mochila
- - - 5 5 6
- 3 3 3 3 5
- - - - 3 3
- - - 2 2 2
0 0 0 0 0 0
u = 4
u = 3
u = 2
u = 1
u = 0
k = 0 k = 1 k = 2 k = 3 k = 4 k = 5
y5(4) = 6
y5(3) = 5
y5(2) = 3
y5(1) = 2
y5(0) = 0
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 209
Problema da mochila
- - - 5 5 6
- 3 3 3 3 5
- - - - 3 3
- - - 2 2 2
0 0 0 0 0 0
u = 4
u = 3
u = 2
u = 1
u = 0
k = 0 k = 1 k = 2 k = 3 k = 4 k = 5
y5(4) = 6
y5(3) = 5
y5(2) = 3
y5(1) = 2
y5(0) = 0
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 210
Problema da mochila
- - - 5 5 6
- 3 3 3 3 5
- - - - 3 3
- - - 2 2 2
0 0 0 0 0 0
u = 4
u = 3
u = 2
u = 1
u = 0
k = 0 k = 1 k = 2 k = 3 k = 4 k = 5
y5(4) = 6
y5(3) = 5
y5(2) = 3
y5(1) = 2
y5(0) = 0
x5=1
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 211
Problema da mochila
- - - 5 5 6
- 3 3 3 3 5
- - - - 3 3
- - - 2 2 2
0 0 0 0 0 0
u = 4
u = 3
u = 2
u = 1
u = 0
k = 0 k = 1 k = 2 k = 3 k = 4 k = 5
y5(4) = 6
y5(3) = 5
y5(2) = 3
y5(1) = 2
y5(0) = 0
x5=1x4=1
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 212
Problema da mochila
- - - 5 5 6
- 3 3 3 3 5
- - - - 3 3
- - - 2 2 2
0 0 0 0 0 0
u = 4
u = 3
u = 2
u = 1
u = 0
k = 0 k = 1 k = 2 k = 3 k = 4 k = 5
y5(4) = 6
y5(3) = 5
y5(2) = 3
y5(1) = 2
y5(0) = 0
x5=1x4=1x3=1
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 213
Problema da mochila
- - - 5 5 6
- 3 3 3 3 5
- - - - 3 3
- - - 2 2 2
0 0 0 0 0 0
u = 4
u = 3
u = 2
u = 1
u = 0
k = 0 k = 1 k = 2 k = 3 k = 4 k = 5
y5(4) = 6
y5(3) = 5
y5(2) = 3
y5(1) = 2
y5(0) = 0
x5=1x4=1x3=1x2=0
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 214
Problema da mochila
- - - 5 5 6
- 3 3 3 3 5
- - - - 3 3
- - - 2 2 2
0 0 0 0 0 0
u = 4
u = 3
u = 2
u = 1
u = 0
k = 0 k = 1 k = 2 k = 3 k = 4 k = 5
y5(4) = 6
y5(3) = 5
y5(2) = 3
y5(1) = 2
y5(0) = 0
x5=1x4=1x3=1x2=0x1=0
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 215
Problema da mochila
• Os estados em verde e as transições possíveis (arcos com setas) definem um grafo multiestágio para a aplicação da recursão de programação dinâmica.
• Número de operações (tempo de processamento) diretamente proporcional ao produto do tamanho da mochila pelo número de variáveis (preencher inteiramente a matriz de dimensões (b+1)x(n+1)): aplicabilidade limitada aos valores de n e de b
• Caso seja possível levar múltiplas cópias de cada item, aumenta o número de decisões e a complexidade do problema.
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 216
Algoritmos pseudopolinomiais
• Calcular:
yj(u): lucro máximo que pode ser obtido carregando-se um peso igual a u usando apenas objetos do conjunto {1,..., j}
• Recursão:
yj-1(k)
yj(k) = max
yj-1(k-aj) + cj
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 217
Algoritmos pseudopolinomiais
y(0,0) 0;
para k = 1 até b faça y(k,0) - ;
para j = 1 até n façainício
para k = 0 até aj–1 faça y(k,j) y(k,j-1);para k = aj até b faça y(k,j) max {y(k,j-1),f(k-aj,j-1) + cj}
fim
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 218
Algoritmos pseudopolinomiais
T(n) = O (b) + n · O (b)T(n) = O (n · b) Tamanho da entrada
Valor do maior dado na entrada
Diz-se que um algoritmo é pseudopolinomial se sua complexidade de pior caso é um polinômio notamanho da entrada e no valor do maior dado de entrada
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 219
Caixeiro viajante
• Grafo orientado com n nós
• Distâncias dij
S { 2, 3, ..., n}
k S
C(S,k) = custo ótimo de sair do nó 1, visitar todos as cidades de S uma única vez, terminar na cidade k.
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 220
Caixeiro viajante
• Início: calcular C(S,k) para |S| = 1, k = 2, ..., n
• Cálculo de C(S,k) para |S| > 1: a melhor maneira de sair do nó 1, visitar todos os nós de S e retornar a k é considerar visitar m imediatamente antes de k, para cada m, considerando C(S-{k}, m) calculado anteriormente:
kSm
dmkSCksC mk
,min,
kdkkC 1,
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 221
Caixeiro viajante
• Calcular para todos S de dado tamanho e para cada possível nó m em S.
• Complexidade:
n
n
k
nO
kn
n
2
1
2
1
2
2
nadiçõesn
Sm
ndentrekescolher
n
k
kkk
n
)1(1
1
1
2
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 222
Definições recursivas ou indutivas
• Definição recursiva: uma classe de objetos relacionados é definida em termos dos próprios objetos.
• Uma definição recursiva envolve uma base (em que um ou mais objetos simples/elementares são definidos) e um passo indutivo (em que objetos maiores são definidos em termos dos objetos menores já definidos).
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 223
Definições recursivas ou indutivas
fat(n) = 1 • 2 • ... • nDefinição recursiva:
Base: 1! = 1Indução: n! = n • (n – 1)!
Base
1º uso do passo indutivo
2º uso do passo indutivo
nº uso do passo indutivo
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 224
Definições recursivas ou indutivas
• Expressões aritméticas são naturalmente definidas de forma recursiva:
Base especificar os operandos atômicos (variáveis, etc.)
• Base: variáveis / inteiros/ reais
• Indução: Se E1 e E2 são expressões, então:
(E1 + E2), (E1 – E2), (E1 • E2), (E1 / E2) e (-E1)
também são expressões aritméticas.
+ -• / Operadores binários
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 225
Procedimentos recursivos
• Chamados de seu interior
• Programas recursivos são freqüentemente mais sucintos ou mais fáceis de serem entendidos.
– Base: entrada particular que pode ser resolvida pela base da indução
– Parte Indutiva: chamadas recursivas sucessivas ao próprio procedimento
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 226
function fat (n: integer): integer;início
se n 1 entãofat 1
senãofat n · fat (n-1)
fim
Procedimentos recursivos
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 227
Call fat(1)
return 2 fat(2)
Base: T(1) = O(1)Indução: T(n) = O(1) + T(n-1) n > 1
Procedimentos recursivos
return 6 fat(3)
return 24 fat(4)
return 1
Call fat(2)
Call fat(3)
Call fat(4)
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 228
• É essencial que a indução faça apenas chamadas envolvendo argumentos de menor tamanho e que a base seja sempre necessariamente atingida.
• Base: Se i = n, só existe um elemento a ser ordenado.
• Indução: Se i < n, obter min {ai, ..., an}, trocá-lo com ai e ordenar
recursivamente {ai +1, ... an}
SelectionSort1) Obter menor elemento da cauda do vetor A[i...n]2) Trocá-lo por A[i]3) Ordenar o vetor A[i+1... n]
Procedimentos recursivos
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 229
procedure SelectionSort (var A: intarray; i, n: integer);var j,smaller, temp: integer;início
se i < n entãoinício smaller i; para j i + 1 até n faça se A[j] < A[smaller] então início
smaller j; temp A[smaller]; A[smaller] A[i];
A[i] temp; SelectionSort (A,i+1,n)
fimfim
fim
T(n) = O(1) + O(n) + T(n-1)T(1) = O(1)
Procedimentos recursivos
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 230
• Análise de procedimentos recursivos:
1. Definir Tp(n) = tempo de processamento de P em função do
tamanho n de seus argumentos.
2. Estabelecer uma relação de recorrência que relacione Tp(n) com
outras funções TQ(k) para outros procedimentos Q com
argumentos de tamanho k.
3. Escolher uma noção de tamanho de argumento que garanta que os procedimentos são chamados recursivamente com argumentos progressivamente menores com o avanço da recursão.
Procedimentos recursivos
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 231
• Quando o argumento se torna suficientemente pequeno, não são feitas novas chamadas recursivas: caso base da definição indutiva de Tp(n)
• Enquanto o argumento não se torna suficientemente pequeno, chamadas recursivas podem ocorrer com argumentos menores
• Tp(n) é obtido pelo exame do código
a) call Q tempo de execução TQ(k)
b) avaliar o corpo de P com as técnicas já conhecidas, deixando termos como TQ(k) como incógnitas: duas expressões para o
tempo de P (caso base e parte indutiva)
c) Substituir O(f(n)) por c·f(n) + dd) Resolver a equação de recorrência
Procedimentos recursivos
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 232
procedure SelectionSort (var A: intarray; i, n: integer);var j,smaller, temp: integer;início
se i < n entãoinício smaller i; para j i + 1 até n faça se A[j] < A[smaller] então início
smaller j; temp A[smaller]; A[smaller] A[i];
A[i] temp; SelectionSort (A,i+1,n)
fimfim
fim
Procedimentos recursivos
Base (i = n): apenas um elemento a ordenar
Indução (i < n): obter o menor elemento em A[i...N], colocá-lo em A[i] e ordenar A[i+1... N]
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 233
Procedimentos recursivos
T(1) = O(1) = aT(n) = O(n) + T(n-1) b.n
T(1) = aT(n) = b.n + T(n-1)T(2) = 2b + aT(3) = 3b + 2b + a = 5b + aT(4) = 4b + 5b + a = 9b + aT(n) =
n
k
abk2
.
)(
)1(2
2
2
2
nO
annb
akbn
k
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 234
Procedimentos recursivos
Base: T(1) = O(1)Indução: T(n) = O(1) + T(n-1) n>1
T(1) = aT(n) = b + T(n-1) n>1T(1) = aT(2) = T(1) + bT(3) = T(2) + b = T(1) + 2bT(4) = T(3) + b = T(1) + 3bT(n) = T(1) + (n-1) · b T(n) = a + (n-1)·b = O(n)
Voltando ao cálculo do fatorial:
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 235
Merge sort
235235
• Algoritmo recursivo baseado em listas, utilizando a técnica de divisão-e-conquista.
• Princípio de divisão para conquistar:
– Dividir a lista em duas listas do mesmo tamanho– Ordenar cada uma das duas listas– Fazer o merge das duas listas ordenadas
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 236
Merge sort
236236
1Lista 1
2
7
7
9
2Lista 2
4
7
8
Merge
1
2
2
4
7
7
7
8
9
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 237
Merge sort
237237
Merge
Lista 2
Mergeados recursivamente
Lista 11
2
2
4
…
…
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 238 238238
Merge sort
Callmerge(1 2 7 7 9, 2 4 7 8)
merge(2 7 7 9, 2 4 7 8)merge(7 7 9, 2 4 7 8)
merge(7 7 9, 4 7 8)merge(7 7 9, 7 8)
merge(7 9, 7 8)merge(9, 7 8)
merge(9, 8)merge(9, NIL)
1 (2 2 4 7 7 7 8 9)2 ( 2 4 7 7 7 8 9)
2 (4 7 7 7 8 9)4 (7 7 7 8 9)7 (7 7 8 9)7 (7 8 9)7 (8 9)8 (9)
Return9
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 239
Merge sort
239239
Lista 14 81 124 nil5
Lista 224 282 nil3
24 26 28 30
4 6 8 10 12 14
L4 L24 L8 > L24
L8 > L28
83
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 240 240240
function merge (lista1, lista2: listType) : listTypeinício
se lista1=NIL então merge lista2
senão se lista2=NIL então
merge lista1 senão
se lista1^.elemento lista2^.elemento entãolista1^.next merge(lista1^.next,
lista2)merge lista1
elselista2^.next merge(lista1,
lista2^.next)merge lista2
fim
Merge sorttype cell=record
element : integernext : listType
type listType=^cell
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 241 241241
function split (lista: listType) : listTypeVar second cell: listTypeinício
se lista=NIL então split NIL
senão se lista^.next=NIL então
split NIL senão
second cell list^.next list^.next second cell^.next second cell^.next split(second cell^.next)
split second cellfim
Merge sort
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 242 242242
Mergen=n1+n2
T(n)=?lista1=NIL ou lista1=NIL O(1)T(n)=O(1)+T(n-1) T(n)=O(n) (percorre a lista)
Splitn: tamanho da listalista1=NIL ou lista1^.next=NIL O(1)T(n)=O(1)+T(n-2)T(0)=aT(1)=bT(n)=c + T(n-2)
Complexidade de Merge sort
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 243 243243
T(0) = aT(1) = bT(1) = bT(2) = c + aT(3) = c + bT(4) = c + ( c + a ) = 2c + a T(5) = c + ( c + b ) = 2c + b T(6) = 3c + a T(7) = 3c + b
Complexidade de Merge sort
n par: T(n) = ( n/2 ) · c + an ímpar: T(n) = ( (n-1)/2 ) · c + b
T(n) = O(n)
Chama-se split recursivamente n/2 vezes, cada vez com cálculos O(1)
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 244 244244
program sort (input, output) const max = 100type cell = record elemento: integer next: listTypeend listType=^cell
var A: array [1…max] of integer k, n: integer
list: listType
Merge sort
procedure merge sort (var list: listType)function merge (lista1, lista2: listType): listTypefunction split (list: listType) : listType
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 245 245245
function makeList (i, n: integer) : listType var new cell: listTypeinício
se i > n então makeList NILelse
new(newCell) newCell^.next makeList(i+1, n) newCell^.element A[i] makeList newCell
fim
Merge sort
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 246 246246
procedure printList (list: listType) início
se list = NIL então returnelse
write(list^.element) printList(list^.next)
fim
Merge sort
inícioreadln(n)para k 1 até n faça read(A[k]) list makeList(1, n) mergeSort(list) printList(list)
fim
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 247 247247
procedure mergeSort(var list: listType) var secondList: listTypeinício
se list <> NIL então se list^.next <> NIL então secondList split(list) mergeSort(list)
mergeSort(secondList) list merge(list, secondList)
fim
Merge sort
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 248 248248
list NIL ou list^.next NIL O(1)n: tamanho da lista
base: T(1) = O(1) indução: T(n) = O(1) + O(n) + T(n/2) + T(n/2) + O(n)
T(1) = O(1) = a T(n) = O(n) + 2 · T(n/2) = b · n + 2 · T(n/2)
T(2) = 2a + 2b T(4) = 4a + 8b T(8) = 8a + 24b T(16) = 16a + 64b T(n) = n · a + (n · log2n) · b
Merge sort
T(n)=O(n log n)
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 249 249249
Torres de Hanoi
C
X Y Z
B
A
A B
A
CA
B
A
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 250 250250
Torres de Hanoi
C
X Y Z
B
A
D C
B
A
D
C
B
A
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 251 251251
Torres de Hanoi
• Repetir n passos 1 e 2 abaixo até que os discos estejam corretamente empilhados:1. Mover o menor disco do suporte “corrente” para o seguinte no …2. Fazer o único movimento possível que não envolva o menor disco
C
X Y Z
B
A
D C
B
A
D
C
B
A
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 252 252252
Torres de Hanoi
X Y Z
n-1n-1
nn-1
N N
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 253 253253
hanoi (n, x, y, z) início
mover n discos de x para y usando zx yse n =1 então x ysenão
hanoi(n-1, x, z, y) x y hanoi(n-1, z, y, x)
fim
Torres de Hanoi
T(n) = O(1) + T(n-1)T(n) = 1 + T(n-1)
T(n) = 1 + 2 T(n-1) n > 1T(n) = O(1) n = 1
b
Setembro 2004 Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro 254 254254
Torres de Hanoi
aaaanTnT
anTnT
aaanTnT
anTnT
aanTnT
aanTnT
anTnT
1234
3
123
2
12
22242)(
422)(
2232)(
322)(
222)(
222
12
n
nn
nn
k
j
kj
n
j
jn
OnT
OnT
abnT
a
aTnT
2
)1(122
122
1122
2)1(2
11
11
0
1
2
0
1