Projeto e Análise de Algoritmos
Celso Carneiro Ribeiro
http://www.inf.puc-rio.br/~celso
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
1
Parte 2
Análise de Algoritmos
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
2
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
3
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
4
Motivação
• Modelagem por conjuntos:
D




 
 

  











  

B
 
F
A
E
C
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
5
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
6
Motivação
• Simplificação tratando-se apenas as interseções:
D





 

  
 











  
B
 
F
Considerar apenas as
interseções não-vazias.
A
C
E
D
A






B
Setembro 2004
E

F
C
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
7
Motivação
• Simplificação com a utilização de um grafo de conflitos:
D





 

  
 











  
B
 
F
disciplinas → nós
conflitos → arestas
A
C
E
D
A
A

B
D



C 
B
Setembro 2004

E
E
F

F
C
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
8
Motivação
• Simplificação com a utilização de um grafo de conflitos:
D





 

  
 











  
B
 
F
disciplinas → nós
conflitos → arestas
A
E
D
A
E
C
B
Setembro 2004
C
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
F
9
Modelo de dados
Grafo = [ nós, arestas ]
•
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ó)
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
10
Matriz de incidência
• n nós e m arestas
• Memória utilizada: nm
a b c
g
A
a
D
b
f
B
e
C
Setembro 2004
E
d
c
F
Anxm
1
0

0

1
0

0
d
e f
g
0 0 0 0 1 1
0 0 0 1 0 1
0 0 1 1 1 0

1 0 0 0 0 0
1 1 0 0 0 0

0 1 1 0 0 0
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
A
B
C
D
E
F
11
Matriz de adjacência
• Memória utilizada: n2
A B C
g
A
a
D
b
f
B
e
C
Setembro 2004
E
d
c
F
Bnxn
0
1

1

1
0

0
D
E F
1 1 1 0 0
0 1 0 0 0
1 0 0 0 1

0 0 0 1 0
0 0 1 0 1

0 1 0 1 0
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
12
A
B
C
D
E
F
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.
g
A
a
D
b
f
B
e
C
Setembro 2004
E
d
c
F
F
E
E
C
D
F
D
A
C
B
E
A
B
A
C
A
B
C
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
F
D
13
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
D
A
B
Setembro 2004
E
C
F
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
D
A
B
Setembro 2004
E
C
F
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
D
A
B
Setembro 2004
E
C
F
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
D
A
B
Setembro 2004
E
C
F
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
D
A
B
Setembro 2004
E
C
F
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
D
A
B
Setembro 2004
E
C
F
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
D
A
B
Setembro 2004
E
C
F
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
D
A
B
Setembro 2004
E
C
F
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
D
A
B
Setembro 2004
E
C
F
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
D
A
B
Setembro 2004
E
C
F
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
D
A
B
E
C
F
• 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
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
D
A
C
F
• 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
• Marcar para o segundo dia qualquer combinação de disciplinas
sem conflitos: A, C, D, F, AF, CD, DF
D
A
C
Setembro 2004
F
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
D
A
C
Setembro 2004
F
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
D
A
C
Setembro 2004
F
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
D
A
C
Setembro 2004
F
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
D
A
C
F
• 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
30
Motivação
• Marcar para o segundo dia qualquer combinação de disciplinas
sem conflitos: A, C, D, F, AF, CD, DF
A
C
• 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 A ou C para o terceiro dia e a que sobrar para o quarto
dia:
A
C
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
32
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:
D
A
B
E
C
F
• 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
33
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?
D
A
Sim!
B
E
C
F
• É impossível colorir o grafo de conflitos com menos de três
cores! (por que?)
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
34
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
35
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
36
Motivação
• Subconjunto independente máximo no grafo de conflito?
BDF
D
A
B
Setembro 2004
E
C
F
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
37
Motivação
• Subconjunto independente máximo no grafo de conflito?
BDF
D
A
B
E
C
F
• Eliminar os nós B, D e F do grafo de conflitos.
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
38
Motivação
• Subconjunto independente máximo no grafo de conflito?
BDF
A
E
C
• 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?
CE
A
E
C
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
40
Motivação
• Subconjunto independente máximo no grafo de conflito?
CE
A
E
C
• Eliminar os nós C e E do grafo de conflitos.
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
41
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
42
Motivação
• Subconjunto independente máximo no grafo de conflito?
A
A
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
43
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
44
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:
D
A
B
E
C
F
• 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
45
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
46
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.
Setembro 2004
A
B
C
D
E
F
G
H
I
J
K
L
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
47
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.
Setembro 2004
A
B
C
D
E
F
G
H
I
J
K
L
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
48
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?
A
B
C
D
E
F
G
H
I
J
K
L
Sim: o grafo pode ser
colorido com apenas duas cores.
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?
Esta solução é ótima, ou é
possível colorir este grafo
com menos cores?
A
B
C
D
E
F
G
H
I
J
K
L
Sim: o grafo pode ser
colorido com apenas duas cores
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
50
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
51
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 estruturado
pseudo linguagem
linguagem de programação
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
52
Algoritmo
Passo 0: k  1
Passo 1: alocar o maior número possível de provas no dia k
sem conflito
Passo 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
53
Análise de algoritmos
Objetivos e questões básicas:
• 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?
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
54
Problema do caixeiro viajante
• 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.
n  1!
soluções
2
n  21  80 anos
n  22  1680anos
Setembro 2004
um a solução: 109 segundos
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
55
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
56
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
57
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
58
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
59
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
Setembro 2004
ordenação
1
2
3
4
5
6
n=6
6
5
4
3
2
1
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
60
Exemplo: Ordenação por seleção
A[1]
A[2]
…
A[n]
para i = 1 até n-1 faça
iní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]  temp
fim
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
61
Análise
• Contar como operações as linhas de código, executando-se
atribuições, comparações,…
para :
n  1(total)  1(teste)
sm aller:
1
para :
n  (i  1)  1(total)  1(teste)
se :
n  (i  1)  1
caso m ais favorável
0,
sm aller  j 
n  (i  1)  1, pior caso
tem p: 3(n  1)
n 1
T (n)  n   1  1  3 n  (i  1)  1 3(n  1)
i 1
n 1
T (n)  4n  3  2(n  1)  3 (n  i )
i 1
T ( n)  6n  5 
Setembro 2004
1  (n  1)
(n  1)
2
n 2 11
T ( n) 
 n5
2
Projeto e Análise de Algoritmos - Celso2Carneiro Ribeiro
62
Comparação de dois algoritmos
TA (n)  100n e TB (n)  2n2 milisegundos
20000
15000
n  50 – Algoritmo B
n  50 – Algoritmo A
TB(n)=2n2
TA(n)=100n
10000
5000
0
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)
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
63
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. B
1
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
64
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
65
Notação O
Descrever o tempo de processamento de um programa usando
a notação O, que “esconde” fatores tais como:
• 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.
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
66
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
T (n)  (n  1) 2  T (n)  O(n 2 )
n 2  2n  1  n 2  2n 2  n 2
n 2  2n  1  4n 2
(para n  1)
n0  1, c  4
 n2 

T (n)  O
100


Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
67
Notação O
Constantes e termos de menor grau não importam:
T (n)  ak n k  ak 1n k 1    a2 n 2  a1n  a0
T ( n)  O ( n k )
n0  1 c  ak  ak 1    a1  a0
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
68
Notação O
lim
n 
hn 
 0 g n   hn   O g n 
g n 
 
T n   2 n  n 3  O 2 n
n3
lim n  0 ou n0  10, c  2
n  2
Transitividade :
f n   Og n 
g n   Ohn 
 f (n)  O(h(n))
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
69
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
70
Notação O
n 2 11
T n  
 n4
2
2
 n2 
T n   O  O n 2
 2 
 
 
 O n3
 n3 

O
 100 

O 100n 2

 
O n 7. 5
Limite mais justo:
menor grau
constante = 1
T(n) = O(n2)
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
71
Notação O
O 1
O log n 
O n 
O n log n 
 
O n 
O 2 
O n2
Linear
nlogn
Quadrático
Cúbico
n
Exponencial
 
Setembro 2004
Logarítmico
3
O n!
On
Constante
n
Fatorial

Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
72
Notação O
Expressões na notação O podem freqüentemente ser
adicionadas:
T1 (n)  O f1 n 
T2 (n)  O f 2 n 
Hipótese: f 2 (n)  O f1 n 
T1 (n)  T2 (n)  O f1 n 
Aplicação: programas que podem ser decompostos em duas
partes
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
73
Exemplo 1
Expressões na notação O podem freqüentemente ser
adicionadas:
ler n
para i = 1 até n faça
para j = 1 até n faça
A[i,j]  0
para i=1 até n faça
A[i,i]  1
T1 (n)  O1
 
T2 (n)  O n2
T3 (n)  On
 
T (n)  T1 n   T2 n   T3 n   O n 2
O1  O1  O1  O1  O1
O1    O1  On  n vezes
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
74
Exemplo 2 - Fatorial
Ler n
i2
fact  1
enquanto i ≤ n faça
inicio
fact  fact * i
i  i+1
fim
Escreva fact
Setembro 2004
Linhas:
111 3  3  1 1
i 2
i n
i  n 1
T (n)  5  3(n  1)  3n  1
Instruções:
T n   1  1  1  (n  1)(1  2  2)  1  1
T (n)  5n  1  1  5n
NotaçãoO :
O1  (n  1).O1
 T ( n)  O ( n)
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
75
Análise do tempo de processamento
Tempo de processamento ~ Complexidade
• 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
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
76
Análise do tempo de processamento
para j = 1 até n faça
A[i,j]  0
O(n)
→ n vezes
→ O(1)
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
77
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
n 1
O1   Omax1, n  i O1
i 1
 n 1

 O  ( n  i )   O n 2
 i 1

 
(n  1) vezes

2
O n
On  i   On 
Setembro 2004
 
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
78
Análise do tempo de processamento
• Teste:
Setembro 2004
se <condição> então
<parte_do_então>
senão
<parte_do_senão>
O (max(f(n), g(n))
→ O(1)
→ O(f(n))
se A[i,i]=0 então
para i =1 a n faça
para j = 1 a n faça
A[i,j]  0
senão
para i = 1 a n faça
A[i,i]  0
O(n2)
→ f(n) = n2
→ O(g(n))
→ g(n) = n
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
79
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]  x
i1
enquanto 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
80
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
 
O n2
Setembro 2004
2

T
(
n
)

2
n
n4
 A

2

T
(
n
)

2
n
 1899n  6
 B
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
81
Cálculo de polinômios
Pn x   an x n  an1 x n 1    a1 x  a0
Dado x, calcularPn x 
P  A[0]
para i = 1 até n faça
P  P + A[i] · (xi);
T1(n) = n · O(n) = O(n2)
O(n) mesmo?
P  A[0]
y  y · x;
para i  1 até n faça
P  P + A[i] · y
y  y · x;
T2(n) = n · [O(1)+O(1)] = O(n)
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
82
Método de Horner
Pn x   an x n  an 1 x n 1    a1 x  a0
Dado x, calcular Pn x 
P  A[n]
para i  n-1 até 0 faça
P  A[i] + x * P;
T3(n) = n · O(1) = O(n)
P  an
P  an 1  xan 
P  an  2  xan 1  an x 
 an  2  an 1 x  an x 2
Qual dos três algoritmos é melhor?

P  an 3  x an  2  an 1 x  an x 2

 an 3  an  2 x  an 1 x 2  an x 3

P  a0  a1 x  a2 x 2    an x n
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
83
Ordenação pelo método da bolha
início
chave  1;
enquanto chave=1 faça
iní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
fim
fim
fim
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
84
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
85
Calcular média e elemento mais próximo
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;
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
86
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) +  n  · O(1)
T(n) = O( n )
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
87
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 ...
T(n) = O(1) + log n · O(1)
senão ...
T(n) = O(log n)
Pesquisa seqüencial: O(n)
Pesquisa binária: O(log n)
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
88
Exemplo:
x = 17
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
min
med min
A[5] < x
min
med med
A[8] < xA[9] =x
max
fim
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
89
Exemplo:
x = 16
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
min
med min
A[5] < x
min
max med
med
min
>x
A[8] < A[9]
x
max
fim
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
90
Algoritmos de menor complexidade
• Heapsort
• Mergesort
O(n log n)
É 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?
Depende!!!
Dados ordenados ou não?
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
91
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
92
Algoritmos de menor complexidade
• Variante:
Há m elementos a serem testados
• Dados não-ordenados
Pesquisa 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
93
Heap
• Tipo de dado:
Fila de prioridade
Implementação:
Heap
• Conjunto de elementos, cada um com uma prioridade
Operaçõ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
94
Á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
95
Á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
96
Á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
18
16
18
7
9
3
Setembro 2004
7
5
1
9
Heap: implementação de
uma APO balanceada
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
97
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 16 9 7 1 9 3 7 5
1
Setembro 2004
2
3
4 5 6 7 8 9 10
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
98
Heap
Construção da árvore
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
4
3
1
2
14
Setembro 2004
16
8
9
10
7
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
99
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
100
Heap
procedure bubbleUp (var A: intarray;i: integer);
início
se i > 1 AND A[i] > A[i/2] então
início
swap (A,i,i/2);
bubbleUp (A,i/2)
fim
fim
procedure insert (var A: intarray; x,n: integer);
início
n  n + 1;
A[n]  x;
bubbleUp (A,n)
T(n) = O(log n)
fim
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
101
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)
fim
fim
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
102
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
103
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
1
i (i + 1)
n
heap
(n-i) maiores elementos já ordenados
para i = 1 até n faça
insert(ai);
para i = 1 até n faça
deletemax
Setembro 2004
O(log n)
T(n) = O(n log n)
O(log n)
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
104
Heapsort
Construção do vetor (primeira parte, usando insert)
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
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
105
Heapsort
Construção do vetor (primeira parte, usando insert)
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
4
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
106
Heapsort
Construção do vetor (primeira parte, usando insert)
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
4
1
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
107
Heapsort
Construção do vetor (primeira parte, usando insert)
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
4
1
Setembro 2004
3
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
108
Heapsort
Construção do vetor (primeira parte, usando insert)
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
4
1
3
Atenção!!!
2
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
109
Heapsort
Construção do vetor (primeira parte, usando insert)
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
4
3
1
2
Setembro 2004
16
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
110
Heapsort
Construção do vetor (primeira parte, usando insert)
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
4
3
1
2
Setembro 2004
16
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
111
Heapsort
Construção do vetor (primeira parte, usando insert)
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
16
3
4
2
Setembro 2004
1
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
112
Heapsort
Construção do vetor (primeira parte, usando insert)
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
16
3
4
2
Setembro 2004
1
9
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
113
Heapsort
Construção do vetor (primeira parte, usando insert)
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
16
3
4
2
Setembro 2004
1
9
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
114
Heapsort
Construção do vetor (primeira parte, usando insert)
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
16
9
4
2
Setembro 2004
1
3
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
115
Heapsort
Construção do vetor (primeira parte, usando insert)
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
16
9
4
2
Setembro 2004
1
3
10
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
116
Heapsort
Construção do vetor (primeira parte, usando insert)
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
16
9
4
2
Setembro 2004
1
3
10
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
117
Heapsort
Construção do vetor (primeira parte, usando insert)
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
16
10
4
2
Setembro 2004
1
3
9
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
118
Heapsort
Construção do vetor (primeira parte, usando insert)
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
16
10
4
2
1
3
9
14
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
119
Heapsort
Construção do vetor (primeira parte, usando insert)
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
16
10
4
2
1
3
9
14
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
120
Heapsort
Construção do vetor (primeira parte, usando insert)
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
16
10
14
4
1
3
9
2
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
121
Heapsort
Construção do vetor (primeira parte, usando insert)
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
16
10
14
4
2
Setembro 2004
1
3
9
8
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
122
Heapsort
Construção do vetor (primeira parte, usando insert)
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
16
10
14
4
2
Setembro 2004
1
3
9
8
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
123
Heapsort
Construção do vetor (primeira parte, usando insert)
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
16
10
14
8
2
Setembro 2004
1
3
9
4
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
124
Heapsort
Construção do vetor (primeira parte, usando insert)
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
16
10
14
8
2
Setembro 2004
1
4
3
9
7
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
125
Heapsort
Construção do vetor (primeira parte, usando insert)
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
16
10
14
8
2
Setembro 2004
1
4
3
9
7
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
126
Heapsort
Construção do vetor (primeira parte, usando insert)
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
16
10
14
8
2
Setembro 2004
7
4
3
9
1
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
127
Heapsort
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]
8
9
1
3
4
7
10 14
16
2
4
14
10
82
7
3
9
16
14
8
10
9
73
4
8
144
222
7
277
41
88
1
2
7
4
10
10
9
31
14
7
28
48
9
19
2
2
1
Árvore antes de extrair a raiz
Setembro 2004
4
1
4
3
2
3
10
39
1
77
2
9
1
32
3
1
Árvore após extrair a raiz
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
128
Heapsort
Implementação melhor: em vez de montar um heap elemento a
elemento, ler o vetor e transformá-lo após a leitura.
procedure heapsort (var A: intarray; n: integer);
var i: integer;
início
heapify (A, n);
O(n)
i  n;
O (n log n)
enquanto i > 1 faça
swap de A[1] e A[i];
deletemax (A,i);
fim
diminui n  n -1
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.
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
129
Heapsort
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.
procedure heapify (var A: intarray; n: integer);
var i: integer;
início
para i = n/2 downto 1 faça
bubbleDown (A,i,n);
fim
n/2 chamadas a BubbleDown
O(n log n) ou menos?
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
130
Heapsort
 n/2 
 n/4  + 1
n
 n/2  + 1
•
•
•
2a
metade:
2º quarto:
2º oitavo:
4
0 chamada
1 chamada
2 chamadas
2
3
1
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
131
Heapsort
n/8
...
n/4
 2
zona 2
•
n/2
n
1
0
zona 1
zona 0
Zona i:
4
n
n
 j  i 1
i
2
2
1
•
No máximo i chamadas a bubbleDown para cada elemento
na zona i
•
Número de elementos na zona i:
Setembro 2004
3
2
n
i 1
2
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
132
Heapsort
•
Zona de maior índice: log2n
•
Altura: log2n
•
A[1] é o único elemento na zona log2n de maior índice
log 2 n
n
i. i 1  ?

2
i 1
4
3
2
1
Heapify O(n)
Setembro 2004

n
n
i. i 1   i i 1 

2
i 1
i 1 2
log 2 n
n  i


i
2 i 1 2
n
.2  n
2
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
133
Heapsort

i


i
i 1 2
1  1 1 1 1 1  1 1 1 1 
              
2  4 4   8 8 8   16 16 16 16 
1 1 1 1
     1
2 4 8 16
1 1 1
1
   
4 8 16
2
1 1
1
  
8 16
4

2
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
134
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
135
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
P ( n)
P ( n)
P ( n)
lim n  lim
 lim n  0
n  2
n   n!
n  n
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
136
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
T1 (n  1)
(n  1) a
lim
 lim
1
a
n  T ( n)
n 
n
1
T2 (n  1)
a n 1
lim
 lim n  a
n  T ( n)
n  a
2
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
137
Algoritmos polinomiais
n
n log n
n3
2n
n log n
n!
Setembro 2004
10
33
1000
1024
2099
3628800
100
664
106
1.27 x 1030
1.93 x 1013
10158
1000
9966
109
1.05 x 10 301
7.89 x 10 29
4 x 10 2567
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
138
Algoritmos polinomiais
•
Propriedade de fechamento:
P = {polinômios}
 é uma constante
P1, P2  P
  · P1  P
 P1 + P2  P
 P1 · P2  P
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
139
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
140
Algoritmos polinomiais
T(n10) = 10 · T(n1)
n
n log n
n3
2n
nlog n
n!
Setembro 2004
1012
0.948 x 1011
104
40
79
14
(n10)3 = 10 (n1 )3
n10 = 3 10
· n1
1013
0.87 x 1012
2.15 x 104
43
95
15
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
141
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
142
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.
Problemas
Setembro 2004
decisão
avaliação
otimização
“sim”
“não”
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
143
Teoria da complexidade
“NP-difíceis” /“NP-árduos”
P-SPACE
NP-Completos
NP
PP
P  NP

 ?
“fáceis” (algoritmos polinomiais)
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
144
Algoritmos pseudopolinomiais
Exemplo: ordenação pelo método das caixas
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
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
145
Algoritmos pseudopolinomiais
para j = a até b faça
n(j)  0;
para i = 1 até n faça
n[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
146
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
:
enquanto:
n[j]  :
k  :
a[k]  :
Setembro 2004
b–a+1
n + (b – a + 1)
n
T(n) = O(b – a + n)
Não é um algoritmo
polinomial, pois T(n) não
é um polinômio apenas
no tamanho da entrada.
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
147
Algoritmos pseudopolinomiais
Exemplo: problema da mochila
• Selecionar dentre n objetos aqueles que serão levados em
uma mochila de capacidade (peso máximo) limitada.
j = 1, ..., n objetos
cj  “lucro”
n
aj  “peso”
maximizar c j x j
b  “peso máximo”

j 1
n
sujeitoa:  a j x j  b
j 1
Hipótese: aj  b j
Setembro 2004
x j  0,1,
j  1,...,n
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
148
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.
k
• Neste ponto, o valor acumulado é
j1
k
• O volume acumulado é
c x
j 1
Setembro 2004
j
a x
j
j
j
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
149
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
150
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
151
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:
u  0; k  0
0,

yk (u )   ,
u  1,...,b;k  0
maxy (u ), y (u  a )  c , u  0,...,b; k  1,...,n
k 1
k 1
k
k

• 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
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
152
Problema da mochila
u  0; k  0
0,

yk (u )   ,
u  1,...,b;k  0
maxy (u ), y (u  a )  c , u  0,...,b; k  1,...,n
k 1
k 1
k
k

• 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.
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
153
Problema da mochila
y5(4) = max 3x1  2 x2  2 x3  x4  3x5
sujeito a : 3x1  3x2  x3  x4  2 x5  4
x j {0,1}, j  1,...,5
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
154
Problema da mochila
max 3x1  2 x2  2 x3  x4  3x5
sujeito a : 3x1  3x2  x3  x4  2 x5  4
x j {0,1}, j  1,...,5
y5(b) = max 3x1  2 x2  2 x3  x4  3x5
sujeito a : 3x1  3x2  x3  x4  2 x5  b
x j {0,1}, j  1,...,5
Valor ótimo = maxb=0,...,4 {y5(b)}
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
155
Problema da mochila
u=4
y0(4)
y5(4)
u=3
y0(3)
y5(3)
u=2
y0(2)
y5(2)
u=1
y0(1)
y5(1)
u=0
y0(0)
y1(0)
y2(0)
y3(0)
y4(0)
y5(0)
k=0
k=1
k=2
k=3
k=4
k=5
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
156
Problema da mochila
u=4
y0(4)
u=3
y0(3)
u=2
y0(2)
u=1
y0(1)
u=0
0
0
0
0
0
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
u=4
-
u=3
-
u=2
-
u=1
-
u=0
0
0
0
0
0
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
u=4
-
?
u=3
-
?
u=2
-
?
u=1
-
?
u=0
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
u=4
-
u=3
-
u=2
-
-
u=1
-
-
u=0
0
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
u=4
-
u=3
-
3
u=2
-
-
u=1
-
-
u=0
0
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
u=4
-
-
u=3
-
3
u=2
-
-
u=1
-
-
u=0
0
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
u=4
-
-
u=3
-
3
u=2
-
-
u=1
-
-
u=0
0
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
u=4
-
-
?
u=3
-
3
?
u=2
-
-
?
u=1
-
-
?
u=0
0
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
u=4
-
-
u=3
-
3
u=2
-
-
u=1
-
-
u=0
0
0
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
u=4
-
-
u=3
-
3
u=2
-
-
-
u=1
-
-
-
u=0
0
0
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
u=4
-
-
u=3
-
3
u=2
-
-
u=1
-
-
-
u=0
0
0
0
2
-
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
u=4
-
-
0
u=3
-
3
u=2
-
-
u=1
-
-
-
u=0
0
0
0
2
-
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
u=4
-
-
0
u=3
-
3
3
u=2
-
-
u=1
-
-
-
u=0
0
0
0
2
-
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
u=4
-
-
-
u=3
-
3
3
u=2
-
-
-
u=1
-
-
-
u=0
0
0
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
u=4
-
-
-
u=3
-
3
3
u=2
-
-
-
u=1
-
-
-
u=0
0
0
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
u=4
-
-
-
?
u=3
-
3
3
?
u=2
-
-
-
?
u=1
-
-
-
?
u=0
0
0
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
u=4
-
-
-
u=3
-
3
3
u=2
-
-
-
u=1
-
-
-
u=0
0
0
0
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
u=4
-
-
-
u=3
-
3
3
u=2
-
-
-
u=1
-
-
-
2
u=0
0
0
0
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
u=4
-
-
-
u=3
-
3
3
u=2
-
-
-
-
u=1
-
-
-
2
u=0
0
0
0
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
u=4
-
-
-
u=3
-
3
3
2
u=2
-
-
-
-
u=1
-
-
-
2
u=0
0
0
0
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
u=4
-
-
-
u=3
-
3
3
0
2
u=2
-
-
-
-
u=1
-
-
-
2
u=0
0
0
0
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
u=4
-
-
-
u=3
-
3
3
0
3
2
u=2
-
-
-
-
u=1
-
-
-
2
u=0
0
0
0
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
u=4
-
-
-
5
2
u=3
-
3
3
3
u=2
-
-
-
-
u=1
-
-
-
2
u=0
0
0
0
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
u=4
-
-
-
5
u=3
-
3
3
3
u=2
-
-
-
-
u=1
-
-
-
2
u=0
0
0
0
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
u=4
-
-
-
5
?
u=3
-
3
3
3
?
u=2
-
-
-
-
?
u=1
-
-
-
2
?
u=0
0
0
0
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
u=4
-
-
-
5
u=3
-
3
3
3
u=2
-
-
-
-
u=1
-
-
-
2
u=0
0
0
0
0
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
u=4
-
-
-
5
u=3
-
3
3
3
u=2
-
-
-
-
u=1
u=0
-
0
-
0
-
0
2
0
0
1
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
u=4
-
-
-
5
u=3
-
3
3
3
u=2
-
-
-
-
u=1
-
-
-
2
2
u=0
0
0
0
0
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
u=4
-
-
-
5
u=3
-
3
3
3
u=2
-
-
-
-
1
u=1
-
-
-
2
2
u=0
0
0
0
0
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
u=4
-
-
-
5
u=3
-
3
3
3
u=2
-
-
-
-
3
u=1
-
-
-
2
2
u=0
0
0
0
0
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
u=4
-
-
-
5
u=3
-
3
3
3
u=2
-
-
-
-
3
u=1
-
-
-
2
2
u=0
0
0
0
0
0
0
3
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
u=4
-
-
-
5
u=3
-
3
3
3
3
u=2
-
-
-
-
3
u=1
-
-
-
2
2
u=0
0
0
0
0
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
u=4
-
-
-
5
1
u=3
-
3
3
3
3
u=2
-
-
-
-
3
u=1
-
-
-
2
2
u=0
0
0
0
0
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
u=4
-
-
-
5
0
1
u=3
-
3
3
3
3
u=2
-
-
-
-
3
u=1
-
-
-
2
2
u=0
0
0
0
0
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
u=4
-
-
-
5
0
5
1
u=3
-
3
3
3
3
u=2
-
-
-
-
3
u=1
-
-
-
2
2
u=0
0
0
0
0
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
u=4
-
-
-
5
5
u=3
-
3
3
3
3
u=2
-
-
-
-
3
u=1
-
-
-
2
2
u=0
0
0
0
0
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
u=4
-
-
-
5
5
?
u=3
-
3
3
3
3
?
u=2
-
-
-
-
3
?
u=1
-
-
-
2
2
?
u=0
0
0
0
0
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
u=4
-
-
-
5
5
u=3
-
3
3
3
3
u=2
-
-
-
-
3
u=1
-
-
-
2
2
u=0
0
0
0
0
0
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
u=4
-
-
-
5
5
u=3
-
3
3
3
3
u=2
-
-
-
-
3
u=1
-
-
-
2
2
u=0
0
0
0
0
0
0
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
u=4
-
-
-
5
5
u=3
-
3
3
3
3
u=2
-
-
-
-
3
u=1
-
-
-
2
2
u=0
0
0
0
0
0
0
2
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
u=4
-
-
-
5
5
u=3
-
3
3
3
3
u=2
-
-
-
-
3
u=1
-
-
-
2
2
2
u=0
0
0
0
0
0
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
u=4
-
-
-
5
5
u=3
-
3
3
3
3
u=2
-
-
-
-
3
0
3
u=1
-
-
-
2
2
2
u=0
0
0
0
0
0
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
u=4
-
-
-
5
5
u=3
-
3
3
3
3
u=2
-
-
-
-
3
0
3
3
u=1
-
-
-
2
2
2
u=0
0
0
0
0
0
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
u=4
-
-
-
5
5
u=3
-
3
3
3
3
u=2
-
-
-
-
3
3
u=1
-
-
-
2
2
2
u=0
0
0
0
0
0
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
u=4
-
-
-
5
5
u=3
-
3
3
3
3
0
3
u=2
-
-
-
-
3
3
u=1
-
-
-
2
2
2
u=0
0
0
0
0
0
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
u=4
-
-
-
5
5
u=3
-
3
3
3
3
0
5
3
u=2
-
-
-
-
3
3
u=1
-
-
-
2
2
2
u=0
0
0
0
0
0
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
u=4
-
-
-
5
5
u=3
-
3
3
3
3
5
u=2
-
-
-
-
3
3
u=1
-
-
-
2
2
2
u=0
0
0
0
0
0
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
u=4
-
-
-
5
5
0
3
u=3
-
3
3
3
3
5
u=2
-
-
-
-
3
3
u=1
-
-
-
2
2
2
u=0
0
0
0
0
0
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
u=4
-
-
-
5
5
0
6
3
u=3
-
3
3
3
3
5
u=2
-
-
-
-
3
3
u=1
-
-
-
2
2
2
u=0
0
0
0
0
0
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
u=4
-
-
-
5
5
6
u=3
-
3
3
3
3
5
u=2
-
-
-
-
3
3
u=1
-
-
-
2
2
2
u=0
0
0
0
0
0
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
u=4
-
-
-
5
5
6
y5(4) = 6
u=3
-
3
3
3
3
5
y5(3) = 5
u=2
-
-
-
-
3
3
y5(2) = 3
u=1
-
-
-
2
2
2
y5(1) = 2
u=0
0
0
0
0
0
0
y5(0) = 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
u=4
-
-
-
5
5
6
y5(4) = 6
u=3
-
3
3
3
3
5
y5(3) = 5
u=2
-
-
-
-
3
3
y5(2) = 3
u=1
-
-
-
2
2
2
y5(1) = 2
u=0
0
0
0
0
0
0
y5(0) = 0
k=0
k=1
k=2
k=3
k=4
k=5
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
208
Problema da mochila
u=4
-
-
-
5
5
6
y5(4) = 6
u=3
-
3
3
3
3
5
y5(3) = 5
u=2
-
-
-
-
3
3
y5(2) = 3
u=1
-
-
-
2
2
2
y5(1) = 2
u=0
0
0
0
0
0
0
y5(0) = 0
k=0
k=1
k=2
k=3
k=4
k=5
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
209
Problema da mochila
x5=1
u=4
-
-
-
5
5
6
y5(4) = 6
u=3
-
3
3
3
3
5
y5(3) = 5
u=2
-
-
-
-
3
3
y5(2) = 3
u=1
-
-
-
2
2
2
y5(1) = 2
u=0
0
0
0
0
0
0
y5(0) = 0
k=0
k=1
k=2
k=3
k=4
k=5
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
210
Problema da mochila
x4=1
x5=1
u=4
-
-
-
5
5
6
y5(4) = 6
u=3
-
3
3
3
3
5
y5(3) = 5
u=2
-
-
-
-
3
3
y5(2) = 3
u=1
-
-
-
2
2
2
y5(1) = 2
u=0
0
0
0
0
0
0
y5(0) = 0
k=0
k=1
k=2
k=3
k=4
k=5
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
211
Problema da mochila
x3=1
x4=1
x5=1
u=4
-
-
-
5
5
6
y5(4) = 6
u=3
-
3
3
3
3
5
y5(3) = 5
u=2
-
-
-
-
3
3
y5(2) = 3
u=1
-
-
-
2
2
2
y5(1) = 2
u=0
0
0
0
0
0
0
y5(0) = 0
k=0
k=1
k=2
k=3
k=4
k=5
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
212
Problema da mochila
x2=0
x3=1
x4=1
x5=1
u=4
-
-
-
5
5
6
y5(4) = 6
u=3
-
3
3
3
3
5
y5(3) = 5
u=2
-
-
-
-
3
3
y5(2) = 3
u=1
-
-
-
2
2
2
y5(1) = 2
u=0
0
0
0
0
0
0
y5(0) = 0
k=0
k=1
k=2
k=3
k=4
k=5
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
213
Problema da mochila
x1=0
x2=0
x3=1
x4=1
x5=1
u=4
-
-
-
5
5
6
y5(4) = 6
u=3
-
3
3
3
3
5
y5(3) = 5
u=2
-
-
-
-
3
3
y5(2) = 3
u=1
-
-
-
2
2
2
y5(1) = 2
u=0
0
0
0
0
0
0
y5(0) = 0
k=0
k=1
k=2
k=3
k=4
k=5
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
214
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
215
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
216
Algoritmos pseudopolinomiais
y(0,0)  0;
para k = 1 até b faça y(k,0)  - ;
para j = 1 até n faça
iní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
217
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 no
tamanho da entrada e no valor do maior dado de
entrada
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
218
Caixeiro viajante
• Grafo orientado com n nós
• Distâncias dij
S  { 2, 3, ..., n}
kS
C(S,k) =
Setembro 2004
custo ótimo de sair do nó 1, visitar todos as
cidades de S uma única vez, terminar na
cidade k.
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
219
Caixeiro viajante
• Início: calcular C(S,k) para |S| = 1, k = 2, ..., n
Ck, k   d1k
• 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:
C s, k   minC S  k , m  d mk 
m  S  k 
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
220
Caixeiro viajante
• Calcular para todos S de dado tamanho e para cada possível
nó m em S.
• Complexidade:
 n  1

  k  (k  1)


k 2  k 
mS
adições


n
n
n 1
escolher k dentre  n 1
 n  1

 n  
k 2  k 
 O n 2  2n
n 1
2

Setembro 2004

Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
221
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
222
Definições recursivas ou indutivas
fat(n) = 1 • 2 • ... • n
Definição recursiva:
Base:
1! = 1
Indução: n! = n • (n – 1)!
nº uso do passo
indutivo
2º uso do passo
indutivo
1º uso do passo
indutivo
Base
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
223
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.
+•/
Setembro 2004
Operadores binários
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
224
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
225
Procedimentos recursivos
function fat (n: integer): integer;
início
se n  1 então
fat  1
senão
fat  n · fat (n-1)
fim
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
226
Procedimentos recursivos
Call 
fat(4)
Call 
fat(3)
Call 
fat(2)
return 24
 fat(4)
return 6
 fat(3)
return 2
 fat(2)
Call   return 1
fat(1)
Base: T(1) = O(1)
Indução: T(n) = O(1) + T(n-1)
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
n>1
227
Procedimentos recursivos
• É essencial que a indução faça apenas chamadas envolvendo
argumentos de menor tamanho e que a base seja sempre
necessariamente atingida.
SelectionSort
1) Obter menor elemento da cauda do vetor A[i...n]
2) Trocá-lo por A[i]
3) Ordenar o vetor A[i+1... n]
• 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}
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
228
Procedimentos recursivos
procedure SelectionSort (var A: intarray; i, n: integer);
var j,smaller, temp: integer;
início
se i < n então
iní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)
fim
T(n) = O(1) + O(n) + T(n-1)
fim
T(1) = O(1)
fim
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
229
Procedimentos recursivos
• 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.
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
230
Procedimentos recursivos
• 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) + d
d) Resolver a equação de recorrência
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
231
Procedimentos recursivos
procedure SelectionSort (var A: intarray; i, n: integer);
var j,smaller, temp: integer;
Base (i = n): apenas um
início
elemento a ordenar
se i < n então
início
Indução (i < n): obter o
smaller  i;
menor elemento em
para j  i + 1 até n faça
A[i...N], colocá-lo em
se A[j] < A[smaller] então
A[i] e ordenar
A[i+1... N]
início
smaller  j;
temp  A[smaller];
A[smaller]  A[i];
A[i]  temp;
SelectionSort (A,i+1,n)
fim
fim
fim
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
232
Procedimentos recursivos
T(1) = O(1) = a
T(n) = O(n) + T(n-1)
b.n
T(1) = a
T(n) = b.n + T(n-1)
T(2) = 2b + a
T(3) = 3b + 2b + a = 5b + a
T(4) = 4b + 5b + a = 9b + a
T(n) = n
  k .b  a
k 2
n
 b k  a
k 2
2n
 b
(n  1)  a
2


 O(n 2 )
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
233
Procedimentos recursivos
Voltando ao cálculo do fatorial:
Base: T(1) = O(1)
Indução: T(n) = O(1) + T(n-1)
n>1
T(1) = a
T(n) = b + T(n-1)
n>1
T(1) = a
T(2) = T(1) + b
T(3) = T(2) + b = T(1) + 2b
T(4) = T(3) + b = T(1) + 3b
T(n) = T(1) + (n-1) · b
T(n) = a + (n-1)·b = O(n)
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
234
Merge sort
• 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
235
235
Merge sort
Lista 1
Merge
Lista 2
1
1
2
2
2
4
7
2
7
7
4
8
9
7
7
7
8
9
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
236
236
Merge sort
Merge
Lista 1
1
2
…
2
4
…
Lista 2
Mergeados recursivamente
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
237
237
Merge sort
Call
1 (2 2 4 7 7 7 8 9)
merge(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)
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)
merge(9, 8)
8 (9)
merge(9, NIL)
9
Return
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
238
238
Merge sort
Lista 1
4
6
8
4
1
8
4 12
L4  L24
10
12
14
5 nil
L8 > L24
L8 > L28
24
Lista 2
Setembro 2004
28
3 nil
24 26
28 30
2
3
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
8
239
239
Merge sort
type cell=record
element : integer
next : listType
function merge (lista1, lista2: listType) : listType
início
se lista1=NIL então
merge  lista2
type listType=^cell
senão
se lista2=NIL então
merge  lista1
senão
se lista1^.elemento  lista2^.elemento então
lista1^.next  merge(lista1^.next, lista2)
merge  lista1
else
lista2^.next  merge(lista1, lista2^.next)
merge  lista2
fim
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
240
240
Merge sort
function split (lista: listType) : listType
Var second cell: listType
iní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 cell
fim
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
241
241
Complexidade de Merge sort
Merge
n=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)
Split
n: tamanho da lista
lista1=NIL ou lista1^.next=NIL  O(1)
T(n)=O(1)+T(n-2)
T(0)=a
T(1)=b
T(n)=c + T(n-2)
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
242
242
Complexidade de Merge sort
T(0) = a
T(1) = b
T(1) = b
T(2) = c + a
T(3) = c + b
T(4) = c + ( c + a ) = 2c + a
T(5) = c + ( c + b ) = 2c + b
T(6) = 3c + a
T(7) = 3c + b
n par: T(n) = ( n/2 ) · c + a
n í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
243
243
Merge sort
program sort (input, output)
const max = 100
type cell = record
elemento: integer
next: listType
end
listType=^cell
var A: array [1…max] of integer
k, n: integer
list: listType
procedure merge sort (var list: listType)
function merge (lista1, lista2: listType): listType
function split (list: listType) : listType
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
244
244
Merge sort
function makeList (i, n: integer) : listType
var new cell: listType
início
se i > n então
makeList  NIL
else
new(newCell)
newCell^.next  makeList(i+1, n)
newCell^.element  A[i]
makeList  newCell
fim
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
245
245
Merge sort
procedure printList (list: listType)
início
se list = NIL então
return
else
write(list^.element)
printList(list^.next)
fim
início
readln(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
246
246
Merge sort
procedure mergeSort(var list: listType)
var secondList: listType
início
se list <> NIL então
se list^.next <> NIL então
secondList  split(list)
mergeSort(list)
mergeSort(secondList)
list  merge(list, secondList)
fim
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
247
247
Merge sort
list  NIL ou list^.next  NIL
n: tamanho da lista
O(1)
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
Setembro 2004
T(n)=O(n log n)
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
248
248
Torres de Hanoi
Setembro 2004
A
A
B
B
A
C
A
C
A
B
X
Y
Z
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
249
249
Torres de Hanoi
A
Setembro 2004
A
B
A
B
C
B
C
D
C
D
X
Y
Z
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
250
250
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
A
Setembro 2004
A
B
A
B
C
B
C
D
C
D
X
Y
Z
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
251
251
Torres de Hanoi
n-1
n-1
n
N
n-1
N
X
Y
Z
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
252
252
Torres de Hanoi
hanoi (n, x, y, z)
início
mover n discos de x para y usando z
xy
se n =1 então
xy
senão
T(n) = O(1) + T(n-1)
hanoi(n-1, x, z, y)
T(n) = 1 + T(n-1)
xy
hanoi(n-1, z, y, x)
T(n) = 1 + 2 T(n-1)
fim
T(n) = O(1)
b
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
n>1
n=1
253
253
Torres de Hanoi
T n   2  T n  1  a
T n   2  2  T n  2  a   a
T (n)  2 2  T n  2   a  21  a
T (n)  2 2  2  T n  3  a   
T (n)  23  T n  3  a  2 2  a  21  a
T (n)  2  2  T n  4  a   
3
T n   2
T (n)  2 4  T n  4   a  23  a  2 2  a  21  a k
n 1
 n2 j 
 T (1)   2   a
 j 0 
2 k 1  1
2 

a 1
j 0
j


T n   b  2 n 1  2 n 1  1  a


T n   2 n 1  2 n 1  1
 
O (1)
T n   O 2 n
Setembro 2004
Projeto e Análise de Algoritmos - Celso Carneiro Ribeiro
254
254