Embed Size (px)
Citation preview
Analise de Algoritmos e
Estruturas de Dados
Guilherme Oliveira Mota
CMCC - Universidade Federal do ABC
10 de outubro de 2018
Esta versao e um rascunho ainda em elaboracao e nao foi revisado
ii
Sumario
I Introducao a Analise de Algoritmos 1
1 Algoritmos: corretude e tempo de execucao 3
1.1 Algoritmos de busca em vetores . . . . . . . . . . . . . . . . . . . . . . 4
1.1.1 Corretude de algoritmos (utilizando invariante de lacos) . . . . . 6
1.2 Tempo de execucao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
1.2.1 Analise de melhor caso, pior caso e caso medio . . . . . . . . . . 13
1.3 Notacao assintotica . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.3.1 Notacoes O, Ω e Θ . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.3.2 Notacoes o e ω . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
1.3.3 Relacoes entre as notacoes assintoticas . . . . . . . . . . . . . . 23
2 Recursividade / Divisao e Conquista 25
2.1 Algoritmos recursivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.1.1 Fatorial . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
2.1.2 Busca binaria . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
2.1.3 Algoritmos recursivos × algoritmos iterativos . . . . . . . . . . 28
2.2 Divisao e conquista . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3 Metodos para solucao de equacoes de recorrencia 31
3.1 Logaritmos e somas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.2 Metodo iterativo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.2.1 Limitantes assintoticos inferiores e superiores . . . . . . . . . . . 37
3.3 Metodo da substituicao . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
iv SUMARIO
3.3.1 Desconsiderando pisos e tetos . . . . . . . . . . . . . . . . . . . 38
3.3.2 Diversas formas de obter o mesmo resultado . . . . . . . . . . . 39
3.3.3 Ajustando os palpites . . . . . . . . . . . . . . . . . . . . . . . . 40
3.3.4 Mais exemplos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.4 Metodo da arvore de recorrencia . . . . . . . . . . . . . . . . . . . . . . 45
3.5 Metodo mestre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.5.1 Resolvendo recorrencias com o metodo mestre . . . . . . . . . . 50
3.5.2 Ajustes para aplicar o metodo mestre . . . . . . . . . . . . . . . 51
II Estruturas de dados 55
4 Lista encadeada, fila e pilha 57
4.1 Lista encadeada . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 57
4.2 Pilha . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
4.3 Fila . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
5 Heap binario 67
5.1 Construcao de um heap binario . . . . . . . . . . . . . . . . . . . . . . 68
6 Fila de prioridades 77
7 Union-find 81
III Algoritmos de ordenacao 83
8 Insertion sort 85
8.1 Corretude e tempo de execucao . . . . . . . . . . . . . . . . . . . . . . 86
8.1.1 Analise de melhor caso, pior caso e caso medio . . . . . . . . . . 88
8.1.2 Uma analise mais direta . . . . . . . . . . . . . . . . . . . . . . 89
9 Merge sort 91
10 Selection sort e Heapsort 95
10.1 Selection sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95
SUMARIO v
10.2 Heapsort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97
11 Quicksort 101
11.1 Tempo de execucao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 105
12 Ordenacao em tempo linear 111
12.1 Counting sort . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111
IV Tecnicas de construcao de algoritmos 115
13 Programacao dinamica 117
13.1 Um problema simples . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118
13.2 Aplicacao e caracterısticas principais . . . . . . . . . . . . . . . . . . . 121
13.3 Utilizando programacao dinamica . . . . . . . . . . . . . . . . . . . . . 125
13.3.1 Corte de barras . . . . . . . . . . . . . . . . . . . . . . . . . . . 125
13.4 Comparando algoritmos top-down e bottom-up . . . . . . . . . . . . . 130
V Algoritmos em grafos 131
14 Grafos 133
14.1 Formas de representar um grafo . . . . . . . . . . . . . . . . . . . . . . 134
14.2 Conceitos essenciais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135
14.3 Trilhas, passeios, caminhos e ciclos . . . . . . . . . . . . . . . . . . . . 137
15 Buscas 139
15.1 Busca em largura . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139
15.1.1 Distancia entre vertices . . . . . . . . . . . . . . . . . . . . . . . 142
15.2 Busca em profundidade . . . . . . . . . . . . . . . . . . . . . . . . . . . 146
15.2.1 Ordenacao topologica . . . . . . . . . . . . . . . . . . . . . . . . 150
15.2.2 Componentes fortemente conexas . . . . . . . . . . . . . . . . . 152
15.2.3 Outras aplicacoes dos algoritmos de busca . . . . . . . . . . . . 152
16 Arvores geradoras mınimas 155
16.1 Algoritmo de Prim . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157
16.2 Algoritmo de Kruskal . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160
17 Trilhas Eulerianas 165
18 Caminhos mınimos 169
18.1 Algoritmo de Dijkstra . . . . . . . . . . . . . . . . . . . . . . . . . . . 170
18.2 Algoritmo de Bellman-Ford . . . . . . . . . . . . . . . . . . . . . . . . 173
18.3 Caminhos mınimos entre todos os pares de vertices . . . . . . . . . . . 179
18.3.1 Algoritmo de Floyd-Warshall . . . . . . . . . . . . . . . . . . . 180
18.3.2 Algoritmo de Johnson . . . . . . . . . . . . . . . . . . . . . . . 183
VI Teoria da computacao 187
19 Complexidade computacional 189
19.1 Classes P, NP e co-NP . . . . . . . . . . . . . . . . . . . . . . . . . . 189
19.2 NP-completude . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 192
vi
Parte
IIntroducao a Analise de Algoritmos
Capıtulo
1Algoritmos: corretude e tempo de
execucao
Um algoritmo e um procedimento que recebe um conjunto de dados como entrada e
devolve um conjunto de dados como saıda apos uma quantidade finita de passos bem
definidos. Dizemos que um algoritmo resolve um problema se, para todas as entradas
possıveis, ele produz uma saıda que contem a solucao do problema computacional
em questao. Algoritmos estao presentes na vida das pessoas ha muitos anos e sao
utilizados o tempo todo. Muitas vezes quando precisamos colocar um conjunto de fichas
numeradas em ordem nao-decrescente, ordenar um conjunto de cartas de baralho ou
selecionar a cedula de maior valor em nossa carteira, inconscientemente nos utilizamos
um algoritmo de nossa preferencia para resolver o problema. Por exemplo, para colocar
um conjunto de fichas numeradas em ordem nao-decrescente ha quem prefira olhar
todas as fichas e encontrar a menor, depois verificar o restante das fichas e encontrar a
menor e assim por diante. Outras pessoas preferem dividir as fichas em varios conjuntos
menores de fichas, ordenar cada um desses conjuntos e depois junta-los de modo que o
conjunto todo fique ordenado. Existem diversas outras maneiras de fazer isso e cada
uma delas e realizada por um procedimento que chamamos de algoritmo.
Ao analisar um algoritmo estamos interessados primeiramente em entender os
detalhes de como ele funciona, bem como em mostrar que, como esperado, o algoritmo
funciona corretamente. Verificar se um algoritmo e eficiente e outro aspecto impor-
tantıssimo da analise de algoritmos. Explicaremos esses aspectos analisando o problema
de encontrar um valor em um vetor e analisar algoritmos simples que resolvem esse
problema.
1.1 Algoritmos de busca em vetores
Vetores sao estruturas de dados simples que armazenam um conjunto de objetos,
geralmente do mesmo tipo, armazenados de forma contınua na memoria. O acesso a um
elemento do vetor e feito de forma direta, atraves do ındice do elemento. Um vetor A
com capacidade para n elementos e representado por A[1..n] e A[i] retorna o elemento
contido na posicao i, para todo 1 ≤ i ≤ n. Ademais, para quaisquer 1 ≤ i < j ≤ n,
denotamos por A[i..j] o subvetor de A que contem os elementos A[i], A[i+ 1], . . . , A[j].
Uma operacao fundamental e de extrema importancia em diversos procedimentos
computacionais e a busca por uma informacao especıfica em um conjunto de dados.
Primeiramente, considere um vetor A[1..n] nao ordenado contendo numeros reais.
Gostarıamos de saber se um valor x esta dentro de A. O algoritmo mais simples e
conhecido como Busca linear. Esse algoritmo percorre o vetor, examinando todos os
seus elementos, um a um, ate encontrar x ou ate verificar todos os elementos de A.
Algoritmo 1: Busca linear(A[1..n], x)
1 i = 1
2 enquanto i ≤ n faca
3 se A[i] == x entao
4 retorna i
5 i = i+ 1
6 retorna −1
No que segue, seja tamanho(A) = n. O funcionamento do algoritmo Busca
linear e bem simples. A variavel i indica que posicao do vetor A estamos analisando.
Inicialmente fazemos i = 1. Incrementamos o valor de i de uma unidade sempre que as
duas condicoes do laco enquanto forem satisfeitas, i.e., A[i] 6= x e i ≤ n. Assim, o
laco enquanto simplesmente verifica se A[i] contem x e se o vetor A ja foi totalmente
verificado. Caso x seja encontrado, o laco enquanto e encerrado e o algoritmo retorna
4
o ındice i tal que A[i] = x. Caso contrario, o algoritmo retorna −1.
Intuitivamente, e facil perceber que Busca linear funciona corretamente. Mas
como podemos ter certeza que o comportamento de Busca linear e sempre como
esperamos que seja? Na proxima secao veremos uma forma de provar que algoritmos
funcionam corretamente. Antes, vejamos outra forma de resolver o problema de
encontrar um valor em um vetor A dado que A esta ordenado.
Considere um vetor ordenado (ordem nao-decrescente1) A com n elementos, i.e.,
A[i] ≤ A[i+ 1] para todo 1 ≤ i ≤ n− 1. Por simplicidade, assuma que n e multiplo
de 2 (assim nao precisamos nos preocupar com pisos e tetos). Nesse caso, existe um
procedimento simples, chamado de busca binaria, que consegue realizar a busca por
uma chave x em A.
A estrategia da busca binaria e muito simples. Basta verificar se A[n/2] = x e
realizar o seguinte procedimento: se A[n/2] = x, entao a busca esta encerrada. Caso
contrario, se x < A[n/2], entao temos a certeza que se x estiver em A, entao x esta na
primeira metade de A, i.e., x esta em A[1 . . . n/2− 1] (isso segue do fato de A estar
ordenado). Caso x > A[n/2], entao sabemos que se x estiver em A, entao x esta no
vetor A[n/2 + 1..n]. Suponha que x < A[n/2]. Assim, podemos verificar se x esta em
A[1 . . . n/2− 1] utilizando a mesma estrategia, i.e., comparamos x com o valor que esta
na metade do vetor A[1 . . . n/2− 1], i.e., comparamos x com A[n/4− 2] e verificamos a
primeira ou segunda metade do vetor dependendo do resultado da comparacao. Abaixo
temos o algoritmo de busca binaria, que recebe um vetor A[1..n] ordenado de modo
nao-decrescente e um valor x a ser buscado.
1Aqui utilizamos o termo nao-decrescente em vez de crescente para indicar que podemos terA[i] = A[i + 1].
5
Algoritmo 2: Busca binaria(A[1..n], x)
1 esquerda = 1
2 direita = n
3 enquanto esquerda ≤ direita faca
4 meio = esquerda+⌊direita−esquerda
2
⌋5 se A[meio] == x entao
6 retorna meio
7 senao se x < A[meio] entao
8 esquerda = meio+ 1
9 senao
10 direita = meio− 1
11 retorna −1
1.1.1 Corretude de algoritmos (utilizando invariante de lacos)
Ao utilizar um algoritmo para resolver um determinado problema esperamos que ele de
sempre a resposta correta. Como analisar se um algoritmo e executado corretamente?
A seguir veremos uma maneira de mostrar que algoritmos funcionam corretamente.
Basicamente, mostraremos que o algoritmo possui certas propriedades e tais propri-
edades continuam verdadeiras apos cada iteracao de um determinado laco (para ou
enquanto).
Uma invariante de laco e um conjunto de propriedades do algoritmo que se mantem
apos iteracoes do laco. Mais formalmente, uma invariante de laco e definida como
abaixo.
6
Definicao 1.1: Invariante de laco
E um conjunto de propriedades (a invariante) tal que valem os itens abaixo.
(i) a invariante e verdadeira imediatamente antes da primeira iteracao do laco,
(ii) se a invariante e verdadeira antes de uma iteracao, entao e verdadeira
imediatamente antes da proxima iteracao.
Para ser util, uma invariante de laco precisa permitir que apos a ultima iteracao
do laco possamos concluir que o algoritmo funciona corretamente utilizando essa
invariante. Uma observacao importante e que quando dizemos “imediatamente antes
de uma iteracao” estamos nos referindo ao momento imediatamente antes de iniciar a
linha correspondente ao laco.
Para entender como podemos utilizar as invariantes de laco para provar a corre-
tude de algoritmos vamos inicialmente fazer a analise dos algoritmos Busca linear.
Comecemos com o algoritmo Busca linear, considerando a seguinte invariante de
laco:
Invariante: Busca linear
Antes de cada iteracao indexada por i, o vetor A[1..i− 1] nao contem x.
Observe que o item (i) na definicao de invariante e trivialmente valido antes da
primeira iteracao, quando i = 1, pois nesse caso a invariante trata de A[0], que nao
existe. Logo, nao pode conter x. Para verificar o item (ii), suponha agora que o vetor
A[1 . . . i − 1] nao contem x e o laco enquanto termina a execucao de sua i-esima
iteracao. Como a iteracao foi terminada, isso significa que a linha 4 nao foi executada.
Portanto, A[i] 6= x. Esse fato, juntamente com o fato de que x /∈ A[1 . . . i− 1], implica
que x /∈ A[1, . . . , i]. Assim, a invariante continua valida antes da (i+ 1)-esima iteracao.
Precisamos agora utilizar a invariante para concluir que o algoritmo funciona
corretamente, i.e., caso x esteja em A o algoritmo deve retornar um ındice i tal que
A[i] = x, e caso x nao esteja em A o algoritmo deve retornar −1. Mas note que se o
algoritmo retorna i na linha 4, entao a comparacao na linha 3 e verificada com sucesso,
de modo que temos A[i] = x como desejado. Porem, se o algoritmo retorna −1, entao
7
o laco enquanto foi executado ate que i = n + 1. Assim, na ultima vez que a linha
que contem o laco enquanto e verificada, temos i = n + 1. Pela invariante de laco,
sabemos que x /∈ A[1 . . . i− 1], i.e., x /∈ A[1..n]. Na ultima linha o algoritmo retorna
−1, que era o desejado no caso em que x nao esta em A. Portanto, o algoritmo funciona
corretamente.
A primeira vista todo o processo que fizemos para mostrar que o algoritmo Busca
linear funciona corretamente pode parecer excessivamente complicado. Porem, essa
impressao vem do fato desse algoritmo ser muito simples (assim, a analise de algo
simples parece ser desnecessariamente longa). Veremos casos onde a corretude de um
dado algoritmo nao e clara, de modo que a necessidade de se utilizar invariantes de
laco e evidente.
Para clarear nossas ideias, analisaremos agora o seguinte algoritmo que realiza uma
tarefa muito simples: recebe um vetor A[1..n] e retorna o produtorio de seus elementos,
i.e.,∏n
i=1A[i].
Algoritmo 3: Produtorio(A[1..n])
1 produto = 1
2 para i = 1 ate tamanho(A) faca
3 produto = produto · A[i]
4 retorna produto
Como podemos definir a invariante de laco para mostrar a corretude de Pro-
dutorio(A[1..n])? A cada iteracao do laco para nos ganhamos mais informacao.
Precisamos entender como essa informacao ajuda a obter a saıda desejada do algoritmo.
No caso de Produtorio, conseguimos perceber que ao fim da i-esima iteracao temos
o produtorio dos elementos de A[1..k]. Isso e muito bom, pois podemos usar esse fato
para ajudar no calculo do produtorio dos elementos de A[1..n]. De fato, a cada iteracao
caminhamos um passo no sentido de calcular o produtorio desejado. Nao e difıcil
perceber que a seguinte invariante e uma boa opcao para mostrar que Produtorio
funciona.
8
Invariante: Produtorio
Antes de cada iteracao indexada por i, a variavel produto contem o produtorio
dos elementos de A[1..i− 1].
Trivialmente a invariante e valida antes da primeira iteracao do laco para, de modo
que o item (i) da definicao de invariante de laco e valido. Para verificar o item (ii),
suponha que a invariante seja valida antes da iteracao i, i.e., produto =∏i−1
j=1A[j] e
considere o momento imediatamente antes da iteracao i+ 1. Dentro da i-esima iteracao
do laco para vamos obter
produto = produto · A[i] (1.1)
=
(i−1∏j=1
A[j]
)· A[i] (1.2)
=i∏
j=1
A[j], (1.3)
confirmando a validade do item (ii), pois mostramos que a invariante se manteve valida
apos a i-esima iteracao.
Note que na ultima vez que a linha 2 do algoritmo e executada temos i = n + 1.
Assim, o algoritmo nao executa a linha 3, e retorna produto. Como a invariante e valida,
temos que produto =∏n
i=1A[i], que e o resultado desejado. Portanto, o algoritmo
funciona corretamente.
Perceba que mostrar que uma invariante se mantem durante a execucao de um
algoritmo nada mais e que uma prova por inducao na quantidade de iteracoes de um
dado laco.
Na proxima secao discutimos o tempo que algoritmos levam para ser executados,
entendendo como analisar algoritmos de uma maneira sistematica para determinar
quao eficiente eles sao.
9
1.2 Tempo de execucao
Uma propriedade desejavel para um algoritmo e que ele seja “eficiente”. Apesar de
intuitivamente associarmos a palavra “eficiente” nesse contexto com o significado de
velocidade em que um algoritmo e executado, precisamos discutir alguns pontos para
deixar claro o que seria um algoritmo eficiente. Um algoritmo sera mais rapido quando
implementado em um computador mais potente do que quando implementado em um
computador menos potente. Se a entrada for pequena, o algoritmo provavelmente sera
executado mais rapidamente do que se a entrada fosse muito grande. Varios fatores
afetam o tempo de execucao de um algoritmo. Por exemplo, o sistema operacional
utilizado, linguagem de programacao utilizada, velocidade do processador, modo com o
algoritmo foi implementado, dentre outros. Assim, queremos um conceito de eficiencia
que seja independente da entrada, da plataforma utilizada e que possa ser de alguma
forma quantificada concretamente de acordo com o tamanho da entrada.
Para analisar a eficiencia de um algoritmo vamos analisar o seu tempo de execucao,
que conta a quantidade de operacoes primitivas (operacoes aritmeticas, comparacoes
etc.) e “passos” executados. Dessa forma e possıvel ter uma boa estimativa do quao
rapido um algoritmo e, alem de permitir comparar seu tempo de execucao com o de
outros algoritmos, o que nos permite escolher o mais eficiente para uma determinada
tarefa.
Em geral, o tempo de execucao de um algoritmo cresce junto com a quantidade de
dados passados como entrada. Portanto, definimos o tempo de execucao como uma
funcao no tamanho da entrada. Para entender melhor vamos comeca com uma
analise simples dos algoritmos Busca linear e Busca binaria vistos anteriormente.
Veremos adiante que nao e tao importante para a analise do tempo de execucao
de um algoritmo se uma dada operacao primitiva leva um certo “tempo” t para ser
executada ou nao. Assim, vamos assumir que toda operacao primitiva leva “tempo” 1
para ser executada. Por comodidade, repetimos o algoritmo Busca linear abaixo.
10
Algoritmo 4: Busca linear(A[1..n], x)
1 i = 1
2 enquanto i ≤ tamanho(A) faca
3 se A[i] == x entao
4 retorna i
5 i = i+ 1
6 retorna −1
Denote por tx a posicao do elemento x no vetor A[1..n], onde colocamos tx = n+ 1
caso x nao esteja em A. Note que a linha 1 e executada somente uma vez e somente
uma dentre as linhas 4 e 6 e executada (obviamente, somente uma vez, dado que o
algoritmo encerra quando retorna um valor). Ja o laco enquanto da linha 2 e executado
tx vezes, a linha 3 e executada tx vezes, e a linha 5 e executada tx − 1 vezes. Assim, o
tempo de execucao T (n) de Busca linear(A[1..n], x) e dado como abaixo (note que
o tempo de execucao depende do tamanho n do vetor de entrada A).
T (n) = 1 + 1 + tx + tx + tx − 1
= 3tx + 1. (1.4)
O tempo de execucao depende de onde x se encontra no vetor A. Se A contem n
elementos e x esta na ultima posicao de A, entao T (n) = 3n+ 1. Porem, se x esta na
primeira posicao de A, temos T (n) = 4.
Para a busca binaria, vamos fazer uma analise semelhante. Por comodidade, repeti-
mos o algoritmo Busca binaria abaixo. Lembre-se que na busca binaria assumimos
que o vetor esta ordenado de modo nao decrescente.
11
Algoritmo 5: Busca binaria(A[1..n], x)
1 esquerda = 1
2 direita = tamanho(A)
3 enquanto esquerda ≤ direita faca
4 meio = esquerda+⌊direita−esquerda
2
⌋5 se A[meio] == x entao
6 retorna meio
7 senao se x < A[meio] entao
8 esquerda = meio+ 1
9 senao
10 direita = meio− 1
11 retorna −1
Denote por rx a quantidade de vezes que o laco enquanto na linha 3 e executado
(note que isso depende de onde x esta em A). As linhas 1 e 2 sao executadas uma
vez cada, e somente uma das linhas 6 e 11 e executada. A linha 4 e executada no
maximo rx vezes, as linhas 5, 7 e 9 sao executadas um total de no maximo rx vezes
(pois em cada iteracao do laco somente uma delas e executada) e as linhas 8 e 10
sao executadas (no total) no maximo rx vezes. Assim, o tempo de execucao T ′(n) de
Busca binaria(A[1..n], x) e dado como abaixo.
T ′(n) ≤ rx + 3 + rx + rx + rx
= 4rx + 3. (1.5)
Assim como na busca linear, o tempo de execucao depende do tamanho da entrada. Se
x esta na primeira ou ultima posicao do vetor, note que o algoritmo de busca binaria
sempre descarta metade do vetor que esta sendo considerado, diminuindo o tamanho
do vetor analisado pela metade, ate que se chegue em um vetor com uma unica posicao
(ou duas, dependendo da paridade de n). Como sempre metade do vetor e descartado, o
algoritmo analisa, nessa ordem, vetores de tamanho n, n/2, n/22 . . . n/2i, onde o ultimo
12
vetor analisado tem tamanho 1, i.e., temos n/2i = 1, que implica i = log n. Assim,
o laco enquanto e executado no maximo log n vezes, de modo que temos rx ≤ log n.
Assim, temos T ′(n) ≤ 4 log n+ 3.
1.2.1 Analise de melhor caso, pior caso e caso medio
O tempo de execucao de melhor caso de um algoritmo e o tempo de execucao da
instancia de entrada que executa de forma mais rapida, dentre todas as instancias
possıveis de um dado tamanho n. No caso da Busca linear, o melhor caso ocorre
quando o elemento x a ser buscado encontra-se na primeira posicao do vetor A. Como
o tempo de execucao de Busca linear e dado por T (n) = 3tx + 1 (veja (1.4)), onde
tx e a posicao de x em A, temos que no melhor caso, o tempo de execucao e
T (n) = 4.
Ja no caso da Busca binaria, o melhor caso ocorre quando x esta exatamente na
metade do vetor A, i.e., A[(direita− esquerda)/2c
]= x. Nesse caso, o laco enquanto
e executado somente uma vez, de modo que o tempo de execucao e dado como abaixo
(veja (1.5)).
T ′(n) ≤ 4rx + 3 = 7.
Geralmente estamos interessados no tempo de execucao de pior caso do algoritmo,
isto e, o maior tempo de execucao do algoritmo dentre todas as entradas possıveis de um
dado tamanho n. A analise de pior caso e muito importante, pois limita superiormente
o tempo de execucao para qualquer entrada, garantindo que o algoritmo nunca vai
demorar mais do que esse limite. Outra razao para a analise de pior caso ser considerada
e que para alguns algoritmos, o pior caso (ou algum caso proximo do pior) ocorre com
muita frequencia. O pior caso da Busca linear a da Busca binaria ocorre quando
o elemento x a ser buscado nao se encontra no vetor A, pois a busca linear precisa
percorrer todo o vetor, e a busca binaria vai subdividir o vetor ate que nao seja mais
possıvel. No caso da busca linear, o tempo de execucao do pior caso e dado por
T (n) = 3(n+ 1) + 1 = 3n+ 4.
13
Ja a busca binaria e executada em tempo
T ′(n) ≤ 4 log n+ 3.
O tempo de execucao do caso medio de um algoritmo e a media do tempo de
execucao dentre todas as entradas possıveis de um dado tamanho n. Por exemplo, para
os algoritmos de busca, por simplicidade assuma que x esta em A. Agora considere
que quaisquer das n! permutacoes dos n elementos de A tem a mesma chance de ser
passado como o vetor de entrada. Note que, nesse caso, cada numero tem a mesma
probabilidade de estar em quaisquer das n posicoes do vetor. Assim, em media, a
posicao tx de x em A e dada por (1 + 2 + . . .+ n)/n = (n+ 1)/2. Logo, o tempo medio
de execucao da busca linear e dado por
T (n) = 3tx + 1 =3n
2+
5
2.
O tempo de execucao de caso medio da busca binaria envolve calcular a media de
rx dentre todas as ordenacoes possıveis do vetor, onde lembre-se que rx e a quantidade
de vezes que o laco e executado na busca binaria. Calcular precisamente essa media
nao e difıcil, mas vamos evitar essa tecnicalidade nesse momento, apenas mencionando
que no caso medio, o tempo de execucao da busca binaria e dado por c log n, para
alguma constante c (numero que nao e uma funcao de n).
Muitas vezes o tempo de execucao no caso medio e quase tao ruim quanto no pior
caso. No caso das buscas, vimos que a busca linear tem tempo de execucao 3n + 4
no pior caso, e (3n+ 5)/2 no caso medio, ambos da forma an+ b, para constantes a
e b. Assim, ambos possui tempo de execucao linear no tamanho da entrada. Mas e
necessario deixar claro que esse nem sempre e o caso. Por exemplo, seja n o tamanho
de um vetor que desejamos ordenar. Um algoritmo de ordenacao chamado Quicksort
tem tempo de execucao de pior caso quadratico em n (i.e., da forma an2 + bn + c,
para constantes a, b e c), mas em media o tempo gasto e da ordem de n log n, que e
muito menor que uma funcao quadratica em n para valores grandes de n. Embora o
tempo de execucao de pior caso do Quicksort seja pior do que de outros algoritmos de
ordenacao (e.g., Mergesort, Heapsort), ele e comumente utilizado, dado que seu pior
caso raramente ocorre. Por fim, vale mencionar que nem sempre e simples descrever
o que seria uma “entrada media” para um algoritmo, e analises de caso medio sao
14
geralmente mais complicadas que analises de pior caso.
1.3 Notacao assintotica
Uma abstracao que ajuda bastante na analise do tempo de execucao de algoritmos e o
estudo da taxa de crescimento de funcoes. Esse estudo nor permite comparar tempo
de execucao de algoritmos independentemente da plataforma utilizada, da linguagem
etc. Se um algoritmo leva tempo f(n) = an2 + bn + c para ser executado, onde a, b
e c sao constantes e n e o tamanho da entrada, o termo que realmente importa para
grandes valores de n e an2. Ademais, as constantes tambem podem ser desconsideradas,
de modo que o tempo de execucao nesse caso seria “da ordem de n2”. Por exemplo,
para n = 1000 e a = b = c = 2, temos an2 + bn+ c = 2000000 + 2000 + 2 = 2002002
e n2 = 1000000. Estamos interessados no que acontece com f(n) quando n tende a
infinito, o que chamamos de analise assintotica de f(n).
1.3.1 Notacoes O, Ω e Θ
Dado um inteiro positivo n e uma funcao f(n), que aqui tem o papel do tempo de
execucao de algoritmos, comecamos definindo as notacoes assintoticas O(f(n)) e Ω(f(n))
abaixo, que nos ajudaram, respectivamente, a limitar superiormente e inferiormente o
tempo de execucao dos algoritmos.
Definicao 1.1: Notacoes O e Ω
Dadas funcoes positivas f(n) e g(n), dizemos que
• f(n) = O(g(n)) se existem constantes positivas C e n0 tais que f(n) ≤ Cg(n)
para todo n ≥ n0;
• f(n) = Ω(g(n)) se existem constantes positivas c e n0 tais que cg(n) ≤ f(n)
para todo n ≥ n0.
Em outras palavras, f(n) = O(g(n)) quando para todo n suficientemente grande, a
15
funcao f(n) e limitada superiormente por Cg(n). Dizemos que f(n) e no maximo da
ordem de g(n). Por outro lado, f(n) = Ω(g(n)) quando para todo n suficientemente
grande, f(n) e limitada inferiormente por cg(n). Dizemos que f(n) e no mınimo da
ordem de g(n).
Dada uma funcao f(n), se f(n) = O(g(n)) e f(n) = Ω(g(n)), entao dizemos que
f(n) = Θ(g(n)). Formalmente,
Definicao 1.2: Notacao Θ
Dadas funcoes positivas f(n) e g(n), dizemos que f(n) = Θ(g(n)) se existem
constantes positivas c, C e n0 tais que cg(n) ≤ f(n) ≤ Cg(n) para todo n ≥ n0.
Note que podemos utilizar as tres notacoes acima para analisar tempos de execucao
de melhor caso, pior caso ou caso medio de algoritmos. No que segue assumimos que n e
grande suficiente. Se um algoritmo tem tempo de execucao T (n) no pior caso e sabemos
que T (n) = O(n log n), entao, para a instancia de tamanho n em que o algoritmo
e mais lento, ele leva tempo no maximo Cn log n, onde C e constante. Portanto,
podemos concluir que para qualquer instancia de tamanho n o algoritmo leva tempo
no maximo da ordem de n log n. Por outro lado, se dizemos que T (n) = Ω(n log n) e o
tempo de execucao de pior caso de um algoritmo, entao nao temos muita informacao
util. Sabemos somente que para a instancia In de tamanho n em que o algoritmo e
mais lento, o algoritmo leva tempo pelo menos Cn log n, onde C e constante. Mas isso
nao implica nada sobre quaisquer outras instancias do algoritmo, nem informa nada a
respeito do tempo maximo de uma execucao para a instancia In.
Analisando agora o tempo de execucao T (n) de melhor caso de um algoritmo,
uma informacao importante e mostrar que T (n) = Ω(g(n)), pois isso afirma que
para a instancia de tamanho n em que o algoritmo e mais rapido, ele leva tempo no
mınimo cg(n), onde c e constante. Assim, para qualquer instancia de tamanho n o
algoritmo leva tempo no mınimo da ordem de g(n). Porem, se sabemos somente que
T (n) = O(g(n), a unica informacao que temos e que para a instancia de tamanho n em
que o algoritmo e mais rapido, ele leva tempo pelo menos Cn log n, onde C e constante.
Isso nao diz nada sobre o tempo de execucao do algoritmo para outras instancias.
Vamos trabalhar com alguns exemplos para entender melhor as notacoes O, Ω e Θ.
16
Fato 1.3
Se f(n) = 10n2 + 5n+ 3, entao f(n) = Θ(n2).
Demonstracao. Para mostrar que f(n) = Θ(n2), vamos mostrar que f(n) = O(n2) e
f(n) = Ω(n2). Verifiquemos primeiramente que f(n) = O(n2). Se tomarmos n0 = 1,
entao note que como queremos f(n) ≤ Cn para todo n ≥ n0 = 1, queremos obter um
C tal que 10n2 + 5n+ 3 ≤ Cn2. Mas entao basta que
C ≥ 10n2 + 5n+ 3
n2= 10 +
5
n+
3
n2.
Mas para n ≥ 1, temos
10 +5
n+
3
n2≤ 10 + 5 + 3 = 18.
Logo, tomando n0 = 1 e C = 18, temos
C = 18 = 10 + 5 + 3 ≥ 10 +5
n+
3
n2=
10n2 + 5n+ 3
n2,
como querıamos. Logo, concluımos que f(n) ≤ Cn2 para todo n ≥ n0.
Agora vamos verificar que f(n) = Ω(n2). Se tomarmos n0 = 1, entao note que
como queremos f(n) ≥ cn para todo n ≥ n0 = 1, queremos obter um C tal que
10n2 + 5n+ 3 ≥ cn2. Mas entao basta que
c ≤ 10 +5
n+
3
n2.
Mas para n ≥ 1, temos
10 +5
n+
3
n2≥ 10.
Logo, tomando n0 = 1 e c = 10, concluımos que f(n) ≥ cn2 para todo n ≥ n0. Como
mostramos que f(n) = O(n2) e f(n) = Ω(n2), entao concluımos que f(n) = Θ(n2).
Perceba que na prova do Fato 1.3 tracamos uma simples estrategia para encontrar
um valor apropriado para C. Os valores para n0 escolhidos nos dois casos foi 1, mas
17
algumas vezes e mais conveniente ou somente e possivel escolher um valor maior para n0.
Considere o exemplo a seguir.
Fato 1.4
Se f(n) = 5 log n+√n, entao f(n) = O(
√n).
Demonstracao. Comece percebendo que nao e difıcil ver que f(n) = O(n), pois sabemos
que log n e√n sao menores que n para valores grandes de n (na verdade, para qualquer
n ≥ 2). Porem, e possıvel melhorar esse limitante para f(n) = O(√n). De fato, basta
obter C e n0 tal que para n ≥ n0 temos 5 log n+√n ≤ C
√n. Logo, queremos que
C ≥ 5 log n√n
+ 1. (1.6)
Mas nesse caso precisamos ter cuidado ao escolhe n0, pois com n0 = 1, temos
5(log 1)/√
5 + 1 = 1, o que pode nos levar a pensar que C = 1 e uma boa escolha
para C. Com essa escolha, precisamos que a desigualdade (1.6) seja valida para todo
n ≥ n0 = 1. Porem, se n = 2, entao (1.6) nao e valida, uma vez que 5(log 2)/√
2 > 1.
Para facilitar, podemos observar que para todo n ≥ 16, temos (log n)/√n ≤ 1, de
modo que a desigualdade (1.6) e valida, i.e., (5 log n)/√n+ 1 ≤ 6. Portanto, tomando
n0 = 16 e C = 6, mostramos que f(n) = O(√n).
Lembre-se que podem existir diversas possibilidades de escolha para n0 e C. Por
exemplo, na prova do Fato 1.4, usar n0 = 3454 e C = 2 tambem funciona para mostrar
que 5 log n+√n = O(
√n). Outra escolha possıvel seria n = 1 e C = 11. Nao e difıcil
mostrar que f(n) = Ω(√n).
Outros exemplos de limitantes seguem abaixo, onde a e b sao inteiros positivos.
• loga n = Θ(logb n).
• loga n = O(nε) para qualquer ε > 0.
• (n+ a)b = Θ(nb).
• 2n+a = Θ(2n).
18
• 2an 6= O(2n).
• 7n2 6= O(n).
Vamos utilizar a definicao da notacao assintotica para mostrar que 7n2 6= O(n).
Fato 1.5
Se f(n) = 7n2 entao f(n) 6= O(n)
Demonstracao. Lembre que f(n) = O(g(n)) se existem constantes positivas C e n0
tais que se n ≥ n0, entao 0 ≤ f(n) ≤ Cg(n). Suponha por contradicao que 7n2 = O(n),
i.e., existem constantes positivas C e n0 tais que se n ≥ n0, entao
7n2 ≤ Cn.
Nosso objetivo agora e chegar a uma contradicao. Mas note que para todo n ≥ n0,
temos
n ≤ C/7,
um absurdo, pois claramente isso nao e verdade para valores de n maiores que C/7, mas
sabemos que esse fato deveria valer para todo n ≥ n0, inclusive valores de n maiores
que C/7.
Relacoes entre as notacoes O, Ω e Θ
No teorema enunciado a seguir descrevemos propriedades importantes acerca das
relacoes entre as notacoes assintoticas O, Ω e Θ.
Teorema 1.6: Propriedades de notacoes assintoticas
Sejam f(n), g(n) e h(n) funcoes positivas. Temos que
1. f(n) = Θ(f(n));
2. Se f(n) = Θ(g(n)) se e somente se g(n) = Θ(f(n));
3. Se f(n) = O(g(n)) se e somente se g(n) = Ω(f(n));
19
4. Se f(n) = O(g(n)) e g(n) = Θ(h(n)), entao f(n) = O(h(n));
O mesmo vale substituindo O por Ω;
5. Se f(n) = Θ(g(n)) e g(n) = O(h(n)), entao f(n) = O(h(n));
O mesmo vale substituindo O por Ω;
6. f(n) = O(g(n) + h(n)
)se e somente se f(n) = O(g(n)) +O(h(n));
O mesmo vale substituindo O por Ω ou substituindo O por Θ;
7. Se f(n) = O(g(n)) e g(n) = O(h(n)), entao f(n) = O(h(n));
O mesmo vale substituindo O por Ω ou substituindo O por Θ.
Demonstracao. Vamos mostrar que os itens enunciados no teorema sao validos.
Item 1. Esse item e simples, pois para qualquer n ≥ 1 temos que f(n) = 1 · f(n), de
modo que para n0 = 1, c = 1 e C = 1 temos que para todo n ≥ n0 vale que
cf(n) ≤ f(n) ≤ Cf(n),
de onde concluımos que f(n) = Θ(f(n)).
Item 2. Note que basta provar uma das implicacoes (a prova da outra implicacao e
identica). Provaremos que se f(n) = Θ(g(n)) entao g(n) = Θ(f(n)) (o outro lado
da implicacao e analogo). Se f(n) = Θ(g(n)), entao temos que existem constantes
positivas c, C e n0 tais que
cg(n) ≤ f(n) ≤ Cg(n) (1.7)
para todo n ≥ n0. Assim, analisando as desigualdades em (1.8), concluımos que(1
C
)f(n) ≤ g(n) ≤
(1
c
)f(n)
para todo n ≥ n0. Portanto, existem constantes n0, c′ = 1/C e C ′ = 1/c tal que
c′f(n) ≤ g(n) ≤ C ′f(n) para todo n ≥ n0.
Item 3. Vamos provar uma das implicacoes (a prova da outra implicacao e analoga).
20
Se f(n) = O(g(n)), entao temos que existem constantes positivas C e n0 tais que
f(n) ≤ Cg(n) (1.8)
para todo n ≥ n0. Portanto, temos que g(n) ≥ (1/C)f(n) para todo n ≥ n0, de onde
concluımos que g(n) = Ω(f(n)).
Item 4.
Item 5.
Note que se uma funcao f(n) e uma soma de funcoes logarıtmicas, exponenciais e
polinomios em n, entao sempre temos que f(n) vai ser Θ(g(n), onde g(n) e o termo de
f(n) com maior taxa de crescimento (desconsiderando constantes). Por exemplo, se
f(n) = 4 log n+ 1000(log n)100 +√n+ n3/10 + 5n5 + n8/27,
entao sabemos que f(n) = Θ(n8).
1.3.2 Notacoes o e ω
Apesar das notacoes assintoticas descritas ate aqui fornecerem informacoes importantes
acerca do crescimento das funcoes, muitas vezes elas nao sao tao precisas quanto
gostarıamos. Por exemplo, temos 2n2 = O(n2) e 4n = O(n2). Apesar dessas duas
funcoes terem ordem de complexidade O(n2), somente a primeira e “justa”. para
descrever melhor essa situacao, temos as notacoes o-pequeno e ω-pequeno. Dizemos que
Definicao 1.7: Notacoes o e ω
Dadas funcoes f(n) e g(n), dizemos que
• f(n) = o(g(n)) se para toda constante c > 0 existe n0 > 0 tal que 0 ≤f(n) < cg(n) para todo n ≥ n0;
• f(n) = ω(g(n)) se para toda constante C > 0 existe n0 > 0 tal que
f(n) > Cg(n) ≥ 0 para todo n ≥ n0.
21
Por exemplo, 2n = o(n2) mas 2n2 6= o(n2). O que acontece e que se f(n) = o(g(n)),
entao f(n) e insignificante com relacao a g(n) para n grande. Alternativamente,
podemos dizer que f(n) = o(g(n)) quando limn→∞(f(n)/g(n)) = 0. Por exemplo,
2n2 = ω(n) mas 2n2 6= ω(n2).
Vamos ver um exemplo para ilustrar como podemos mostrar que f(n) = o(g(n))
para duas funcoes f e g.
Fato 1.8
10n+ 3 log n = o(n2).
Demonstracao. Seja f(n) = 10n + 3 log n. Precisamos mostrar que para qualquer
constante positiva c existe um n0 tal que 10n+ 3 log n < cn2 para todo n ≥ n0. Assim,
seja c > 0 uma constante qualquer. Primeiramente note que 10n+ 3 log n < 13n e que
se n > 13/c, entao
10n+ 3 log n < 13n < cn.
Portanto, acabamos de provar o que precisavamos (com n0 = (13/c) + 1).
Note que com uma analise similar a feita na prova acima podemos provar que
10n + 3 log n = o(n1+ε) para todo ε > 0. Basta que, para todo c > 0, facamos
n > (13/c)1/ε.
Outros exemplos de limitantes seguem abaixo, onde a e b sao inteiros positivos.
• loga n 6= o(logb n).
• loga n 6= ω(logb n).
• loga n = o(nε) para qualquer ε > 0.
• an = o(n1+ε) para qualquer ε > 0.
• an = ω(n1−ε) para qualquer ε > 0.
• 1000n2 = o((log n)n2).
22
1.3.3 Relacoes entre as notacoes assintoticas
Muitas dessas comparacoes assintoticas tem propriedades importantes. No que segue
sejam f(n), g(n) e h(n) assintoticamente positivas. Todas as cinco notacoes descritas
sao transitivas, e.g., se f(n) = O(g(n)) e g(n) = O(h(n)), entao temos f(n) = O(h(n)).
Reflexividade vale para O, Ω e Θ, e.g., f(n) = O(f(n)). Temos tambem a simetria com
a notacao Θ, i.e., f(n) = Θ(g(n)) se e somente se g(n) = Θ(f(n)). Por fim, a simetria
transposta vale para os pares O,Ω e o, ω, i.e., f(n) = O(g(n)) se e somente se
g(n) = Ω(f(n)), e f(n) = o(g(n)) se e somente se g(n) = ω(f(n)).
23
24
Capıtulo
2Recursividade / Divisao e Conquista
Ao desenvolver um algoritmo, muitas vezes precisamos executar uma tarefa repe-
tidamente, utilizando para isso estruturas de repeticao para ou enquanto. Algu-
mas vezes precisamos tomar decisoes condicionais, utilizando operacoes da forma
“se...senao...entao” para isso. Em geral, todas essas operacoes sao rapidamente assi-
miladas pois fazem parte do cotidiano de qualquer pessoa, dado que muitas vezes
precisamos tomar decisoes condicionais ou executar tarefas repetidamente. Porem, para
desenvolver alguns algoritmos sera necessario fazer uso da recursao. Essa tecnica de
solucao de problemas resolve problemas grandes atraves de sua reducao em problemas
menores do mesmo tipo, que por sua vez sao reduzidos e assim por diante, ate que
os problemas sejam tao pequenos que podem ser resolvidos diretamente. Diversos
problemas tem a seguinte caracterıstica: toda instancia do problema contem uma
instancia menor do mesmo problema (estrutura recursiva). Esses problemas podem ser
resolvidos com os passos a seguir.
(i) Se a instancia for suficientemente pequena, resolva o problema diretamente,
(ii) caso contrario, divida a instancia em instancias menores, resolva-as utilizando
os passos (i) e (ii) e retorne a instancia original.
Um algoritmo que aplica o metodo acima e chamado de algoritmo recursivo. No que
segue, vamos analisar alguns exemplos de algoritmos recursivos para entender melhor
como funciona a recursividade.
2.1 Algoritmos recursivos
Uma boa forma de entender melhor a recursividade e atraves da analise de alguns
exemplos. Vamos mostrar como executar procedimentos recursivos para calcular o
fatorial de um numero e para encontrar um elemento em um vetor ordenado.
2.1.1 Fatorial
Uma funcao bem conhecida na matematica e o fatorial de um inteiro nao negativo
n. A funcao fatorial, denotada por n!, e definida como o produto dos inteiros entre
1 e n, onde assumimos 0! = 1. Mas note que podemos definir n! da seguinte forma
recursiva:
• 0! = 1,
• n! = n · (n− 1)! para n > 0.
Essa definicao inspira o seguinte simples algoritmo recursivo.
Algoritmo 6: Fatorial(n)
1 se n = 0 entao
2 retorna 1
3 senao
4 retorna n · Fatorial(n− 1)
Por exemplo, ao chamar “Fatorial(3)” o algoritmo vai executar a linha 4, retor-
nando “3 ·Fatorial(2)”. Nesse ponto o computador salva o estado atual na “pilha de
recursao” e faz uma chamada a “Fatorial(2)”, que vai executar a linha 4 novamente
e retornar “2 · Fatorial(1)”, Novamente o estado atual e salvo na pilha de recursao e
uma chamada a “Fatorial(1)” e realizada. Essa chamada recursiva sera a ultima,
26
pois nesse ponto a linha 2 sera executada e essa chamada retorna 1. Assim, a pilha de
recursao comeca a ser desempilhada, e o resultado final sera 3 · (2 · (1 · 1)).
Pelo exemplo do paragrafo anterior, conseguimos perceber que a execucao de um
programa recursivo precisa salvar varios estados do programa ao mesmo tempo, de
modo que isso aumenta o uso de memoria. Por outro lado, muitas vezes uma solucao
recursiva e bem mais simples que uma iterativa correspondente.
2.1.2 Busca binaria
Considere um vetor ordenado (ordem crescente) A com n elementos. Nesse caso, po-
demos facilmente desenvolver uma variacao recursiva do algoritmo Busca binaria que
consegue realizar (como na versao iterativa) a busca por uma chave x em A em tempo
O(log n) no pior caso. A estrategia e muito simples. Basta verificar se A[bn/2c] = x
e realizar o seguinte: se A[bn/2c] = x, entao a busca esta encerrada. Caso contrario,
se x < A[bn/2c], entao basta verificar recursivamente o vetor A[1, . . . , bn/2c − 1]. Se
x > A[bn/2c], entao verifica-se recursivamente o vetor A[bn/2c+ 1, . . . , n]. Como esse
procedimento analisa, passo a passo, somente metade do tamanho do vetor do passo
anterior, seu tempo de execucao e O(log n). Para executar o algoritmo abaixo basta
fazer Busca binaria - Recursiva(A[1..n], 1, n, x).
Algoritmo 7: Busca binaria - Recursiva(A[1..n], inicio, fim, x)
1 se inicio > fim entao
2 retorna −1
3 meio = inicio+⌊fim−inicio
2
⌋4 se A[meio] == x entao
5 retorna meio
6 senao se x < A[meio] entao
7 Busca binaria - Recursiva(A[1..n], inicio, meio− 1, x)
8 senao
9 Busca binaria - Recursiva(A[1..n], meio+ 1, fim, x)
27
2.1.3 Algoritmos recursivos × algoritmos iterativos
Mas quando utilizar um algoritmo recursivo ou um algoritmo iterativo? Vamos
discutir algumas vantagens e desvantagens de cada tipo de procedimento.
A utilizacao de um algoritmo recursivo tem a vantagem de, em geral, ser simples
e oferecer codigos claros e concisos. Assim, alguns problemas que podem parecer
complexos de inıcio, acabam tendo uma solucao simples e elegante, enquanto que
algoritmos iterativos longos requerem experiencia por parte do programador para
serem entendidos. Por outro lado, uma solucao recursiva pode ocupar muita memoria,
dado que o computador precisa manter varios estados do algoritmo gravados na pilha
de execucao do programa. Muitas pessoas acreditam que algoritmos recursivos sao,
em geral, mais lentos do que algoritmos iterativos para o mesmo problema, mas a
verdade e que isso depende muito do compilador utilizado e do problema em si. Alguns
compiladores conseguem lidar de forma rapida com as chamadas a funcoes e com o
gerenciamento da pilha de execucao.
Algoritmos recursivos eliminam a necessidade de se manter o controle sobre diversas
variaveis que possam existir em um algoritmo iterativo para o mesmo problema. Porem,
pequenos erros de implementacao podem levar a infinitas chamadas recursivas, de
modo que o programa nao encerraria sua execucao.
Nem sempre a simplicidade de um algoritmo recursivo justifica o seu uso. Um
exemplo claro e dado pelo problema de se calcular termos da sequencia de Fibonacci
(1, 1, 2, 3, 5, 8, 13, 21, 34, . . .). O seguinte algoritmo ilustra quao ineficiente um algoritmo
recursivo pode ser.
Algoritmo 8: Fibonacci(n)
1 se n ≤ 2 entao
2 retorna 1
3 retorna Fibonacci(n− 1) + Fibonacci(n− 2)
28
Apesar de sua simplicidade, o procedimento acima e muito ineficiente. Seu tempo
de execucao e dado por T (n) = T (n − 1) + T (n − 2) + 1, que e exponencial em n.
E possıvel implementar um algoritmo iterativo simples que e executado em tempo
linear. Isso ocorre porque na versao recursiva muito trabalho repetido e feito pelo
algoritmo. De fato, quando Fibonacci(n− 1) + Fibonacci(n− 2) e executado, alem
da chamada a Fibonacci(n− 2) que e feita, a chamada a Fibonacci (n− 1) fara
mais uma chamada a Fibonacci (n− 2), mesmo que ele ja tenho sido calculado antes,
e esse fenomeno cresce exponencialmente ate chegar a base da recursao.
Na Parte III veremos diversos algoritmos recursivos para resolver o problema de
ordenacao dos elementos de um vetor. Ao longo deste livro muitos outros algoritmos
recursivos serao discutidos.
2.2 Divisao e conquista
Divisao e conquista e um paradigma para o desenvolvimento de algoritmos que faz uso
da recursividade. Para resolver um problema utilizando esse paradigma, seguimos os
tres seguintes passos.
• O problema e dividido em subproblemas menores;
• Os subproblemas menores sao resolvidos recursivamente: cada um desses
subproblemas menores e divido em subproblemas ainda menores, a menos
que sejam tao pequenos a ponto de ser simples resolve-los diretamente;
• Solucoes dos subproblemas menores sao combinadas para formar uma solucao
do problema inicial.
Essa parte ainda sera escrita...
29
30
Capıtulo
3Metodos para solucao de equacoes de
recorrencia
Relacoes como T (n) = 2T (n/2) +n ou T (n) = T (n/3) +T (n/4) + 3 log n sao chamadas
de recorrencias, definidas como equacoes ou inequacoes que descrevem uma funcao em
termos de seus valores para entradas menores. Apresentaremos quatro metodos para
resolucao de recorrencias: (i) iterativo, (ii) arvore de recorrencia, (iii) substituicao e
(iv) mestre.
Antes de discutirmos os metodos de resolucao de recorrencias, apresentamos na
proxima secao algumas relacoes matematicas e somas que surgem com frequencia na
resolucao de recorrencias. O leitor familiarizado com os conceitos apresentados deve
seguir para a secao seguinte, que explica o metodo iterativo.
3.1 Logaritmos e somas
Como recorrencias sao funcoes definidas recursivamente em termos da propria funcao
para valores menores, se expandirmos recorrencias ate que cheguemos ao caso base
da recursao, muitas vezes teremos realizado uma quantidade logarıtmica de passos
recursivos. Assim, e natural que termos logarıtmicos aparecam durante a resolucao
de recorrencias. Assim, abaixo listamos as propriedades mais comuns envolvendo
manipulacao de logaritmos.
Fato 3.1
Dados numeros reais a, b, c ≥ 1, as seguintes igualdades sao validas.
(i) aloga b = b.
(ii) logc(ab) = logc a+ logc b.
(iii) logc(a/b) = logc a− logc b.
(iv) logc(ab) = b logc a.
(v) logb a = logc alogc b
.
(vi) logb a = 1loga b
.
(vii) alogc b = blogc a.
Demonstracao. Por definicao, temos logb a = x se e somente se bx = a. No que segue
vamos provar cada uma das identidades descritas no enunciado.
(i) aloga b = b. Segue diretamente da definicao de logaritmo, uma vez que ax = b se e
somente se x = loga b.
(ii) logc(ab) = logc a+ logc b. Como a, b e c sao positivos, existem numeros k e ` tais
que a = ck e b = c`. Assim, temos
logc(ab) = logc(ckc`) = logc
(ck+`
)= k + ` = logc a+ logc b,
onde as duas ultimas desigualdades seguem da definicao de logaritmos.
(iii) logc(a/b) = logc a − logc b. Como a, b e c sao positivos, existem numeros k e `
tais que a = ck e b = c`. Assim, temos
logc(ab) = logc(ck/c`) = logc
(ck−`
)= k − ` = logc a− logc b.
(iv) logc(ab) = b logc a. Como a, b e c sao positivos, podemos escrever a = ck para
32
algum numero real k. Assim, temos
logc(ab) = logc(c
kb) = kb = b logc a.
(v) logb a = logc alogc b
. Vamos mostrar que logc a = (logb a)(logc b). Note que, pela
identidade (i), temos logc a = logc
(blogb a
). Assim, usando a identidade (iii),
temos que logc a = (logb a)(logc b).
(vi) logb a = 1loga b
. Vamos somente usar (v) e o fato de que loga a = 1:
logb a =loga a
loga b=
1
loga b.
(vii) alogc b = blogc a. Esse fato segue das identidades (i), (v) e (vi). De fato,
alogc b = a(loga b)/(loga c)
=(aloga b
)1/(loga c)
= b1/(loga c)
= blogc a.
Vamos agora verificar como se obter formulas para algumas somas que aparecem
com frequencia em analise de algoritmos, que sao as somas dos termos de progressoes
aritmeticas e a soma dos termos de progressoes geometricas.
Uma progressao aritmetica (PA) (a1, a2, . . . , an) com razao r e uma sequencia de
numeros que contem um termo inicial a1 e todos os outros termos ai (com 2 ≤ i ≤ n)
sao definidos como ai = a1 + (i− 1)r. Assim, a soma dos termos dessa PA e dada por∑ni=1 ai =
∑ni=1(a1 + (i− 1)r).
Uma progressao geometrica (PG) (b1, b2, . . . , bn) com razao q e uma sequencia de
numeros que contem um termo inicial b1 e todos os outros termos bi (com 2 ≤ i ≤ n)
sao definidos como bi = b1qi−1. Assim, a soma dos termos dessa PG e dada por∑n
i=1 bi =∑n
i=1(b1qi−1).
33
Teorema 3.2
Considere uma progressao aritmetica∑n
i=1 an com razao r e uma progressao
geometrica∑n
i=1 bn com razao q. A soma dos termos da progressao aritmetica
e dada por (a1+an)n2
e a soma dos termos da progressao geometrica e dada pora1(qn−1)
q−1 .
Demonstracao. Vamos comecar com a progressao aritmetica. A primeira observacao
importante e que para todo inteiro positivo k temos que
1 + 2 + . . .+ k = k(k + 1)/2. (3.1)
Esse fato pode facilmente ser provado por inducao em n. Agora considere a soma∑ni=1(a1 + (i− 1)r). Temos que
n∑i=1
(a1 + (i− 1)r
)= a1n+ r(1 + 2 + . . .+ (n− 1))
= a1n+rn(n− 1)
2
= n(a1 + (a1 + r(n− 1))
)=n(a1 + an)
2,
onde na segunda igualdade utilizamos (3.1).
Resta verificar a formula para a soma dos termos da progressao geometrica S =∑ni=1(b1q
i−1). Note que temos
qS = b1(q + q2 + q3 + . . .+ qn−1 + qn), e
S = b1(1 + q + q2 + . . .+ qn−2 + qn−1).
Portanto, subtraindo S de qS obtemos (q − 1)S = b1(qn − 1), de onde concluımos que
S =b1(q
n − 1)
q − 1.
34
3.2 Metodo iterativo
Esse metodo consiste simplesmente em expandir a recorrencia ate se chegar no caso
base, que sabemos como calcular diretamente. Em geral, vamos utilizar como caso
base T (1) = 1.
Como um primeiro exemplo, considere T (n) = T (n/2) + 1, que e o tempo de
execucao do algoritmo de busca binaria.
T (n) = T (n/2) + 1
= (T ((n/2)/2) + 1) + 1 = T (n/22) + 2
= (T ((n/22)/2) + 1) + 2 = T (n/23) + 3
...
= T (n/2i) + i.
Sabemos que T (1) = 1. Entao, se tomarmos i = log n, temos
T (n) = T (n/2logn) + log n
= T (1) + log n
= Θ(log n).
Para um segundo exemplo, considere T (n) = 2T (n/2) + n. Portanto,
T (n) = 2T (n/2) + n
= 2(2T (n/4) + n/2
)+ n = 22T (n/22) + 2n
= 23T (n/23) + 3n
...
= 2iT (n/2i) + in.
35
Fazendo i = log n, temos
T (n) = 2lognT (n/2logn) + n log n
= nT (1) + n log n
= n+ n log n = Θ(n log n).
Como veremos na Parte III, Insertion sort e Merge sort sao dois algoritmos
que resolvem o problema de ordenacao e tem, respectivamente, tempos de execucao de
pior caso T1(n) = Θ(n2) e T2(n) = 2T (n/2) + n. Como acabamos de verificar, temos
T2(n) = Θ(n log n), de modo que podemos concluir que, no pior caso, Merge sort e
assintoticamente mais eficiente que Insertion sort.
Analisaremos agora um ultimo exemplo, que representa um algoritmo que sempre
divide o problema em 2 subproblemas de tamanho n/3 e cada chamada recursiva e
executada em tempo constante. Seja T (n) = 2T (n/3)+1. Seguindo a mesma estrategia
dos exemplos anteriores, obtemos o seguinte.
T (n) = 2T (n/3) + 1
= 2(2T (n/32) + 1
)+ 1 = 22T (n/32) + (1 + 2)
= 23T (n/33) + (1 + 2 + 22)
...
= 2iT (n/3i) +i−1∑j=0
2j
= 2iT (n/3i) + 2i − 1
Fazendo i = log3 n, temos T (n/3log3 n) = 1, de onde concluımos que
T (n) = 2 · 2log3 n − 1
= 2(2log2 n
)1/ log2 3 − 1
= 2n1/ log2 3 − 1
= Θ(n1/ log2 3).
36
3.2.1 Limitantes assintoticos inferiores e superiores
Se quisermos apenas provar que T (n) = O(f(n)) em vez de Θ(f(n)), podemos utilizar
limitantes superiores em vez de igualdades. Analogamente, para mostrar que T (n) =
Ω(f(n)), podemos utilizar limitantes inferiores em vez de igualdades. Por exemplo,
para T (n) = 2T (n/3) + 1, se quisermos mostrar somente que T (n) = Ω(n1/ log2 3),
podemos simplificar a analise. O ponto principal e, ao expandir a recorrencia T (n),
entender qual e o termo que “domina” assintoticamente T (n), i.e., qual e o termo que
determina a ordem de complexidade de T (n).
T (n) = 2T (n/3) + 1
= 2(2T (n/32) + 1
)+ 1 ≥ 22T (n/32) + 2
≥ 23T (n/33) + 3
...
≥ 2iT (n/3i) + i
Fazendo i = log3 n, temos T (n/3log3 n) = 1, de onde concluımos que
T (n) ≥ 2log3 n + log3 n
= n1/ log2 3 + log3 n
= Ω(n1/ log2 3).
Nem sempre o metodo iterativo para resolucao de recorrencias funciona bem.
Quando o tempo de execucao de um algoritmo e descrito por uma recorrencia nao tao
balanceada como a dos exemplos dados, pode ser difıcil executar esse metodo. Outro
ponto fraco e que rapidamente os calculos podem ficar complicados.
3.3 Metodo da substituicao
Esse metodo consiste simplesmente em “adivinhar” a solucao e provar por inducao
matematica que o palpite dado e, de fato, a solucao para a recorrencia. Mas como
adivinhar uma solucao? Podemos utilizar o metodo da arvore de recorrencia visto
a seguir para estimar um valor, mas algumas vezes sera necessario experiencia e
37
criatividade.
Considere um algoritmo com tempo de execucao T (n) = T (bn/2c) + T (dn/2e) + n.
Por simplicidade, vamos assumir agora que n e uma potencia de 2. Logo, podemos
considerar T (n) = 2T (n/2)+n, pois temos que n/2i e um inteiro para todo 1 ≤ i ≤ log n.
Mostraremos que T (n) = O(n log n).
Para isso, provaremos por inducao que T (n) ≤ cn log n para c ≥ 2 e n ≥ 2,
i.e., existem constantes c = 2, n0 = 2 tais que se n ≥ n0, entao T (n) ≤ cn log n,
que implica T (n) = O(n log n). Via de regra assumiremos T (1) = 1, a menos que
indiquemos algo diferente. Note que se n = 1 for o caso base da inducao, entao temos
um problema nesse exemplo, pois 1 > 0 = cn log n para n = 1. Porem, em analise
assintotica estamos preocupados somente com valores grandes de n. Assim, como
T (2) = 2T (1) + 2 = 4 ≤ c · 2 · log 2 para c ≥ 2, vamos assumir que n ≥ 2, onde a
base da inducao que vamos realizar e n = 2. Suponha que para 2 ≤ m < n temos
T (m) ≤ cn log n. Vamos mostrar que T (n) ≤ cn log n.
T (n) = 2T (n/2) + n
≤ 2(c(n/2) log(n/2)
)+ n
= cn log n− cn+ n
≤ cn log n.
Portanto, mostramos que T (n) ≤ cn log n para c ≥ 2 e todo n ≥ 2, de onde concluımos
que T (n) = O(n log n).
3.3.1 Desconsiderando pisos e tetos
Vimos que T (n) = T (bn/2c) +T (dn/2e) +n = Θ(n log n) sempre que n e uma potencia
de 2. Mostraremos a seguir que podemos sempre assumir que n e uma potencia
de 2. Vamos observar agora que de fato podemos desconsiderar o piso e o teto em
T (n) = T (bn/2c) + T (dn/2e) + n. Suponha que n ≥ 3 nao e uma potencia de 2. Entao
38
existe um inteiro k ≥ 2 tal que 2k−1 < n < 2k. Portanto,
T (n) ≤ T (2k) ≤ d2k log(2k)
= (2d)2k−1 log(2 · 2k−1)
< (2d)n(log 2 + log n)
< (2d)n(log n+ log n)
= (4d)n log n.
Similarmente,
T (n) ≥ T (2k−1) ≥ d′2k−1 log(2k−1)
=d′
22k(log(2k)− 1)
>d′
2n
(log n− 9 log n
10
)=
(d′
20
)n log n.
Como existem constantes d′/20 e 4d tais que para todo n ≥ 3 temos (d′/20)n log n ≤T (n) ≤ (4d)n log n, entao T (n) = Θ(n log n). Logo, e suficiente ter considerado somente
valores de n que sao potencias de 2.
Analises semelhantes funcionam para a grande maioria das recorrencias consideradas
em analise de algoritmos. Em particular, e facil mostrar que podemos desconsiderar
pisos e tetos em recorrencias do tipo T (n) = a(T (bn/bc) + T (dn/ce)) + f(n) para
constantes a > 0 e b, c > 1.
Portanto, geralmente vamos assumir que n e potencia de algum inteiro positivo,
sempre que for conveniente para a analise. Assim, em geral desconsideraremos pisos e
tetos.
3.3.2 Diversas formas de obter o mesmo resultado
Podem existir diversas formas de encontrar um limitante assintotico utilizando inducao.
Lembre-se que anteriormente mostramos que T (n) ≤ dn log n para d ≥ 2 e a base de
nossa inducao era n = 2. Mostraremos agora que T (n) = O(n log n) provando que
39
T (n) ≤ n log n+ n. A base da inducao nesse caso e T (1) = 1 ≤ 1 log 1 + 1. Suponha
que para todo 2 ≤ m < n temos T (m) ≤ m logm+m. Assim,
T (n) = 2T (n/2) + n
≤ 2((n/2) log(n/2) + n/2
)+ n
= n log(n/2) + 2n
= n log n− n+ 2n
= n log n+ n.
Logo, mostramos que T (n) = O(n log n+ n) = O(n log n).
Uma observacao importante e que no passo indutivo e necessario provar exatamente
o que foi suposto, com a mesma constante. Por exemplo, se supormos T (m) ≤ cm logm
e mostrarmos no passo indutivo que T (n) ≤ cn log n+ 1, isso nao implica que T (n) =
O(n log n).
Vimos que se T (n) = 2T (n/2) +n, entao temos T (n) = O(n log n). Porem esse fato
nao indica que nao podemos diminuir ainda mais esse limite. Para garantir que a ordem
de grandeza de T (n) e n log n, precisamos mostrar que T (n) = Ω(n log n). Utilizando
o metodo da substituicao, mostraremos que T (n) ≥ n log n− n, de onde concluımos
que T (n) = Ω(n log n). A base da inducao nesse caso e T (1) = 1 ≥ n log n− n para
n = 1. Suponha que para todo 2 ≤ m < n temos T (m) ≥ m logm−m. Assim,
T (n) = 2T (n/2) + n
≥ 2((n/2) log(n/2) + n/2
)− n
= n log(n/2)
= n log n− n.
Portanto, mostramos que T (n) = Ω(n log n− n) = Ω(n log n).
3.3.3 Ajustando os palpites
Algumas vezes quando queremos provar que T (n) = O(f(n)
)para alguma funcao f(n),
podemos ter problemas para obter exito caso nosso palpite esteja errado. Porem, e
possıvel que tenhamos de fato T (n) = O(f(n)
)mas o palpite precise de um leve ajuste.
40
Considere T (n) = 3T (n/3) + 1. Podemos imaginar que esse e o tempo de execucao
de um algoritmo recursivo que a cada passo divide o vetor em 3 partes de tamanho
n/3, e a cada chamada e executada em tempo constante. Assim, um bom palpite e
que T (n) = O(n). Vamos tentar provar que o palpite T (n) ≤ cn e correto para alguma
constante positiva c. Assim, temos
T (n) = 3T (n/3) + 1
≤ cn+ 1,
que nao prova o que desejamos, pois para completar a prova por inducao precisamos
mostrar que T (n) ≤ cn (e nao cn+1, como foi feito). Porem, e verdade que T (n) = O(n),
mas o problema e que o palpite nao foi forte o suficiente. Como corriqueiro em provas
por inducao, precisamos fortalecer a hipotese indutiva. Vamos tentar agora um novo
palpite: T (n) ≤ cn− d, onde d ≥ 1/2.
T (n) = 3T (n/3) + 1
≤ 3(cn
3− d)
+ 1
= cn− 3d+ 1
≤ cn− d.
Assim, como a base T (1) = 1 ≤ c−d para c ≥ d+1, temos que T (n) = O(cn−d) = O(n).
3.3.4 Mais exemplos
Discutiremos agora alguns exemplos que nos ajudarao a entender todas as particulari-
dades que podem surgir na aplicacao do metodo da substituicao.
Exemplo 1: T (n) = 4T (n/2) + n3.
Considere n ≥ 2. Vamos provar que T (n) = Θ(n3). Primeiramente, mostraremos
que T (n) = O(n3). Para isso, vamos provar que T (n) ≤ cn3 para alguma constante
apropriada c.
Note que T (1) = 1 ≤ c · 13 desde que c ≥ 1. Suponha que T (m) ≤ cm3 para todo
41
2 ≤ m < n. Assim, temos que
T (n) = 4T (n/2) + n3
≤ 4cn3
8+ n3
≤ cn3,
onde a ultima desigualdade vale sempre que c ≥ 2. Portanto, fazendo c ≥ 2, acabamos
de provar por inducao que T (n) ≤ cn3 = O(n3).
Para provar que T (n) = Ω(n3), vamos provar que T (n) ≥ dn3 para um d apropriado.
Primeiro note que T (1) = 1 ≥ d · 13 desde que d ≤ 1. Suponha que T (m) ≥ dm3 para
todo 2 ≤ m < n. Assim, temos que
T (n) = 4T (n/2) + n3
≥ 4dn3
8+ n3
≥ dn3,
onde a ultima desigualdade vale sempre que d ≤ 2. Portanto, fazendo d ≤ 1, acabamos
de provar por inducao que T (n) ≥ dn3 = Ω(n3).
Exemplo 2: T (n) = 4T (n/16) + 5√n.
Comecemos provando que T (n) ≤ c√n log n para um c apropriado. Assumimos
que n ≥ 16. Para o caso base temos T (16) = 4 + 5√
16 = 24 ≤ c√
16 log 16, onde a
ultima desigualdade vale sempre que c ≥ 3/2. Suponha que T (m) ≤ c√m logm para
todo 16 ≤ m < n. Assim,
T (n) = 4T (n/16) + 5√n
≤ 4
(c
√n√16
(log n− log 16)
)+ 5√n
= c√n log n− 4c
√n+ 5
√n
≤ c√n log n,
42
onde a ultima desigualdade vale se c ≥ 5/4. Como 3/2 > 5/4, basta fazer c = 3/2
para concluir que T (n) = O(√n log n). A prova de que T (n) = Ω(
√n log n) e similar a
prova feita para o limitante superior, de modo que a deixamos por conta do leitor.
Exemplo 3: T (n) = T (n/2) + 1.
Temos agora o caso onde T (n) e o tempo de execucao do algoritmo de busca binaria.
Mostraremos que T (n) = O(log n). Para n = 2 temos T (2) = 2 ≤ c = c log 2 sempre
que c ≥ 2. Suponha que T (m) ≤ c logm para todo 2 ≤ m < n. Logo,
T (n) = T (n/2) + 1
≤ c log n− c+ 1
≤ c log n,
onde a ultima desigualdade vale para c ≥ 1. Assim, T (n) = O(log n).
Exemplo 4: T (n) = T (bn/2c+ 2) + 1, onde assumimos T (4) = 1.
Temos agora o caso onde T (n) e muito semelhante ao tempo de execucao do
algoritmo de busca binaria. Logo, nosso palpite e que T (n) = O(log n), o que de fato e
correto. Porem, para a analise funcionar corretamente precisamos de cautela. Vamos
mostrar duas formas de analisar essa recorrencia.
Primeiro vamos mostrar que T (n) ≤ c log n para um valor de c apropriado. Seja
n ≥ 4 e note que T (4) = 1 ≤ c log 4 para c ≥ 1/2. Suponha que T (m) ≤ c logm para
43
todo 4 ≤ m < n temos
T (n) = T (bn/2c+ 2) + 1
≤ c log(n
2+ 2)
+ 1
= c log
(n+ 4
2
)+ 1
= c log(n+ 4)− c+ 1
≤ c log(3n/2)− c+ 1
= c log n+ c log 3− 2c+ 1
= c log n− c(2− log 3) + 1
≤ c log n,
onde a penultima desigualdade vale para n ≥ 8 e a ultima desigualdade vale sempre
que c ≥ 1/(2− log 3). Portanto, temos T (n) = O(log n).
Veremos agora uma outra abordagem, onde fortalecemos a hipotese de inducao.
Provaremos que T (n) ≤ c log(n− a) para um valor apropriado de a e c.
T (n) = T (bn/2c+ 2) + 1
≤ c log(n
2+ 2− a
)+ 1
= c log
(n− a
2
)+ 1
= c log(n− a)− c+ 1
≤ c log(n− a),
onde a primeira desigualdade vale para a ≥ 4 e a ultima desigualdade vale para c ≥ 1.
Assim, faca a = 4 e note que T (6) = T (5) + 1 = T (4) + 2 = 3 ≤ c log(6− 4) para todo
c ≥ 3. Portanto, fazendo a = 4 e c ≥ 3, mostramos que T (n) ≤ c log(n− a) para todo
n ≥ 6, de onde concluımos que T (n) = O(log n).
44
3.4 Metodo da arvore de recorrencia
Este e talvez o mais simples dos metodos, que consiste em analisar a arvore de recursao
do algoritmo, uma arvore onde cada no representa o custo do subproblema associado
em cada nıvel da recursao, e os filhos de cada vertice sao os subproblemas que foram
gerados na chamada recursiva associada ao vertice. Nos somamos os custos dentro de
cada nıvel, obtendo o custo total por nıvel, e entao somamos os custos de todos os
nıveis, obtendo a solucao da recorrencia.
A Figura 3.1 abaixo e uma arvore de recursao para a recorrencia T (n) = 2T (n/2)+cn
e fornece o palpite O(n log n). Na Figura 3.2 temos a arvore de recursao para a
recorrencia T (n) = 2T (n/2) + 1. Nas arvores abaixo, em cada nıvel temos dois valores,
o primeiro desses valores determina o custo do subproblema em questao, e o segundo
valor (circulado nas figuras), e o tamanho do subproblema. No lado direito temos o
custo total em cada nıvel da recursao. Por fim, no canto inferior direito das Figuras 3.1
e 3.2 temos a estimativa para o valor das recorrencias.
Figura 3.1: Arvore de recorrencia para T (n) = 2T (n/2) + cn.
45
Figura 3.2: Arvore de recorrencia para T (n) = 2T (n/2) + 1.
Note que o valor de c nao faz diferenca no resultado T (n) = O(n log n), de modo
que quando for conveniente, podemos considerar tais constantes como tendo valor 1.
Geralmente o metodo da arvore de recorrencia e utilizado para fornecer um bom palpite
para o metodo da substituicao, de modo que e permitida uma certa “frouxidao” na
analise. Porem, uma analise cuidadosa da arvore de recorrencia e dos custos associados
a cada nıvel pode servir como uma prova direta para a solucao da recorrencia em
questao.
46
3.5 Metodo mestre
O metodo mestre faz uso do Teorema 3.1 abaixo para resolver recorrencias do tipo
T (n) = aT (n/b) + f(n) para a ≥ 1, b > 1, onde f(n) e positiva. Esse resultado
formaliza uma analise cuidadosa feita utilizando arvores de recorrencia. Na Figura 3.3
temos uma analise da arvore de recorrencia de T (n) = aT (n/b) + f(n).
Figura 3.3: Arvore de recorrencia para T (n) = aT (n/b) + f(n).
Note que temos
a0 + a1 + . . .+ alogb n =a1+logb n − 1
a− 1
=(bn)logb a − 1
a− 1
= Θ(nlogb a
).
Portanto, considerando somente o tempo para dividir o problema em subproblemas
recursivamente, temos que e gasto tempo Θ(nlogb a
). A ideia envolvida no Teorema
47
Mestre (que sera apresentado a seguir) analisa situacoes dependendo da diferenca entre
f(n) e nlogb a.
Teorema 3.1: Teorema Mestre
Sejam a ≥ 1 e b > 1 constantes e seja f(n) uma funcao. Para T (n) =
aT (n/b) + f(n), vale o seguinte:
(1) Se f(n) = O(nlogb a−ε) para alguma constante ε > 0, entao T (n) = Θ(nlogb a).
(2) Se f(n) = Θ(nlogb a), entao T (n) = Θ(nlogb a log n).
(3) Se f(n) = Ω(nlogb a+ε) para alguma constante ε > 0, e para n suficientemente
grande temos a · f(n/b) ≤ cf(n) para alguma constante c < 1, entao
T (n) = Θ(f(n)).
Mas qual a intuicao por tras desse resultado? Imagine um algoritmo com tempo de
execucao T (n) = aT (n/b) + f(n). Primeiramente, lembre que a arvore de recorrencia
descrita na Figura 3.3 sugere que o valor de T (n) depende de quao grande ou pequeno
f(n) e com relacao a nlogb a. Se a funcao f(n) sempre assume valores “pequenos” (aqui,
pequeno significa f(n) = O(nlogb a−ε)), entao e de se esperar que o mais custoso para
o algoritmo seja dividir cada instancia do problema em a partes de uma fracao 1/b
dessa instancia. Assim, nesse caso, o algoritmo vai ser executado recursivamente logb n
vezes ate que se chegue a base da recursao, gastando para isso tempo da ordem de
alogb n = nlogb a, como indicado pelo item (1). O item (3) corresponde ao caso em que
f(n) e “grande” comparado com o tempo gasto para dividir o problema em a partes
de uma fracao 1/b da instancia em questao. Portanto, faz sentido que f(n) determine
o tempo de execucao do algoritmo nesse caso, que e a conclusao obtida no item (3). O
caso intermediario, no item (2), corresponde ao caso em que a funcao f(n) e dividir o
algoritmo recursivamente sao ambos essenciais no tempo de execucao do algoritmo.
Infelizmente, existem alguns casos nao cobertos pelo Teorema Mestre, mas mesmo
nesses casos conseguir utilizar o teorema para conseguir limitantes superiores e inferiores.
Entre os casos (1) e (2) existe um intervalo em que o Teorema Mestre nao fornece
nenhuma informacao, que e quando f(n) e assintoticamente menor que nlogb a, mas
assintoticamente maior que nlogb a−ε para todo ε > 0, e.g., f(n) = Θ(nlogb a/ log n) ou
48
Θ(nlogb a/ log(log n)). De modo similar, existe um intervalo sem informacoes entre (2) e
(3).
Existe ainda um outro caso em que nao e possıvel aplicar o Teorema Mestre a
uma recorrencia do tipo T (n) = aT (n/b) + f(n). Em algumas recorrencias T (n) =
aT (n/b) + f(n) podemos ter f(n) = Ω(nlogb a+ε), porem nao satisfazem a condicao
a · f(n/b) ≤ cf(n) no item (3). Felizmente, essa condicao e geralmente satisfeita em
recorrencias que representam tempo de execucao de algoritmos. Desse modo, para
algumas funcoes f(n), podemos considerar a seguinte versao simplificada do Teorema
Mestre, que dispensa a condicao extra no item (3). Vamos considerar funcoes f(n) que
geralmente aparecem em analise de algoritmos. Seja f(n) um polinomio de grau k com
coeficientes nao negativos (para k constante), i.e., f(n) =∑k
i=0 aini, onde a0, a1, . . . , ak
sao constantes e a0, a1, . . . , ak−1 ≥ 0 e ak > 0.
Teorema 3.2: Teorema Mestre - Versao simplificada
Sejam a ≥ 1, b > 1 e k ≥ 0 constantes e seja f(n) um polinomio de grau k com
coeficientes nao negativos. Para T (n) = aT (n/b) + f(n), vale o seguinte:
(1) Se f(n) = O(nlogb a−ε) para alguma constante ε > 0, entao T (n) = Θ(nlogb a).
(2) Se f(n) = Θ(nlogb a), entao T (n) = Θ(nlogb a log n).
(3) Se f(n) = Ω(nlogb a+ε) para alguma constante ε > 0, entao T (n) = Θ(f(n)).
Demonstracao. Vamos provar que para f(n) como no enunciado, se f(n) = Ω(nlogb a+ε),
entao para todo n suficientemente grande temos a · f(n/b) ≤ cf(n) para alguma
constante c < 1. Dessa forma, nao precisamos verificar essa condicao extra de (3)
em 3.1, pois sera sempre satisfeita.
Primeiro note que como f(n) =∑k
i=0 aini = Ω(nlogb a+ε) temos k = logb a + ε.
Resta provar que af(n/b) ≤ cf(n) para algum c < 1. Logo, basta provar que cf(n)−
49
af(n/b) ≥ 0 para algum c < 1. Assim,
cf(n)− af(n/b) = ck∑
i=0
aini − a
k∑i=0
aini
bi
= ak
(c− a
bk
)nk +
k−1∑i=0
ai
(c− a
bi
)ni
≥ ak
(c− a
bk
)nk −
k−1∑i=0
ai
( abi
)ni
≥ ak
(c− a
bk
)n · nk−1 −
(a
k−1∑i=0
ai
)nk−1
= (c1n)nk−1 − (c2)nk−1,
onde c1 e c2 sao constantes e na ultima desigualdade utilizamos o fato de b > 1 (assim,
bi > 1 para todo i ≥ 0). Logo, para n ≥ c2/c1, temos que cf(n)− af(n/b) ≥ 0.
3.5.1 Resolvendo recorrencias com o metodo mestre
Vamos analisar alguns exemplos de recorrencia onde aplicaremos o Teorema Mestre
diretamente a recorrencia desejada.
Exemplo 1: T (n) = 2t(n/2) + n.
Claramente, temos a = 2 e b = 2. Portanto, f(n) = n = nlog2 2. O caso do Teorema
Mestre em que esses parametros se encaixam e o caso (2). Assim, pelo Teorema Mestre,
T (n) = Θ(n log n).
Exemplo 2: T (n) = 4T (n/10) + 5√n.
Neste caso temos a = 4, b = 10 e f(n) = 5√n. Assim, logb a = log10 4 ≈ 0, 6. Como
5√n = 5n0,5 = O(n0,6−0,1), estamos no caso (1) do Teorema Mestre. Logo,
T (n) = Θ(nlogb a) = Θ(nlog10 4).
Exemplo 3: T (n) = 4T (n/16) + 5√n.
50
Note que a = 4, b = 16 e f(n) = 5√n. Assim, logb a = log16 4 = 1/2. Como
5√n = 5n0,5 = Θ(nlogb a), estamos no caso (2) do Teorema Mestre. Logo,
T (n) = Θ(nlogb a log n) = Θ(nlog16 4 log n) = Θ(√n log n).
Exemplo 4: T (n) = 4T (n/2) + 10n3.
Neste caso temos a = 4, b = 2 e f(n) = 10n3. Assim, logb a = log2 4 = 2. Como
10n3 = Ω(n2+1), estamos no caso (3) do Teorema Mestre. Vamos verificar a condicao
extra. Antes de concluir que T (n) = Θ(f(n)) precisamos mostrar que a ·f(n/b) ≤ cf(n)
(i.e., 40(n/2)3 < 10cn3) para alguma constante c < 1 e para todo n suficientemente
grande. Mas isso e verdade para todo n ≥ 1 para qualquer 1/2 < c < 1. Logo,
concluımos que T (n) = Θ(n3).
Exemplo 5: T (n) = 5T (n/4) + n.
Temos a = 5, b = 4 e f(n) = n. Assim, logb a = log4 5. Como log4 5 > 1, temos
que f(n) = n = O(nlog4 5−ε) para ε = 1 − log4 5 > 0. Logo, estamos no caso (1) do
Teorema Mestre. Assim, concluımos que T (n) = Θ(nlog4 5).
teste c : E → F ...... c : E → F
3.5.2 Ajustes para aplicar o metodo mestre
Dada uma recorrencia T (n) = aT (n/b) + f(n), existem duas possibilidades em que
o Teorema Mestre (Teorema 3.1) nao e aplicavel (diretamente):
(i) nenhuma das tres condicoes assintoticas no teorema e valida para f(n);
(ii) f(n) = Ω(nlogb a+ε) para alguma constante ε > 0, mas nao existe c < 1 tal que
a · f(n/b) ≤ cf(n) para todo n suficientemente grande.
51
Para verificar (i), temos que verificar que valem as tres seguintes afirmacoes: 1) f(n) 6=Θ(nlogb a); para qualquer ε > 0 temos 2) f(n) 6= O(nlogb a−ε) e 3) f(n) 6= Ω(nlogb a+ε).
Lembre que, dado que temos a versao simplificada do Teorema Mestre (Teorema 3.2),
nao precisamos verificar o item (ii) pois essa condicao e sempre satisfeita para polinomios
f(n) com coeficientes nao negativos.
No que segue mostraremos que nao e possıvel aplicar o Teorema Mestre direta-
mente a algumas recorrencias, mas sempre e possıvel conseguir limitantes superiores e
inferiores analisando recorrencias levemente modificadas.
Exemplo 1: T (n) = 2T (n/2) + n log n.
Comecamos notando que a = 2, b = 2 e f(n) = n log n. Para todo n suficientemente
grande e qualquer constante C vale que n log n ≥ Cn. Assim, para qualquer ε, temos
que n log n 6= O(n1−ε), de onde concluımos que a recorrencia T (n) nao se encaixa no
caso (1). Como n log n 6= Θ(n), tambem nao podemos utilizar o caso (2). Por fim, como
log n 6= Ω(nε) para qualquer ε > 0, temos que n log n 6= Ω(n1+ε), de onde concluımos
que o caso (3) do Teorema Mestre tambem nao se aplica.
Exemplo 2: T (n) = 5T (n/8) + nlog8 5 log n.
Comecamos notando que a = 5, b = 8 e f(n) = nlog8 5 log n.
Para todo n suficientemente grande e qualquer constante C vale que nlog8 5 log n ≥Cnlog8 5. Assim, para qualquer ε, temos que nlog8 5 log n 6= O(nlog8 5−ε), de onde con-
cluımos que a recorrencia T (n) nao se encaixa no caso (1). Como nlog8 5 log n 6= Θ(nlog8 5),
tambem nao podemos utilizar o caso (2). Por fim, como log n 6= Ω(nε) para qualquer
ε > 0, temos que nlog8 5 log n 6= Ω(nlog8 5+ε), de onde concluımos que o caso (3) do
Teorema Mestre tambem nao se aplica.
Exemplo 3: T (n) = 3T (n/9) +√n log n.
Comecamos notando que a = 3, b = 9 e f(n) =√n log n. Logo, nlogb a =
√n. Para
todo n suficientemente grande e qualquer constante C vale que√n log n ≥ C
√n.
Assim, para qualquer ε, temos que√n log n 6= O(
√n/nε), de onde concluımos que a
recorrencia T (n) nao se encaixa no caso (1). Como√n log n 6= Θ(
√n), tambem nao
podemos utilizar o caso (2). Por fim, como log n 6= Ω(nε) para qualquer ε > 0, temos
que√n log n 6= Ω(
√n · nε), de onde concluımos que o caso (3) do Teorema Mestre
52
tambem nao se aplica.
Exemplo 4: T (n) = 16T (n/4) + n2/ log n.
Comecamos notando que a = 16, b = 4 e f(n) = n2/ log n. Logo, nlogb a = n2. Para
todo n suficientemente grande e qualquer constante C vale que n ≥ C log n. Assim,
para qualquer ε, temos que n2/ log n 6= O(n2−ε), de onde concluımos que a recorrencia
T (n) nao se encaixa no caso (1). Como n2/ log n 6= Θ(n2), tambem nao podemos
utilizar o caso (2). Por fim, como n2/ log n 6= Ω(n2+ε) para qualquer ε > 0, concluımos
que o caso (3) do Teorema Mestre tambem nao se aplica.
Como vimos, nao e possıvel aplicar o Teorema Mestre diretamente as recorrencias
descritas nos exemplos acima. Porem, podemos ajustar as recorrencias e conseguir bons
limitantes assintoticos utilizando o Teorema Mestre. Por exemplo, para a recorrencia
T (n) = 16T (n/4) + n2/ log n dada no exemplos acima, claramente temos T (n) ≤16T (n/4) +n2, de modo que podemos aplicar o Teorema Mestre na recorrencia T ′(n) =
16T (n/4) + n2. Como n2 = nlog4 16, pelo caso (2) do Teorema Mestre, temos que
T ′(n) = Θ(n2 log n). Portanto, como T (n) ≤ T ′(n), concluımos que
T (n) = O(n2 log n),
obtendo um limitante assintotico superior para T (n). Por outro lado, temos que
T (n) = 16T (n/4) + n2/ log n ≥ T ′′(n), onde T ′′(n) = 16T (n/4) + n. Pelo caso (1) do
Teorema Mestre, temos que T ′′(n) = Θ(n2). Portanto, como T (n) ≥ T ′′(n), concluımos
que
T (n) = Ω(n2).
Dessa forma, apesar de nao sabermos exatamente qual e a ordem de grandeza de T (n),
temos uma boa estimativa, dado que mostramos que essa ordem de grandeza esta entre
n2 e n2 log n.
A seguir temos um exemplo de recorrencia que nao satisfaz a condicao extra do
item (3) do Teorema 3.1. Ressaltamos que e improvavel que tal recorrencia descreva o
tempo de execucao de um algoritmo (a menos que esse algoritmo tenha sido projetado
especialmente para ter esse tempo de execucao).
Exemplo 5: T (n) = T (n/2) + n(2− cosn).
53
Primeiro vamos verificar que estamos no caso (3) do Teorema Mestre. De fato,
como a = 1 e b = 2, temos nlogb a = 1. Assim, como f(n) = n(2− cosn) ≥ n, temos
f(n) = Ω(nlogb a+ε) para qualquer 0 < ε < 1.
Vamos agora verificar se e possıvel obter a condicao extra do caso (3). Precisamos
mostrar que f(n/2) ≤ c · f(n) para algum c < 1 e todo n suficientemente grande.
Vamos usar o fato que cos(2kπ) = 1 para qualquer inteiro k, e que cos(kπ) = −1 para
todo inteiro ımpar k. Seja n = 2kπ para qualquer inteiro ımpar k ≥ 3. Assim, temos
c ≥ f(n/2)
f(n)=
(n/2)(2− cos(kπ)
)n(2− cos(2kπ))
=2− cos(kπ)
2(2− cos(2kπ))=
3
2.
Logo, para infinitos valores de n, a constante c precisa ser pelo menos 3/2, nao e
possıvel obter a condicao extre no caso (3). Assim, nao ha como aplicar o Teorema
Mestre a recorrencia T (n) = T (n/2) + n(2− cosn).
Existem outros metodos para resolver equacoes de recorrencia mais gerais que
equacoes do tipo T (n) = aT (n/b) + f(n). Um exemplo importante e o metodo
de Akra-Bazzi, que consegue resolver equacoes nao tao balanceadas como T (n) =
T (n/3) + T (2n/3) + Θ(n), mas nao entraremos em detalhes desse metodo aqui.
54
Parte
II
Estruturas de dados
Capıtulo
4Lista encadeada, fila e pilha
Algoritmos geralmente precisam manipular conjuntos de dados que podem crescer,
diminuir ou sofrer diversas modificacoes durante sua execucao. Muitos algoritmos
necessitam realizar algumas operacoes essenciais, como insercao e remocao de elementos
em um conjunto de dados. A eficiencia dessas e de outras operacoes depende fortemente
do tipo de estrutura de dados utilizada. Abaixo vamos discutir as estruturas lista
encadeada, pilha e fila.
4.1 Lista encadeada
Lista encadeada e uma estrutura de dados onde a ordem dos elementos e determinada
por um ponteiro em cada objeto, diferente do que acontece com vetores, onde os
elementos estao dispostos em uma ordem linear determinada pelos ındices do vetor.
Em uma lista duplamente encadeada L, cada elemento contem um atributo chave e
dois ponteiros, anterior e proximo. Obviamente, cada elemento da lista pode conter
outros atributos contendo mais dados. Aqui vamos sempre inserir, remover ou modificar
elementos de uma lista baseado nos atributos chave, que sempre contem inteiros nao
negativos.
Dado um elemento x na lista, x.anterior aponta para o elemento que esta imediata-
mente antes de x na lista e x.proximo aponta para o elemento que esta imediatamente
apos x na lista. Se x.anterior = null, entao x nao tem predecessor, de modo que
e o primeiro elemento da lista, a cabeca da lista. Se x.proximo = null, entao x nao
tem sucessor e e chamado de cauda da lista, sendo o ultimo elemento de L. O atributo
L.cabeca aponta para o primeiro elemento da lista L, sendo que L.cabeca = null
quando a lista esta vazia.
Uma lista L pode ter varios formatos. Ela pode ser duplamente encadeada, como
descrito no paragrafo anterior, ou pode ser uma lista encadeada simples, onde nao
existe o ponteiro anterior. Uma lista pode ser ordenada ou nao ordenada, circular
ou nao circular. Em uma lista circular, o ponteiro proximo da cauda aponta para a
cabeca da lista, enquanto o ponteiro anterior da cabeca aponta para a cauda. A
figura abaixo mostra um exemplo de uma lista duplamente encadeada circular.
Figura 4.1: Lista duplamente encadeada circular.
A seguir vamos descrever os procedimentos de busca, insercao e remocao em uma
lista duplamente encadeada, nao ordenada e nao-circular.
O procedimento Busca lista abaixo realiza uma busca pelo primeiro elemento
com chave k na lista L. Primeiramente, a cabeca da lista L e analisada e em seguida
os elementos da lista sao analisados, um a um, ate que k seja encontrado ou ate que a
lista seja completamente verificada. No pior caso, toda a lista deve ser verificada, de
modo que o tempo de execucao de Busca lista e O(n) para uma lista com n elementos.
Algoritmo 9: Busca lista(L, k)
1 x = L.cabeca
2 enquanto x 6= null e x.chave 6= k faca
3 x = x.proximo
4 retorna x
A insercao e realizada sempre no comeco da lista. No procedimento abaixo inserimos
um elemento x na lista L. Portanto, caso L nao seja vazia, o ponteiro x.proximo deve
58
apontar para a atual cabeca de L e L.cabeca.anterior deve apontar para x. Caso L
seja vazia entao x.proximo aponta para null. Como x sera a cabeca de L, o ponteiro
x.anterior deve apontar para null.
Algoritmo 10: Insercao lista(L, x)
1 x.proximo = L.cabeca
2 se L.cabeca 6= null entao
3 L.cabeca.anterior = x
4 L.cabeca = x
5 x.anterior = null
Como somente uma quantidade constante de operacoes e executada, o procedimento
Insercao-Lista e executado em tempo O(1) para uma lista com n elementos. Note que
o procedimento de insercao em uma lista encadeada ordenada levaria tempo O(n), pois
precisarıamos inserir x na posicao correta dentro da lista, tendo que percorrer toda a
lista no pior caso.
O procedimento Remocao lista abaixo, remove um elemento x de uma lista L.
Note que o parametro passado para o procedimento e um ponteiro para x e nao um
valor chave k. Esse ponteiro pode ser retornado, por exemplo, por uma chamada a
Busca-Lista. A remocao e simples, sendo necessario somente atualizar os ponteiros
x.anterior.proximo e x.proximo.anterior, tendo cuidado com os casos onde x e a
cabeca ou a cauda de L.
Algoritmo 11: Remocao lista(L, x)
1 se x.anterior 6= null entao
2 x.anterior.proximo = x.proximo
3 senao
4 L.cabeca = x.proximo
5 se x.proximo 6= null entao
6 x.proximo.anterior = x.anterior
59
Como somente uma quantidade constante de operacoes e efetuada, a remocao leva
tempo O(1) para ser executada. Porem, se quisermos remover um elemento que contem
uma dada chave k, precisamos primeiramente efetuar uma chamada ao algoritmo
Busca lista(L, k) e remover o elemento retornado pela busca, gastando tempo O(n)
no pior caso.
Observe que o fato do procedimento Remocao lista ter sido feito em uma lista
duplamente encadeada e essencial para que seu tempo de execucao seja O(1). Se L
for uma lista encadeada simples, nao temos a informacao de qual elemento em L esta
na posicao anterior a x, dado que nao existe x.anterior. Portanto, seria necessario
uma busca por esse elemento, para podermos efetuar a remocao de x. Desse modo, um
procedimento de remocao em uma lista encadeada simples leva tempo O(n) no pior
caso.
4.2 Pilha
Pilha e uma estrutura de dados onde as operacoes de insercao e remocao sao feitas na
mesma extremidade, chamada de topo da pilha. Ademais, ao se realizar uma remocao
na pilha, o elemento a ser removido e sempre o ultimo elemento que foi inserido na
pilha. Essa polıtica de remocao e conhecida como “LIFO”, acronimo para “last in, first
out”.
Existem inumeras aplicacoes para pilhas. Por exemplo, verificar se uma palavra e
um palındromo e um procedimento muito simples de se realizar utilizando uma pilha.
Basta inserir as letras em ordem e depois realizar a remocao uma a uma, verificando
se a palavra formada e a mesma que a inicial. Uma outra aplicacao (muito utilizada)
e a operacao “desfazer”, presente em varios editores de texto. Toda mudanca de
texto e colocada em uma pilha, de modo que cada remocao da pilha fornece a ultima
modificacao realizada. Mencionamos tambem que pilhas sao uteis na implementacao
de algoritmos de busca em profundidade em grafos.
Vamos mostrar como implementar uma pilha de no maximo n elementos utilizando
um vetor P [1..n]. Ressaltamos que existem ainda outras formas de implementar pilhas.
Por exemplo, poderıamos utilizar listas encadeadas para realizar essa tarefa.
Dado um vetor P [1..n], o atributo P.topo contem o ındice do elemento que foi
inserido por ultimo, contendo 0 quando a pilha estiver vazia. P.tamanho contem o
60
tamanho do vetor, i.e., n. Em qualquer momento, o vetor P [1 . . . P.topo] representa a
pilha em questao, onde P [1] contem o primeiro elemento inserido na pilha e P [P.topo]
contem o ultimo.
Quando inserimos um elemento x na pilha P , dizemos que estamos empilhando x
em P . Similarmente, ao remover x de P nos desempilhamos x de P . As duas operacoes
de pilha a seguir, Empilha e Desempilha, sao bem simples e todas elas levam tempo
O(1) para serem executadas.
Para acrescentar um elemento x a pilha P , utilizamos o procedimento Empilha
abaixo, que verifica se a pilha esta cheia e, caso ainda haja espaco, atualiza o topo da
pilha P.topo para P.topo + 1 e insere x em P [P.topo].
Algoritmo 12: Empilha(P, x)
1 se P.topo = P.tamanho entao
2 retorna “Pilha cheia”
3 senao
4 P.topo = P.topo + 1
5 P [P.topo] = x
Para desempilhar basta verificar se a pilha esta vazia e, caso contrario, decrementar
de uma unidade o valor de P.topo, retornando o elemento que estava no topo da pilha.
Algoritmo 13: Desempilha(P )
1 se P.topo == 0 entao
2 retorna “Pilha vazia”
3 senao
4 P.topo = P.topo− 1
5 retorna P [P.topo + 1]
A figura abaixo ilustra as seguinte operacoes, em ordem, onde a pilha P esta
inicialmente vazia: Empilha(P, 3), Empilha(P, 5), Empilha(P, 1), Desempilha(P ),
Desempilha(P ), Empilha(P, 8).
61
Figura 4.2: Operacoes em uma pilha.
4.3 Fila
A fila e uma estrutura de dados onde as operacoes de insercao e remocao sao feitas em
extremidades opostas, a cabeca e a cauda da fila. Ademais, ao se realizar uma remocao
na fila, o elemento a ser removido e sempre o primeiro elemento que foi inserido na
fila. Essa polıtica de remocao e conhecida como “FIFO”, acronimo para “first in, first
out”.
O conceito de fila e amplamente utilizado na vida real. Por exemplo, qualquer
sistema que controla a ordem de atendimento em bancos pode ser implementado
utilizando filas. Mais geralmente, filas podem ser utilizadas em algoritmos que precisam
controlar acesso a recursos, de modo que a ordem de acesso e definida pelo tempo em
que o recurso foi solicitado. Outra aplicacao e a implementacao de busca em largura
em grafos.
Como acontece com pilhas, filas podem ser implementadas de diversas formas. Aqui
vamos focar na implementacao utilizando vetores. Vamos mostrar como implementar
uma fila de no maximo n− 1 elementos utilizando um vetor F [1, . . . , n]. Para ter o
controle de quando a pilha esta vazia ou cheia, conseguimos guardar no maximo n− 1
elementos em um vetor de tamanho n.
Dado um vetor F [1, . . . , n], os atributos F.cabeca e F.cauda contem, respec-
tivamente, os ındices para o inıcio de F e para a posicao onde o proximo ele-
mento sera inserido em F . Portanto, os elementos da fila encontram-se nas posicoes
F.cabeca, F.cabeca + 1, . . . , F.cauda − 2, F.cauda − 1, onde as operacoes de soma e
subtracao sao feitas modulo F.tamanho = n, i.e., podemos enxergar o vetor F de forma
circular.
Quando inserimos um elemento x na fila F , dizemos que estamos enfileirando x em
62
F . Similarmente, ao remover x de F nos estamos desenfileirando x de F .
Antes de descrever as operacoes, vamos discutir alguns detalhes sobre filas. Inicial-
mente, temos F.cabeca = F.cauda = 1. Sempre que F.cabeca = F.cauda, a fila esta
vazia, e a fila esta cheia quando F.cabeca = F.cauda + 1. As duas operacoes de fila a
seguir, Fila-adiciona e Fila-remove levam tempo O(1) para serem executadas.
O procedimento Fila-adiciona abaixo adiciona um elemento a fila. Primeiramente
e verificado se a fila esta cheia, caso onde nada e feito. Caso contrario, o elemento e
adicionado na posicao F.cauda e atualizamos o valor de F.cauda. Esse procedimento
realiza uma quantidade constante de operacoes, de modo que e claramente executado
em tempo O(1).
Algoritmo 14: Fila-adiciona(F, x)
1 se (F.cabeca == 1 e F.cauda == n) ou (F.cabeca == F.cauda + 1) entao
2 retorna “Fila cheia”
3 senao
4 F [F.cauda] = x
5 se F.cauda == F.tamanho entao
6 F.cauda = 1
7 senao
8 F.cauda = F.cauda + 1
Para remover um elemento da fila, utilizamos o procedimento Fila-remove abaixo,
que verifica se a fila esta vazia e, caso contrario, retorna o primeiro elemento que foi
inserido na fila (elemento contido no ındice F.cabeca) e atualiza o valor de F.cabeca.
Como no procedimento Fila-adiciona, claramente o tempo gasto em Fila-remove
e O(1).
63
Algoritmo 15: Fila-remove(F )
1 se F.cabeca == F.cauda entao
2 retorna “Fila vazia”
3 senao
4 x = F [F.cabeca]
5 se F.cabeca == F.tamanho entao
6 F.cabeca = 1
7 senao
8 F.cabeca = F.cabeca + 1
9 retorna x
A figura abaixo ilustra as seguinte operacoes (as mesmas que fizemos para ilus-
trar as operacoes de pilha), em ordem, onde a fila F esta inicialmente vazia: Fila-
adiciona(F, 3), Fila-adiciona(F, 5), Fila-adiciona(F, 1), Fila-remove(F ), Fila-
remove(F ), Fila-adiciona(F, 8).
Figura 4.3: Operacoes em uma fila. H aponta para a cabeca e T para a cauda.
Resumindo as informacoes deste capıtulo, temos que pilhas e filas sao estruturas de
dados simples mas com diversas aplicacoes. Insercao e remocao em ambas as estruturas
levam tempo O(1) para serem executadas e sao pre-determinadas pela estrutura.
Insercoes e remocoes em pilha sao feitas na mesma extremidade, implementando a
polıtica LIFO. Na fila, a polıtica FIFO e implementada, onde o primeiro elemento
inserido e o primeiro a ser removido.
Listas encadeadas sao organizadas com a utilizacao de ponteiros nos elementos.
Uma caracterıstica interessante de listas duplamente encadeadas e que insercao e
remocao sao feitas em tempo O(1). Uma vantagem em relacao ao uso de vetores e que
64
nao e necessario saber a quantidade de elementos que serao utilizados previamente.
Em geral, o tempo de execucao das operacoes em listas encadeadas depende do tipo de
lista em questao, que sumarizamos na tabela abaixo.
Nao ordenada, Ordenada, Nao ordenada, Ordenada
simples simples dupla. enc. dupla. enc.
Busca-Lista O(n) O(n) O(n) O(n)
Insercao-Lista O(1) O(n) O(1) O(n)
Remocao-Lista O(n) O(n) O(1) O(1)
65
66
Capıtulo
5Heap binario
Antes de discutirmos heaps binarios lembre que uma arvore binaria e uma estrutura
de dados organizada em formato de arvores onde existe um vertice raiz, cada vertice
possui no maximo dois filhos, e cada vertice que nao e raiz tem exatamente um pai. O
unico no que nao possui pai e chamado de raiz da arvore. Vertices que nao possuem
filhos sao chamados de folhas.
Lembre tambem que a altura de uma arvore e a quantidade de arestas do maior
caminho entre a raiz e uma de suas folhas. Dizemos que os vertices que estao a uma
distancia i da raiz estao no nıvel i (a raiz esta no nıvel 0). Uma arvore binaria e dita
completa se todos os seus nıveis estao completamente preenchidos. Note que arvores
binarias completas com altura h possuem 2h+1 − 1 vertices. Dizemos que a altura de
um vertice v e a altura da subarvore com raız em v.
Uma arvore binaria com altura h e dita quase completa se os nıveis 0, 1, . . . , h− 1
tem todos os vertices possıveis. Na Figura 5.1 temos um exemplo de uma arvore quase
completa ordenada.
Um heap e uma estrutura que pode ser definida de duas formas diferentes, depen-
dendo da aplicacao: heap maximo e heap mınimo. Como todas as operacoes em heaps
maximos sao similares as operacoes em heaps mınimos, vamos aqui trabalhar somente
com heaps maximos.
Dado um vetor A, a quantidade de elementos suportada por A e denotada por
A.tamanho. Definiremos agora a estrutura em que estamos interessados nesta secao, o
heap maximo, que pode ser representado atraves do uso de um vetor. Um heap repre-
Figura 5.1: Arvore binaria quase completa.
sentado em A tem no maximo A.tam-heap elementos, onde A.tam-heap ≤ A.tamanho.
Vamos utilizar nomenclatura de pai e filhos, como em arvores. O elemento em A[1]
e o unico elemento que nao tem pai e, para todo 2 ≤ i ≤ A.tam-heap, temos que o
ındice do pai de A[i] e bi/2c. Os filhos esquerdo e direito de um elemento A[i] estao,
respectivamente, nos ındices 2i e 2i+ 1, onde um elemento tem filho esquerdo somente
se 2i ≤ A.tam-heap e tem filho direito somente se 2i+ 1 ≤ A.tam-heap. Finalmente,
o vetor A satisfaz a propriedade de heap: para todo 2 ≤ i ≤ A.tam-heap, temos
A[bi/2c] ≥ A[i], i.e., o valor do pai e sempre maior ou igual ao valor de seus filhos.
Analisando a definicao acima podemos enxergar um heap como uma arvore binaria
quase completa onde a propriedade de heap e satisfeita. Ademais, em um heap maximo
visto como uma arvore binaria, o ultimo nıvel da arvore e preenchido de forma contıgua
da esquerda para a direita. A Figura 5.1 vista anteriormente representa um heap
maximo.
5.1 Construcao de um heap binario
Primeiramente descreveremos um procedimento chamado de Max-conserta-heap
que sera util na construcao de um heap e tambem para o algoritmo Heapsort. Max-
conserta-heap recebe um vetor A e um ındice i e assumimos que as subarvores com
raiz A[2i] ou A[2i+ 1] sao heaps maximos. Max-conserta-heap vai mover A[i] para
baixo na arvore de modo que, ao final do procedimento, a subarvore com raiz em A[i]
satisfaz a propriedade de heap.
68
Algoritmo 16: Max-conserta-heap(A, i)
1 maior = i
2 se 2i ≤ A.tam-heap entao
3 se A[2i] > A[maior] entao
4 maior = 2i
5 se 2i+ 1 ≤ A.tam-heap entao
6 se A[2i+ 1] > A[maior] entao
7 maior = 2i+ 1
8 se maior 6= i entao
9 troca A[i] com A[maior]
10 Max-conserta-heap (A,maior)
A Figura 5.2 mostra um exemplo de execucao da rotina Max-conserta-heap.
Figura 5.2: Execucao de Max-conserta-heap(A, 2) em A =[20, 0, 10, 6, 8, 3, 5, 1, 4, 7, 2].
Teorema 5.1: Corretude de Max-conserta-heap
O algoritmo Max-conserta-heap(A, i) recebe um vetor A e um ındice i tal
que as subarvores com raiz A[2i] ou A[2i+ 1] sao heaps maximos, e modifica A de
modo que a arvore com raiz em A[j] para todo i ≤ j ≤ A.tam-heap e um heap
maximo.
69
Demonstracao. Vamos provar a corretude de Max-conserta-heap(A, i) por inducao
em i. Como os ultimos A.tam-heap/2 elementos de A sao folhas (heaps de tamanho 1),
sabemos que as arvores com raiz em A[i] para bA.tam-heap/2 + 1 ≤ i ≤ A.tam-heap
sao heaps maximos.
Seja i ≥ 1 e suponha agora que o algoritmo funciona corretamente quando recebe
A e um ındice i + 1 ≤ j ≤ A.tam-heap. Precisamos mostrar que Max-conserta-
heap(A, i) funciona corretamente, i.e., a arvore com raiz A[j], para todo i ≤ j ≤A.tam-heap, e um heap maximo.
Considere uma execucao de Max-conserta-heap(A, i). Note que se A[i] e maior
ou igual a seus filhos, entao os testes nas linhas 3, 6 e 8 nao serao verificados e o
algoritmo nao faz nada, que e o esperado, uma vez que a arvore com raiz em A[i] ja e
um heap maximo.
Assuma agora que A[i] e menor do que algum dos seus filhos. Caso A[2i] seja o
maior dos filhos, o teste na linha 2 e na linha 3 sera executado com sucesso e teremos
maior = 2i. A linha 7 nao sera executada, e como maior 6= i, o algoritmo troca
A[i] com A[maior] e executa Max-conserta-heap (A,maior) na linha 10. Como
maior = 2i ≥ i + 1, sabemos pela hipotese de inducao que o algoritmo funciona
corretamente, de onde concluımos que a arvore com raiz em A[2i] e um heap maximo.
Como A[i] e agora maior que A[2i], concluımos que a arvore com raiz A[j], para todo
i ≤ j ≤ A.tam-heap, e um heap maximo. A prova a analoga quando A[2i + 1] e o
maior dos filhos de A[i].
Vamos analizar o tempo de execucao de Max-conserta-heap(A, i) em um heap
com n elementos representado pelo vetor A. O ponto chave e perceber que a cada
chamada recursiva, Max-conserta-heap desce um nıvel na arvore. Assim, em uma
arvore de altura h, em O(h) passos a base da arvore e alcancada. Como em cada passo
somente tempo constante e gasto, concluımos que Max-conserta-heap tem tempo
de execucao O(h), onde h e a altura da arvore em questao. Sabendo que um heap pode
ser visto como uma arvore binaria quase completa, que tem altura O(log n), o tempo
de execucao de Max-conserta-heap e O(log n).
Vamos fazer uma analise mais detalhada do tempo de execucao T (n) de Max-
conserta-heap (A, i). Note que a cada chamada recursiva o problema diminui
consideravelmente de tamanho. Se estamos na iteracao correspondente a um elemento
A[i], a proxima chamada recursiva sera na subarvore cuja raiz e um filho de A[i].
70
Mas qual o pior caso possıvel? No pior caso, se o problema inicial tem tamanho
n, o subproblema seguinte possui tamanho no maximo 2n/3. Isso segue do fato de
possivelmente analisarmos a subarvore cuja raiz e o filho esquerdo de A[1] (i.e., esta no
ındice 2) e o ultimo nıvel da arvore esta cheio ate a metade. Assim, a subarvore com raiz
no ındice 2 possui aproximadamente 2/3 dos vertices, enquanto que a subarvore com
raiz em 3 possui aproximadamente 1/3 dos vertices. Em todos os proximos passos os
subproblemas sao divididos na metade do tamanho da instancia atual. Como queremos
um limitante superior, podemos calcular o tempo de execucao de Max-conserta-heap
como:
T (n) ≤ T (2n/3) + 1
≤ T((2/3)2n
)+ 2
...
≤ T((2/3)in
)+ i
= T(n/(3/2)i
)+ i
Fazendo i = log3/2 n e assumindo T (1) = 1, temos
T (n) ≤ 1 + log3/2 n
= O(log n).
Podemos tambem aplicar o Teorema Mestre. Sabendo que o tempo de execucao
T (n)de Max-conserta-heap e no maximo T (2n/3) + 1. podemos aplicar o Teorema
Mestre a recorrencia T ′(n) = T ′(2n/3) + 1 para obter um limitante superior para
T (n). Como a = 1, b = 3/2 e f(n) = 1, temos que f(n) = Θ(nlog3/2 1). Assim,
utilizando o caso (2) do Teorema Mestre, concluımos que T ′(n) = Θ(log n). Portanto,
T (n) = O(log n).
Note que os ultimos n/2 elementos de A sao folhas (heaps de tamanho 1), de
modo que um heap pode ser construıdo simplesmente chamando o procedimento Max-
conserta-heap(A, i) para i = n/2, . . . , 1, nessa ordem. Seja a rotina Construa-
heap(A) abaixo tal procedimento.
71
Algoritmo 17: Construa-heap(A[1..n])
1 A.tam-heap = n
2 para i = bn/2c ate 1 faca
3 Max-conserta-heap(A, i)
A Figura 5.3 tem um exemplo de execucao da rotina Construa-heap. Antes
de estimarmos o tempo de execucao do algoritmo, vamos mostrar que ele funciona
corretamente. Para isso precisaremos da seguinte invariante de laco.
Invariante: Construa-heap
Antes de cada iteracao do laco para (indexado por i), para todo i+ 1 ≤ j ≤ n,
a arvore com raiz A[j] e um heap maximo.
Teorema 5.3
O algoritmo Construa-heap(A[1..n]) transforma o vetor A em um heap
maximo.
Demonstracao. Inicialmente temos i = bn/2c, entao precisamos verificar se, para todo
bn/2c + 1 ≤ j ≤ n, a arvore com raiz A[j] e um heap maximo. Mas essa arvore e
composta somente pelo elemento A[j], pois como j > bn/2c, o elemento A[j] nao tem
filhos. Assim, a arvore com raiz em A[j] e um heap maximo.
Suponha agora que a invariante e valida imediatamente antes da i-esima iteracao
do laco para, i.e., para todo i+ 1 ≤ j ≤ n, a arvore com raiz A[j] e um heap maximo.
Para mostrar que a invariante e valida imediatamente antes da (i− 1)-esima iteracao,
note que na i-esima iteracao do laco temos que as arvores com raiz A[j] sao heaps,
para i + 1 ≤ j ≤ n. Portanto, caso A[i] tenha filhos, esses sao raızes de heaps, de
modo que a chamada a Max-conserta-heap(A, i) na linha 3 funciona corretamente,
transformando a arvore com raiz A[i] em um heap maximo. Assim, para todo i ≤ j ≤ n,
a arvore com raiz A[j] e um heap maximo. Portanto, a invariante se mantem valida
72
antes de todas as iteracoes do laco.
Ao fim da execucao do laco temos i = 0, de modo que, pela invariante de laco, a
arvore com raiz em A[1] e um heap maximo.
No que segue seja T (n) o tempo de execucao de Construa-heap em um vetor
A com n elementos. Uma simples analise permite concluir que T (n) = O(n log n): o
laco para e executado no maximo n/2 vezes, e em cada uma dessas execucoes a rotina
Max-conserta-heap, que leva tempo O(log n) e executada. Logo, concluımos que
T (n) = O(n log n).
Uma analise mais cuidadosa fornece um limitante melhor que O(n log n). Primeiro
vamos observar que em um heap de tamanho n existem no maximo dn/2h+1e elementos
com altura h. Verificaremos isso por inducao na altura h. As folhas sao os elementos
com altura h = 0. Como temos n/2 = dn/20+1e folhas, entao a base esta verificada.
Seja 1 ≤ h ≤ blog nc e suponha que existem no maximo dn/2he elementos com altura
h−1. Note que na altura h existem no maximo metade da quantidade maxima possıvel
de elementos de altura h − 1. Assim, utilizando a hipotese indutiva, na altura h
temos no maximo⌈dn/2he/2
⌉elementos, que implica que existem no maximo dn/2h+1e
elementos com altura h.
Assim, para cada elemento de altura h, a chamada recursiva de Max-conserta-
heap correspondente executa em tempo O(h). Assim, para n suficientemente grande,
temos que cada uma dessas chamadas recursivas e executada em tempo no maximo Ch
para alguma constante C > 0. Portanto, o tempo de execucao de Construa-heap e
dado como segue.
T (n) ≤blognc∑h=0
⌈ n
2h+1
⌉Ch
= Cn
blognc∑h=0
h
2h.
73
Seja S =∑blognc
h=0h
2h+1 . Notando que 2S = 1 +∑blognc
h=1h
2h−1 , obtemos
S = 2S − S =
1 +
blognc∑h=1
h
2h−1
+
blognc∑h=0
h
2h+1
=
(1− blog nc
n
)+
blognc−1∑h=1
1
2h
≤ 1 +∞∑h=1
1
2h
= 2.
Portanto,
T (n) = O(Sn) = O(n).
74
Figura 5.3: Execucao do Construa-heap(A) no vetor A = [3, 1, 5, 8, 2, 4, 7, 6, 9].
75
76
Capıtulo
6Fila de prioridades
Neste capıtulo introduzimos filas de prioridades. Essas estruturas sao uteis em diversos
procedimentos, incluindo uma implementacao eficiente dos algoritmos de Prim e Dijkstra
(veja Capıtulos 16 e 18).
Dado um conjunto V de elementos, onde cada elemento de v ∈ V possui um atributo
v.chave e um atributo v.indice. Uma fila de prioridades baseada nos atributos chave
dos elementos de V e uma estrutura de dados que contem as chaves de V e permite
executar algumas operacoes de forma eficiente. Filas de prioridades podem ser de
mınimo ou de maximo, mas como os algoritmos sao todos analogos, mostraremos aqui
somente as operacoes em uma fila de prioridades de mınimo.
Uma fila de prioridades F sobre um conjunto V , baseada nos valores v.chave para
cada v ∈ V , permite remover (ou consultar) um elemento com chave mınima, inserir
um novo elemento em F , e alterar o valor da chave de um elemento em F para um
valor menor.
Vamos mostrar como implementar uma fila de prioridades F utilizando um heap
mınimo. Apos quaisquer operacoes em F , essa fila de prioridades sempre representara
um heap mınimo.
No Capıtulo 5 introduzimos diversos algoritmos sobre a estrutura de dados heap.
Fizemos isso utilizando um vetor F com um conjunto de chaves. A seguir discutimos
uma pequena variacao dos algoritmos Max-conserta-heap e Construa-heap apre-
sentados na Secao 5 que, em vez de um conjunto de chaves, mantem um vetor F de
elementos v de um conjunto V tal que, cada v ∈ V possui atributos v.chave e v.indice,
representando respectivamente a chave do elementos e o ındice em que o elemento se
encontra dentro do vetor F . Os algoritmos que apresentaremos mantem os ındices dos
elementos de F atualizados. Esses algoritmos serao uteis para uma implementacao
eficiente dos algoritmos de Prim e Dijkstra vistos nas proximas secoes. Lembre que F
possui tamanho elementos e o heap contem F.tam-heap ≤ F.tamanho. Abaixo temos
a versao correspondente a heaps mınimos do algoritmo Max-conserta-heap, onde
mantemos os ındices dos elementos de F atualizados.
Algoritmo 18: Min-conserta-heap-indice(F, i)
1 menor = i
2 se 2i ≤ F.tam-heap entao
3 se F [2i].chave < F [menor].chave entao
4 menor = 2i
5 se 2i+ 1 ≤ A.tam-heap entao
6 se F [2i+ 1].chave < F [menor].chave entao
7 menor = 2i+ 1
8 se menor 6= i entao
9 troca F [i].indice com F [menor].indice
10 troca F [i] com F [menor]
11 Min-conserta-heap-indice (F,menor)
Para construir um heap baseado no vetor F , vamos utilizar um procedimento similar
ao descrito na Secao 5, fazendo uso do algoritmo Min-conserta-heap-indice.
Algoritmo 19: Construa-heap-indice(F )
1 F.tam-heap = F.tamanho
2 para i = 1 ate F.tam-heap faca
3 F [i].indice = i
4 para i = bF.tam-heap/2c ate 1 faca
5 Min-conserta-heap-indice(F, i)
78
Vamos voltar nossa atencao as filas de prioridade. Se Mınimo(F ) e o procedimento
para retornar o elemento de menor valor em F , basta que ele retorne F [1], de modo que
e executado em tempo constante. Porem, se quisermos remover o elemento de menor
valor, precisamos fazer isso de modo que ao fim da operacao a fila de prioridades ainda
seja um heap mınimo. Para garantir essa propriedade, salvamos o valor de F [1].chave
em uma variavel e colocamos F [F.tam-heap] em F [1], reduzindo em seguida o ta-
manho do heap F em uma unidade. Porem, como a propriedade de heap pode ter
sido destruıda, vamos conserta-la executando Min-conserta-heap-indice(F, 1). O
algoritmo Remocao-min(F ) abaixo remove e retorna o elemento que contem a menor
chave dentre todos os elementos de F .
Algoritmo 20: Remocao-min(F )
1 se F.tam-heap < 1 entao
2 retorna “Fila de prioridades esta vazia”
3 indice-menor = F [1]
4 F [F.tam-heap].indice = 1
5 F [1] = F [F.tam-heap]
6 F.tam-heap = F.tam-heap− 1
7 Min-conserta-heap-indice(F, 1)
8 retorna indice-menor
Como Min-conserta-heap-indice(F, 1) e executado em tempo O(log n) para um
heap F com n elementos, e facil notar que o tempo de execucao de Remocao-min(F )
e O(log n) para uma fila de prioridades F com n elementos.
Para alterar o valor de uma chave salva em F [i].chave para um valor menor, basta
realizar a alteracao diretamente e ir “subindo” esse elemento no heap ate que a propri-
edade de heap seja restaurada. O seguinte procedimento realiza essa operacao.
79
Algoritmo 21: Diminui-chave(F, i, x)
1 se x > F [i].chave entao
2 retorna “x e maior que F [i].chave”
3 F [i].chave = x
4 enquanto i > 1 e F [i].chave < F [bi/2c].chave faca
5 troca F [i].indice e F [bi/2c].indice6 troca F [i] e F [bi/2c]7 i = bi/2c
Como o algoritmo simplesmente “sobe” no heap, i.e., a cada passo o ındice i e divi-
dido por 2, entao em uma fila de prioridades com n elementos, Diminui-chave(F, i, x)
e executado em tempo O(log n).
Para inserir um novo elemento com chave x em uma fila de prioridades F , primeiro
verificamos se e possıvel aumentar o tamanho do heap, caso seja possıvel, aumen-
tamos seu tamanho tam-heap em uma unidade, inserimos um elemento com valor
maior que todas as chaves em F (aqui representado por ∞) e executamos Diminui-
chave(F, tam-heap, x) para colocar esse elemento em sua posicao correta.
Algoritmo 22: Insere-fila-prioridades(F, x)
1 se F.tam-heap = F.tamanho entao
2 retorna “heap esta cheio”
3 F.tam-heap = F.tam-heap + 1
4 F [tam-heap].indice = F.tam-heap
5 F [tam-heap].chave =∞6 Diminui-chave(F, tam-heap, x)
Como o algoritmo realiza somente uma operacao Diminui-chave e todas as
outras operacoes sao executadas em tempo constante, concluımos que Insere-fila-
prioridades(F, x) e executado em tempo O(log n).
80
Capıtulo
7Union-find
A estrutura de dados conhecida como union-find mantem uma particao de um conjunto
de elementos A e permite as seguintes operacoes:
• Cria conjunto(x): cria um conjunto novo contendo somente o elemento x;
• Find(x): retorna qual e o conjunto de A que contem o elemento x;
• Union(x, y): gera um conjunto obtido da uniao dos conjuntos que contem os
elementos x e y de A.
Podemos facilmente obter algoritmos que realizam as operacoes Cria conjunto(x)
e Find(x) em tempo constante, i.e., O(1). Para a operacao Union(x, y) vamos
descrever as ideias de um algoritmo que a realiza em tempo O(|X|), onde X e Y sao
respectivamente o tamanho dos conjuntos que contem x e y, e |X| ≤ |Y |.Dado um conjunto A, cada subconjunto X de A mantido pela estrutura Union-find e
identificado atraves de um atributo x.representante presente em cada elemento de A.
Assim, se temos X = a, b, c, os tres elementos de X tem o mesmo representante, como
por exemplo a.representante = a, b.representante = a e c.representante = a. A
operacao Cria conjunto(x) faz x.representante = x, de modo que para realizar a
operacao Union(x, y) onde x ∈ X, y ∈ Y e |X| ≤ |Y |, vamos atualizar o representante
de todo elemento de X (o menor dentre X e Y ) para ter o mesmo representante dos
elementos de Y , isto e, basta fazer v.representante = y.representante para todo
v ∈ X. Assim, e possıvel executar essa operacao em tempo O(|X|).
82
Parte
III
Algoritmos de ordenacao
Capıtulo
8Insertion sort
O problema de ordenacao consiste em ordenar um conjunto de chaves contidas em
um vetor. Mais precisamente, seja A = (a1, a2, . . . , an) uma sequencia com n numeros
dada como entrada. Queremos obter uma permutacao (a′1, a′2, . . . , a
′n) desses numeros
de modo que a′1 ≤ a′2 ≤ . . . ≤ a′n, i.e., desejamos obter como saıda os elementos da
sequencia de entrada ordenados de modo nao-decrescente.
Dentre caracterısticas importantes de algoritmos de ordenacao, podemos destacar
duas: um algoritmo e dito “in-place” se utiliza somente espaco constante a mais do que
os dados de entrada, e um algoritmo e dito estavel se a ordem em que chaves de mesmo
valor aparecem na saıda sao a mesma da entrada. Discutiremos essas propriedades, e a
aplicabilidade e tempo de execucao dos algoritmos que serao apresentados.
Vamos analisar um algoritmo simples, chamado de Insertion sort, que recebe
um vetor A = (a1, a2, . . . , an) com n numeros e retorna esse mesmo vetor A em ordem
nao-decrescente. A ideia do algoritmo Insertion sort e executar n “rodadas” de
instrucoes, onde a cada rodada temos um subvetor de A ordenado que contem um
elemento a mais do que o subvetor da rodada anterior. Mais precisamente, ao fim
na i-esima rodada, o algoritmo garante que o vetor A[1..i] esta ordenado. Sabendo
que o vetor A[1..i] esta ordenado, e facil “encaixar” o elemento A[i + 1] na posicao
correta no vetor A[1..i + 1]. Para encaixar o elemento A[i + 1] na posicao correta
em A[1..i + 1], o algoritmo vai comparar o numero contido em A[i + 1] com A[i],
A[i−1], e assim por diante, ate que encontre um ındice j tal que A[j] < A[i+1]. Assim,
a posicao correta de A[i+1] e a posicao j+1. Segue o pseudocodigo do Insertion sort.
Algoritmo 23: Insertion sort(A)
1 para i = 2, . . . , n faca
2 atual = A[i]
3 j = i− 1
4 enquanto j > 0 e A[j] > atual faca
5 A[j + 1] = A[j]
6 j = j − 1
7 A[j + 1] = atual
8 retorna A
Note que o Insertion sort e um algoritmo in-place e estavel. A Figura 8.1 mostra
uma execucao do algoritmo.
Figura 8.1: Execucao do Insertion sort no vetor A = [2, 5, 1, 4, 3].
Na secao seguinte mostraremos que o algoritmo funciona corretamente.
8.1 Corretude e tempo de execucao
86
Para entender como podemos utilizar as invariantes de laco para provar a corretude
de algoritmos vamos fazer a analise do algoritmo Insertion sort. Considere a seguinte
invariante de laco.
Invariante: Insertion sort
Antes de cada iteracao do laco para (indexado por i), o subvetor A[1..i− 1]
esta ordenado de modo nao-decrescente.
Observe que o item (i) e valido antes da primeira iteracao, quando i = 2, pois o
vetor A[1, . . . , i− 1] contem somente um elemento e, portanto, sempre esta ordenado.
Para verificar (ii), suponha agora que o vetor A[1, . . . , i − 1] esta ordenado e o laco
para executa sua i-esima iteracao. O laco enquanto “move” passo a passo o elemento
A[i] para a esquerda ate encontrar sua posicao correta, deixando o vetor A[1, . . . , i]
ordenado. Por fim, precisamos mostrar que ao final da execucao o algoritmo ordena
todo o vetor A. Note que o laco termina quando i = n+ 1, de modo que a invariante
de laco considerada garante que A[1, . . . , i− 1] = A[1, . . . , n] esta ordenado, de onde
concluımos que o algoritmo esta correto.
Para calcular o tempo de execucao de Insertion sort, basta notar que a linha 1
e executada n vezes, as linhas 2, 3 e 7 sao executadas n − 1 vezes cada, e se ri e a
quantidade de vezes que o laco enquanto e executado na i-esima iteracao do laco
para, entao a linha 4 e executada∑n
i=2(ri) vezes, e as linhas 5 e 6 sao executadas∑ni=2(ri − 1) vezes cada uma. Por fim, a linha 8 e executada somente uma vez. Assim,
o tempo de execucao T (n) de Insertion sort e dado por
T (n) = n+ 3(n− 1) +n∑
i=2
ri + 2n∑
i=2
(ri − 1) + 1
= 4n− 2 + 3n∑
i=2
ri − 2n∑
i=2
1
= 2n+ 3n∑
i=2
ri.
Note que para de fato sabermos a eficiencia do algoritmo Insertion sort precisa-
mos saber o valor de cada ri, mas para isso e preciso assumir algo sobre a ordenacao
87
do vetor de entrada.
8.1.1 Analise de melhor caso, pior caso e caso medio
No Insertion sort, o melhor caso ocorre quando a sequencia de entrada esta ordenada
de modo crescente. Nesse caso, o laco da linha 4 e executado somente uma vez para
cada 2 ≤ i ≤ n, de modo que temos ri = 1. De fato, a condicao A[j] > atual sera falsa
ja na primeira iteracao do laco enquanto, pois aqui temos j = i− 1 e como o vetor de
entrada esta ordenado, temos A[i− 1] < A[i]. Portanto, nesse caso, temos que
T (n) = 2n+ 3n∑
i=2
ri
= 5n− 3
= Θ(n).
Geralmente estamos interessados no tempo de execucao de pior caso do algoritmo,
isto e, o maior tempo de execucao do algoritmo entre todas as entradas possıveis de um
dado tamanho. A analise de pior caso e muito importante, pois limita superiormente
o tempo de execucao para qualquer entrada, garantindo que o algoritmo nunca vai
demorar mais do que esse limite. Outra razao para a analise de pior caso ser considerada
e que para alguns algoritmos, o pior caso (ou algum caso proximo do pior) ocorre
com muita frequencia. O pior caso do Insertion sort acontece quando o vetor esta
ordenado de modo decrescente, pois o laco da linha 4 sera executado i vezes em cada
iteracao i do laco na linha 1, de modo que temos ri = i. Assim, temos
T (n) = 2n+ 3n∑
i=2
ri
= n2 + 2n− 6 (8.1)
= Θ(n2), (8.2)
Podemos concluir que assintoticamente o tempo de execucao do pior caso de
Insertion sort e menos eficiente que o tempo no melhor caso.
Como vimos anteriormente, o tempo de execucao do caso medio de um algoritmo e
a media do tempo de execucao dentre todas as entradas possıveis. Por exemplo, no
88
caso do Insertion sort, pode-se assumir que quaisquer das n! permutacoes dos n
elementos tem a mesma chance de ser o vetor de entrada. Note que, nesse caso, cada
numero tem a mesma probabilidade de estar em quaisquer das n posicoes do vetor.
Assim, em media, metade dos elementos em A[1, . . . , i− 1] sao menores que A[i], de
modo que na i-esima execucao do laco para, o laco enquanto e executado cerca de
i/2 vezes em media. Portanto, temos em media por volta de n(n − 1)/4 execucoes
do laco enquanto. Com uma analise simples do tempo de execucao do Insertion
sort que descrevemos anteriormente, obtemos que no caso medio, T (n) e uma funcao
quadratica em n, i.e., uma funcao da forma T (n) = a2n + bn + c, onde a, b e c sao
constantes que nao dependem de n.
Muitas vezes o tempo de execucao no caso medio e quase tao ruim quanto no
pior caso, como na analise do Insertion sort que fizemos anteriormente, onde para
ambos os casos obtivemos uma funcao quadratica no tamanho do vetor de entrada.
Mas e necessario deixar claro que esse nem sempre e o caso. Por exemplo, seja n o
tamanho de um vetor que desejamos ordenar. Um algoritmo de ordenacao chamado
Quicksort tem tempo de execucao de pior caso quadratico em n, mas em media o
tempo gasto e da ordem de n log n, que e muito menor que uma funcao quadratica em
n para valores grandes de n. Embora o tempo de execucao de pior caso do Quicksort
seja pior do que de outros algoritmos de ordenacao (e.g., Merge sort, Heapsort),
ele e comumente utilizado, dado que seu pior caso raramente ocorre. Por fim, vale
mencionar que nem sempre e simples descrever o que seria uma “entrada media” para
um algoritmo, e analises de caso medio sao geralmente mais complicadas que analises
de pior caso.
8.1.2 Uma analise mais direta
Nao precisamos fazer uma analise tao cuidadosa como a que fizemos na secao anterior.
Essa e uma das vantagens de se utilizar notacao assintotica para estimar tempo de
execucao de algoritmos. No que segue vamos fazer a analise do tempo de execucao
do Insertion sort de forma mais rapida, focando apenas nos pontos que realmente
importam. Todas as instrucoes de todas as linhas de Insertion sort sao executadas
em tempo constante, de modo que o que vai determinar a eficiencia do algoritmo e
a quantidade de vezes que os lacos para e enquanto sao executados. O laco para e
89
executado n− 1 vezes, mas a quantidade de execucoes do laco enquanto depende da
distribuicao dos elementos dentro do vetor A. Se A estiver em ordem decrescente, entao
as instrucoes dentro do laco enquanto sao executadas i vezes para cada execucao do
laco para (indexado por i), totalizando 1 + 2 + . . . + n − 1 = n(n − 1)/2 = Θ(n2)
execucoes. Porem, se A ja estiver corretamente ordenado no inıcio, entao o laco
enquanto e executado somente 1 vez para cada execucao do laco para, totalizando
n− 1 = Θ(n) execucoes, bem menos que no caso anterior.
Para deixar claro como a analise assintotica pode ser util para simplificar a analise,
imagine que um algoritmo tem tempo de execucao dado por T (n) = an2 + bn + c.
Em analise assintotica queremos focar somente no termo que e relevante para valores
grandes de n. Portanto, na maioria dos casos podemos esquecer as constantes envolvidas
em T (n) (nesse caso, a, b e c). Podemos tambem esquecer dos termos que dependem
de n mas que nao sao os termos de maior ordem (nesse caso, podemos esquecer do
termo an). Assim, fica facil perceber que temos T (n) = Θ(n2). Para verificar que essa
informacao e de fato verdadeira, basta tomar n0 = 1 e notar que para todo n ≥ n0
temos an2 ≤ an2 + bn + c ≤ (a + b + c)n2, i.e., fazemos c = a e C = a + b + c na
definicao da notacao Θ.
Com uma analise similar, podemos mostrar que para qualquer polinomio
f(n) =k∑
i=1
aini,
onde ai e constante para 1 ≤ i ≤ k, e ak > 0, temos f(n) = Θ(nk).
90
Capıtulo
9Merge sort
O algoritmo Merge sort e um algoritmo simples que faz uso do paradigma de divisao
e conquista. Dado um vetor de entrada A com n numeros, o Merge sort divide
A em duas partes de tamanho n/2, ordena as duas partes recursivamente e depois
combina as duas partes ordenadas em uma unica parte ordenada. O procedimento
Merge sort e como segue, onde Combina e um procedimento para combinar duas
partes ordenadas em uma so parte ordenada. Para ordenar um vetor A de n posicoes,
basta executar Merge sort (A, 1, n).
Algoritmo 24: Merge sort(A, inicio, fim)
1 se inicio < fim entao
2 meio = b(inicio+ fim)/2c3 Merge sort(A, inicio,meio)
4 Merge sort(A,meio+ 1, fim)
5 Combina(A, inicio,meio, fim)
Na Figura 14.3 ilustramos uma execucao do algoritmo Merge sort no vetor
A = [7, 3, 1, 10, 2, 8, 15, 6]. Note que na metade superior da figura corresponde as
chamadas recursivas nas linhas (3) e (4). A metade inferior da figura corresponde as
chamadas recursivas ao procedimento Combina (linha (5)). Logo a seguir temos o
algoritmo Combina.
Figura 9.1: Execucao de Merge sort(A, 1, n) para A = [7, 3, 1, 10, 2, 8, 15, 6].
Algoritmo 25: Combina(A, inicio,meio, fim)
1 n1 = meio− inicio+ 1
2 n2 = fim−meio3 cria vetores auxiliares E[1..(n1 + 1)] e D[1..(n2 + 1)]
4 E[n1 + 1] =∞5 D[n2 + 1] =∞6 para i = 1 ate n1 faca
7 E[i] = A[inicio+ i− 1]
8 para j = 1 ate n2 faca
9 D[j] = A[meio+ j]
10 i = 1
11 j = 1
12 para k = inicio ate fim faca
13 se E[i] ≤ D[j] entao
14 A[k] = E[i]
15 i = i+ 1
16 senao
17 A[k] = D[j]
18 j = j + 1
92
O procedimento Combina(A, inicio,meio, fim) cria um vetor E commeio−inicio+1 posicoes e um vetor D com fim−meio posicoes, que recebem, respectivamente, o
vetor ordenado A[inicio..meio] e A[meio+ 1..f im]. Comparando os elementos desses
dois vetores, e facil colocar em ordem todos esses elementos em A[inicio..fim]. Note
que por usar os vetores auxiliares E e D, o Merge sort nao e um algoritmo in-place.
Na Figura 9.2 temos uma simulacao da execucao de Combina(A, 1, 4, 8), onde
A = [1, 3, 7, 10, 2, 6, 8, 15].
Figura 9.2: Execucao de Combina(A, p, q, r) no vetor A = [1, 3, 7, 10, 2, 6, 8, 15] comparametros p = 1, q = 4 e r = 8.
Considere uma execucao de Combina ao receber um vetor A e parametros inicio,
meio e fim como entrada. Note que a linha 3 e executada em tempo Θ(fim− inicio)e todas as outras linhas sao executadas em tempo constante. O laco para na linha
(6) e executado meio− inicio+ 1 vezes, o laco para na linha (8) e executado fim− 1
vezes, e o laco para na linha (12)) e executado fim − inicio + 1 vezes. Se C(n) e
93
o tempo de execucao de Combina(A, inicio,meio, fim) onde n = fim− inicio + 1,
entao temos C(n) = Θ(n).
Vamos agora analisar o tempo de execucao do algoritmo Merge sort quando
ele e utilizado para ordenar um vetor com n elementos. Vimos que o tempo para
combinar as solucoes recursivas e Θ(n). Portanto, como os vetores em questao sao
sempre divididos ao meio no algoritmo Merge sort, seu tempo de execucao T (n)
e dado por T (n) = T (bn/2c) + T (dn/2e) + cn. Como estamos preocupados em fazer
uma analise assintotica, podemos assumir que c = 1, pois isso nao fara diferenca no
resultado obtido. Por ora, vamos desconsiderar pisos e tetos, considerar
T (n) = 2T (n/2) + n,
para n > 1, e T (n) = 1 para n = 1.
Como visto no Capıtulo 3, o tempo de execucao de Merge sort e dado por
T (n) = 2T (n/2) + n = Θ(n log n).
94
Capıtulo
10
Selection sort e Heapsort
Neste capıtulo vamos introduzir dois algoritmos para o problema de ordenacao, o
Selection sort e o Heapsort. O Selection sort e um algoritmo que sempre mantem
o vetor de entrada A dividido em dois subvetores contıguos, uma parte inicial Ae de A
contendo elementos nao ordenados, e a segunda parte Ad de A contendo os maiores
elementos de A (ja ordenados). A cada iteracao do algoritmo, o maior elemento x
do subvetor Ae e encontrado, e o subvetor Ad e aumentado de uma unidade com a
insercao do elemento x em sua posicao correta. O Heapsort utiliza uma estrutura
de dados chamada de heap binario (ou, simplesmente, heap) para encontrar o maior
elemento de um subvetor de forma eficiente. Dessa forma, o Heapsort pode ser visto
como uma versao mais eficiente do Selection sort.
10.1 Selection sort
O algoritmo Selection sort possui uma estrutura muito simples, contendo dois
lacos para aninhados. O primeiro laco e executado n − 1 vezes, de modo que em
cada iteracao desse laco, obtemos um vetor ordenado Ad que e uma unidade maior
que o vetor ordenado que tınhamos antes da iteracao. Ademais, o vetor Ad sempre
contem os maiores elementos de A. Para manter essa propriedade, a cada passo, o
maior elemento fora do subvetor ordenado Ad e adicionado ao inıcio de Ad. Abaixo
temos o pseudocodigo de Selection sort.
Algoritmo 26: Selection sort(A[1..n])
1 para i = n ate 2 faca
2 indiceMax = i
3 para j = i− 1 ate 1 faca
4 se A[j] > A[indiceMax] entao
5 indiceMax = j
6 troca A[indiceMax] com A[i]
Note que todas as linhas sao executadas em tempo constante e cada um dos lacos
para e executado Θ(n) vezes cada. Como um dos lacos esta dentro do outro, temos
que o tempo de execucao de Selection sort(A[1..n]) e Θ(n2).
Na Figura 10.1 temos um exemplo de execucao do algoritmo Selection sort(A).
No que segue vamos utilizar a seguinte invariante de laco para mostrar que o
algoritmo Selection sort(A[1..n]) funciona corretamente.
Invariante: Selection sort
Antes de cada iteracao do primeiro laco para (indexado por i), o subvetor
A[i+ 1..n] esta ordenado de modo nao-decrescente e contem os maiores elementos
de A.
Teorema 10.2
O algoritmo Selection sort(A) ordena um vetor A de modo nao-decrescente.
Demonstracao. Como inicialmente i = n, a invariante e trivialmente satisfeita. Su-
ponha agora que a invariante e valida imediatamente antes da i-esima iteracao do
primeiro laco para, i.e., o subvetor A[i+ 1..n] esta ordenado de modo nao-decrescente
e contem os maiores elementos de A. Precisamos mostrar que antes da (i− 1)-esima
iteracao o subvetor A[i..n] esta ordenado de modo nao-decrescente e contem os maiores
elementos de A. Mas note que na i-esima iteracao do primeiro laco para, o segundo
96
Figura 10.1: Execucao de Selection sort(A) no vetor A = [2, 5, 1, 4, 3].
laco para (na linha 3) verifica qual o ındice indiceMax do maior elemento do vetor
A[1..i− 1] (isso pode ser formalmente provado por uma invariante de laco!). Na linha 6,
o maior elemento de A[1..i − 1] e trocado de lugar com o elemento A[i], garantindo
que A[i..n] esta ordenado e contem os maiores elementos de A.
Por fim, note que na ultima vez que a linha 1 e executada temos i = 1. Assim,
pela invariante de laco, o vetor A[2..n] esta ordenado. Como sabemos que os maiores
elementos de A estao em A[2..n], concluımos que o vetor A[1..n] esta ordenado.
10.2 Heapsort
O Heapsort e um algoritmo de ordenacao com tempo de execucao de pior caso
Θ(n log n), como o Merge sort. O Heapsort e um algoritmo in-place, apesar de
nao ser estavel.
97
O algoritmo troca o elemento na raiz do heap (maior elemento) com o elemento
na ultima posicao do vetor e restaura a propriedade de heap para A[1, . . . , n− 1], em
seguida fazemos o mesmo para A[1, . . . , n− 2] e assim por diante. O algoritmo e como
segue.
Algoritmo 27: Heapsort (A)
1 Construa-heap(A)
2 para i = n ate 2 faca
3 troca A[1] com A[i]
4 A.tam-heap = A.tam-heap− 1
5 Max-conserta-heap(A, 1)
Na Figura 10.2 temos um exemplo de execucao do algoritmo Heapsort.
Uma vez que ja provamos a corretude de Construa-heap e Max-conserta-
heap (veja Capıtulo 5), a prova de corretude do algoritmo Heapsort e bem simples.
Utilizaremos a seguinte invariante de laco.
Invariante: Heapsort
Antes de cada iteracao do laco para (indexado por i) temos que:
• O vetor A[i + 1..n] esta ordenado de modo nao-decrescente e contem os
maiores elementos de A.
• A.tam-heap = i e o vetor A[1..A.tam-heap] e um heap maximo.
Teorema 10.2
O algoritmo Heapsort(A) ordena o vetor A de modo nao-decrescente.
Demonstracao. A linha 1 constroi um heap a partir do vetor A. Assim, como inicial-
mente i = n, a invariante e trivialmente satisfeita. Suponha agora que a invariante e
valida imediatamente antes da i-esima iteracao do laco, i.e., o subvetor A[i+1..n] esta or-
98
Figura 10.2: Algoritmo Heapsort executado no vetor A = [4, 7, 3, 8, 1, 9]. Note que aprimeira arvore da figura e o heap obtido por Construa-heap(A).
denado de modo nao-decrescente e contem os maiores elementos de A, e A.tam-heap = i
onde A[1..A.tam-heap] e um heap maximo. Precisamos mostrar que a invariante e
valida antes da (i− 1)-esima iteracao. Na i-esima iteracao do primeiro laco, o algo-
ritmo troca A[1] com A[i], colocando o maior elemento de A[1..A.tam-heap] em A[i],
diminui A.tam-heap em uma unidade, fazendo com que A.tam-heap = i− 1, e executa
Max-conserta-heap(A, 1). Mas note que o unico elemento de A[1..A.tam-heap] que
pode nao satisfazer a propriedade de heap e A[1]. Como sabemos que Max-conserta-
heap(A, 1) funciona corretamente, temos que apos esse comando A[1..A.tam-heap] e
um heap maximo. Como o maior elemento de A[1..A.tam-heap] esta em A[i] e dado
que sabemos que A[i+1..n] esta ordenado de modo nao-decrescente e contem os maiores
99
elementos de A, concluımos que o vetor A[i..n] esta ordenado de modo nao-decrescente
e contem os maiores elementos de A. Assim, mostramos que a invariante e valida antes
da (i− 1)-esima iteracao do laco.
Ao final da execucao do laco, temos i = 1. Portanto, pela invariante, sabemos que
A[2..n] esta ordenado de modo nao-decrescente e contem os maiores elementos de A.
Como A[2..n] contem os maiores elementos de A, o menor elemento certamente esta
em A[1], de onde concluımos que A esta ordenado.
Claramente, esse algoritmo tem tempo de execucao O(n log n). De fato, Construa-
heap e feito em tempo O(n) e como sao realizadas n− 1 execucoes do laco para, e
Max-conserta-heap e executado em tempo O(log n), temos que o tempo total gasto
por Heapsort e O(n log n). Ademais, nao e difıcil perceber que se o vetor de entrada
estiver ordenado, Heapsort leva tempo Ω(n log n). Portanto, o tempo de execucao do
Heapsort e Θ(n log n).
100
Capıtulo
11
Quicksort
O algoritmo Quicksort e um algoritmo que resolve o problema de ordenacao e tem
tempo de execucao de pior caso Θ(n2), bem pior que o tempo O(n log n) gasto por
Heapsort e Mergesort. Porem, muitas vezes o Quicksort oferece a melhor escolha
na pratica. Isso se da pelo fato de seu tempo de execucao ser em media Θ(n log n) e
a constante escondida em Θ(n log n) ser bem pequena. Vamos descrever o algoritmo
Quicksort e fazer uma analise do tempo medio de execucao do Quicksort.
Seja A[1..n] um vetor. O algoritmo Quicksort faz uso do metodo de divisao
e conquista (assim como o Mergesort). O algoritmo funciona como segue: um
elemento de A chamado de pivo, e escolhido dentre todos os elementos de A. Feito
isso, o Quicksort reorganiza o vetor A de modo que o pivo fique em sua posicao final
(no vetor ordenado), digamos A[x], todas as chaves em A[1, . . . , x − 1] sao menores
que o pivo e todas as chaves em A[x + 1, . . . , n] sao maiores que o pivo. O proximo
passo e ordenar recursivamente os vetores A[1, . . . , x−1] e A[x+ 1, . . . , n]. O algoritmo
Particao abaixo reorganiza o vetor A[inıcio, . . . , f im] in-place, retornando a posicao
correta do pivo escolhido.
Algoritmo 28: Particao(A, inıcio, fim)
1 pivo = A[fim]
2 i = inıcio
3 para j = inıcio ate fim− 1 faca
4 se A[j] ≤ pivo entao
5 troca A[i] e A[j]
6 i = i+ 1
7 troca A[i] e A[fim]
8 retorna i
Na Figura 11.1 temos um exemplo de execucao do procedimento Particao.
A seguinte invariante de laco pode ser utilizada para provar a corretude do algoritmo
Particao(A, inıcio, fim).
Invariante: Particao
Antes de cada iteracao do laco para indexada por j, temos A[fim]=pivo e vale
que
(i) para inıcio ≤ k ≤ i− 1, temos A[k] ≤ pivo;
(ii) para i ≤ k ≤ j − 1, temos A[k] > pivo.
Teorema 11.2
O algoritmo Particao(A[1..n]) retorna um ındice i tal que o pivo esta na posicao
A[i], todo elemento em A[1..i− 1] e menor ou igual ao pivo, e todo elemento em
A[i+ 1..n] e maior que o pivo.
Demonstracao. Como o pivo esta inicialmente em A[fim], nao precisamos nos pre-
ocupar com a condicao A[fim]=pivo na invariante, dado que A[fim] so e alterado
apos a execucao do laco. Antes da primeira iteracao do laco para temos i = inıcio
102
e j = inıcio, logo as condicoes (i) e (ii) sao trivialmente satisfeitas. Suponha que a
invariante e valida antes da iteracao j do laco para, i.e., para inıcio ≤ k ≤ i− 1, temos
A[k] ≤ pivo, e para i ≤ k ≤ j − 1, temos A[k] > pivo. Provaremos que ela continua
valida imediatamente antes da (j+ 1)-esima iteracao. Na j-esima iteracao do laco, caso
A[j] > pivo, a unica operacao feita e alterar j para j + 1, de modo que a condicao (ii)
continua valida (nesse caso a condicao (i) e claramente satisfeita). Caso A[j] ≤ pivo,
trocamos A[i] e A[j] de posicao, de modo que agora temos que todo elemento em
A[1..i] e menor ou igual ao pivo (pois sabıamos que, para inıcio ≤ k ≤ i− 1, tınhamos
A[k] ≤ pivo). Feito isso, i e incrementado para i+ 1. Assim, como para inıcio ≤ k ≤ i,
temos A[k] ≤ pivo, a invariante continua valida.
Ao fim da execucao do laco, temos j = fim, de modo que o teorema segue
diretamente da validade da invariante de laco e do fato da linha 7 trocar A[i] e A[fim]
de posicao.
Como o laco para e executado fim−inıcio vezes, o tempo de execucao de Particao
e Θ(fim− inıcio). Agora podemos descrever o algoritmo Quicksort. Para ordenar
A basta executar Quicksort(A, 1, n).
Algoritmo 29: Quicksort(A, inıcio, fim)
1 se inıcio < fim entao
2 i = Particao(A, inıcio, fim)
3 Quicksort (A, inıcio, i− 1)
4 Quicksort (A, i+ 1, fim)
Na Figura 11.2 temos um exemplo de execucao do procedimento Quicksort.
Para provar que o algoritmo Quicksort funciona corretamente, usaremos inducao
no ındice i.
Teorema 11.3: Corretude de Quicksort
O algoritmo Quicksort(A[inıcio..f im]) ordena o vetor A de modo nao-
descrescente.
Demonstracao. Claramente o algoritmo ordena um vetor que contem somente um
103
Figura 11.1: Particao executado em A = [3, 8, 6, 1, 5, 2, 4] com inıcio = 1 e fim = 7.
elemento (pois esse vetor ja esta trivialmente ordenado). Seja A um vetor com n
elementos e suponha que o algoritmo funciona corretamente para vetores com menos
que n elementos. Note que a linha 2 devolve um ındice i que contem um elemento em
sua posicao final na ordenacao desejada, e todos os elementos de A[inıcio, i− 1] sao
menores que A[i], e todos os elementos de A[i+ 1, fim] sao maiores que A[i]. Assim, ao
executar a linha 3, por hipotese de inducao sabemos que A[inıcio, i−1] estara ordenado.
Da mesma forma, ao executar a linha 4, sabemos que A[i+ 1, fim] estara ordenado.
Portanto, todo o vetor A fica ordenado ao final da execucao de Quicksort.
104
Figura 11.2: Algoritmo Quicksort executado no vetor A = [3, 9, 1, 2, 7, 4, 8, 5, 0, 6]com inıcio = 1 e fim = 10.
11.1 Tempo de execucao
O tempo de execucao de Quicksort depende fortemente de como as chaves estao
distribuıdas dentro do vetor de entrada A. Se na linha 1 de Quicksort, o elemento
escolhido como pivo e sempre o maior do vetor analisado, entao o problema de ordenar
e sempre quebrado em dois subproblemas, um de tamanho n− 1 e um de tamanho 0.
Lembrando que o tempo de execucao de Particao(A, 1, n) e Θ(n), temos que, nesse
caso, o tempo de execucao de Quicksort e dado por T (n) = T (n − 1) + Θ(n). Se
105
esse fenomeno ocorre em todas as chamadas recursivas, entao temos
T (n) = T (n− 1) + n
= T (n− 2) + n+ (n− 1)
...
= T (1) +n−1∑i=2
i
= 1 +(n+ 1)(n− 2)
2
= Θ(n2)
Entao, no caso analisado, T (n) = Θ(n2). Intuitivamente, esse e o pior caso possıvel.
Mas pode ser que o vetor seja sempre dividido em duas partes de mesmo tamanho,
tendo tempo de execucao dado por T (n) = 2T (n/2) + Θ(n) = Θ(n log n).
Felizmente, para grande parte das possıveis ordenacoes iniciais do vetor A, o tempo
de execucao do caso medio para o Quicksort e assintoticamente bem proximo de
Θ(n log n). Por exemplo, se Particao divide o problema em um subproblema de
tamanho (n− 1)/1000 e outro de tamanho 999(n− 1)/1000, o tempo de execucao e
dado por
T (n) = T ((n− 1)/1000) + T (999(n− 1)n/1000) + Θ(n)
= T (n/1000) + T (999n/1000) + Θ(n).
E possıvel mostrar que temos T (n) = O(n log n). De fato, para qualquer constante
k > 1 (e.g., k = 10100), se Particao divide A em partes de tamanho aproximadamente
n/k e (k − 1)n/k, o tempo de execucao ainda e O(n log n).
Vamos utilizar o metodo da substituicao para mostrar que T (n) = O(n log n).
Assumindo que T (n) ≤ c para alguma constante c ≥ 1 e todo n ≤ k− 1. Vamos provar
que T (n) = T (n/k) + T ((k − 1)n/k) + n e no maximo
dn log n+ n
para todo n ≥ k e algum d > 0. Comecamos notando que T (k) ≤ T (k−1)+T (1)+k ≤
106
2c + k ≤ dk log k + k. Suponha que T (m) ≤ dm logm + m para todo k < m < n e
vamos analisar T (n).
T (n) = T (n/k) + T ((k − 1)n/k) + n
≤ d(nk
log(nk
))+n
k+ d
((k − 1)n
klog
((k − 1)n
k
))+
(k − 1)n
k+ n
= d(nk
log(nk
))+ d
((k − 1)n
k
(log(k − 1) + log
(nk
)))+ 2n
= dn log n+ n− dn log k +
(d(k − 1)n
klog(k − 1) + n
)≤ dn log n+ n.
onde a ultima desigualdade vale se d ≥ k/ log k. Pois para tal valor de d temos
dn log k ≥(d(k − 1)n
klog(k − 1) + n
).
Portanto, acabamos de mostrar que T (n) = O(n log n) quando o Quicksort divide o
vetor A sempre em partes de tamanho aproximadamente n/k e (k − 1)n/k. A ideia
por tras desse fato que, a princıpio, pode parecer contraintuitivo, e que pelo fato do
tamanho da arvore de recursao nesse caso ser logk/(k−1) n = Θ(log n), e em cada passo
e executada uma quantidade de passos proporcional ao tamanho do vetor analisado,
entao o tempo total de execucao e O(n log n).
Vamos agora analisar formalmente o tempo de execucao de pior caso. O pior caso e
dado por T (n) = max0≤x≤n−1(T (x) + T (n− x− 1)) + n. Vamos utilizar o metodo da
substituicao para mostrar que T (n) ≤ n2. Supondo que T (m) ≤ m2 para todo m < n,
obtemos
T (n) ≤ max0≤x≤n−1
(x2 + c(n− x− 1)2) + n
= max0≤x≤n−1
(x2 + (n− x− 1)2) + n
≤ (n− 1)2 + n
= n2 − (2n− 1) + n
≤ n2,
107
onde o maximo na segundo linha e atingido quando x = 0 ou x = n − 1. Para ver
isso, seja f(x) = (x2 + (n− x− 1)2) e note que f ′(x) = 2x− 2(n− x− 1), de modo
que f ′((n − 1)/2) = 0. Assim, (n − 1)/2 e um ponto maximo ou mınimo. Como
f ′′((n− 1)/2) > 0, temos que (n− 1)/2 e ponto de mınimo de f . Portanto, os pontos
maximos sao x = 0 e x = n− 1.
Vamos agora analisar o que acontece no caso medio, quando todas as ordenacoes
possıveis dos elementos de A tem a mesma chance de serem o vetor de entrada A.
Suponha agora que o pivo e escolhido uniformemente ao acaso dentre as chaves contidas
em A, i.e., cada uma das possıveis n! ordenacoes de A tem a mesma chance de ser a
ordenacao do vetor de entrada A.
E facil ver que o tempo de execucao de Quicksort e dominado pela quantidade
de operacoes feitas na linha 4 de Particao, dentro do laco para. Mostraremos agora
que a variavel aleatoria X que conta a quantidade de vezes que essa linha e executada
durante uma execucao completa de Quicksort tem valor esperado O(n log n).
Sejam o1, . . . , on os elementos de A em sua ordenacao final (apos estarem ordenados
de modo crescente), i.e., o1 < o2 < . . . < on. A primeira observacao importante e
que dois elementos oi e oj sao comparados no maximo uma vez, pois elementos sao
comparados somente com o pivo e uma vez que algum elemento e o pivo ele nunca mais
sera comparado com nenhum outro elemento. Defina Xij como a variavel aleatoria
indicadora para o evento “oi e comparado com oj”.
Vamos calcular P (oi ser comparado com oj). Comecemos notando que para oi ser
comparado com oj, um dos dois precisa ser o primeiro elemento de oi, oi+1, . . . , oja ser escolhido como pivo. De fato, caso ok com i < k < j seja escolhido como pivo
antes de oi e oj, entao oi e oj irao para partes diferentes do vetor ao fim da chamada
atual ao algoritmo Particao e nunca serao comparados. Portanto,
P (oi ser comparado com oj) = P (oi ou oj ser o primeiro a ser escolhido
como pivo em oi, oi+1, . . . , oj)
=2
j − i+ 1.
108
Voltando nossa atencao para a variavel aleatoria X, temos
X =n−1∑i=1
n∑j=i+1
Xij.
Utilizando a linearidade da esperanca, concluımos que
E[X] =n−1∑i=1
n∑j=i+1
E[Xij]
=n−1∑i=1
n∑j=i+1
P (oi ser comparado com oj)
=n−1∑i=1
n∑j=i+1
2
j − i+ 1
< 2n−1∑i=1
n∑k=1
1
k
=n−1∑i=1
O(log n)
= O(n log n).
Portanto, concluımos que o tempo medio de execucao de Quicksort e O(n log n).
Se, em vez de escolhermos um elemento fixo para ser o pivo, escolhermos um dos
elementos do vetor uniformemente ao acaso, entao uma analise analoga a que fizemos
aqui mostra que o tempo esperado de execucao dessa versao aleatoria de Quicksort
e O(n log n). Assim, sem supor nada sobre a entrada do algoritmo, garantimos um
tempo de execucao esperado de O(n log n).
109
110
Capıtulo
12
Ordenacao em tempo linear
Vimos alguns algoritmos com tempo de execucao (de pior caso ou caso medio) Θ(n log n).
Mergesort e Heapsort tem esse limitante no pior caso e Quicksort possui tempo
de execucao esperado da ordem de n log n. Note que esses 3 algoritmos sao baseados em
comparacoes entre os elementos de entrada. E possıvel mostrar, analisando uma arvore
de decisao geral, que qualquer algoritmo baseado em comparacoes requer Ω(n log n)
comparacoes no pior caso. Portanto, Mergesort e Heapsort sao assintoticamente
otimos.
Algumas vezes, quando sabemos informacoes extras sobre os dados de entrada,
e possıvel obter um algoritmo de ordenacao em tempo linear. Obviamente, tais
algoritmos nao sao baseados em comparacoes. Para exemplificar, vamos discutir o
algoritmo Counting sort a seguir.
12.1 Counting sort
Assuma que o vetor de entrada A contem somente numeros inteiros entre 0 e k. Quando
k = O(n), o algoritmo Counting sort e executado em tempo Θ(n). Sera necessario
utilizar um vetor extra B com n posicoes e um vetor C com k posicoes, de modo que o
algoritmo nao e in-place. A ordem relativa de elementos iguais sera mantida, de modo
que o algoritmo e estavel.
Para cada elemento x em A, o Counting sort verifica quantos elementos de A
sao menores ou iguais a x. Assim, o algoritmo consegue colocar x na posicao correta
sem precisar fazer nenhuma comparacao. O algoritmo pode ser visto abaixo.
Algoritmo 30: Counting sort(A, k)
/* C e um vetor auxiliar e B guardara o vetor ordenado */
1 Sejam B[1..A.tamanho] e C[0..k] novos vetores
/* Inicializando o vetor C */
2 para i = 0 ate k faca
3 C[i] = 0
/* C[i] contera a quantidade de ocorrencias de i em A */
4 para j = 1 ate n faca
5 C[A[j]] = C[A[j]] + 1
/* C[i] contera a quantidade de ocorrencias de elementos de 0, . . . iem A */
6 para i = 1 ate k faca
7 C[i] = C[i] + C[i− 1]
/* Colocando o resultado da ordenac~ao de A em B */
8 para j = n ate 1 faca
9 B[C[A[j]]] = A[j]
10 C[A[j]] = C[A[j]]− 1
11 retorna B
A Figura 12.1 contem um exemplo de execucao do algoritmo Counting sort.
Os quatro lacos para existentes no algoritmo Counting-sort sao executados, res-
pectivamente, k, n, k e n vezes. Portanto, claramente a complexidade do procedimento
e Θ(n+ k). Concluımos entao que quando k = O(n), o algoritmo Counting sort e
executado em tempo Θ(n), de modo que e assintoticamente mais eficiente que todos os
algoritmos de ordenacao vistos aqui. Uma caracterıstica importante do algoritmo e
que ele e estavel. Esse algoritmo e comumente utilizado como subrotina de um outro
algoritmo de ordenacao em tempo linear, chamado Radix sort, e e essencial para o
funcionamento do Radix sort que o Counting sort seja estavel.
112
Figura 12.1: Execucao do Counting sort no vetor A = [3, 0, 5, 4, 3, 0, 1, 2].
113
114
Parte
IV
Tecnicas de construcao de algoritmos
Capıtulo
13
Programacao dinamica
“Dynamic programming is a fancy name for
divide-and-conquer with a table.”
Ian Parberry — Problems on Algorithms, 1995.
Programacao dinamica e uma importante tecnica de construcao de algoritmos, utili-
zada em problemas cujas solucoes podem ser modeladas de forma recursiva. Assim,
como na divisao e conquista, um problema gera subproblemas que serao resolvidos
recursivamente. Porem, quando a solucao de um subproblema precisa ser utilizada
varias vezes em um algoritmo de divisao e conquista, a programacao dinamica pode ser
uma eficiente alternativa no desenvolvimento de um algoritmo para o problema. Uma
das caracterısticas mais marcantes da programacao dinamica e evitar resolver o mesmo
subproblema diversas vezes. Isso pode ser feito de duas formas (abordagens top-down
e bottom-up), que veremos ao longo deste capıtulo.
13.1 Um problema simples
Antes de discutirmos a tecnica de programacao dinamica, vamos analisar o problema de
encontrar o n-esimo numero da sequencia de Fibonacci para obter um pouco de intuicao
sobre o que sera discutido adiante. A sequencia 1, 1, 2, 3, 5, 8, 13, 21, 34, . . . e conhecida
como sequencia de Fibonacci. O n-esimo termo dessa sequencia, denotado por F (n),
e dado por F (1) = 1, F (2) = 1 e para n ≥ 3 temos F (n) = F (n − 1) + F (n − 2).
Assim, o seguinte algoritmo recursivo para calcular o n-esimo numero da sequencia de
Fibonacci e muito natural.
Algoritmo 31: Fibonacci(n)
1 se n ≤ 2 entao
2 retorna 1
3 retorna Fibonacci(n− 1) + Fibonacci(n− 2)
O algoritmo acima e extremamente ineficiente. De fato, muito trabalho repetido
e feito, pois subproblemas sao resolvidos recursivamente diversas vezes. A Figura ??
mostra como alguns subproblemas sao resolvidos varias vezes em uma chamada a
Fibonacci(5).
Podemos estimar o metodo da substituicao para mostrar que o tempo de execucao
T (n) = T (n − 1) + T (n − 2) + 1 de Fibonacci(n) e Ω((
(1 +√
5)/2)n)
. Para ficar
claro de onde tiramos o valor((1 +
√5)/2
)n, vamos provar que T (n) ≥ xn para algum
x ≥ 1 de modo que vamos verificar qual o maior valor de x que conseguimos obter.
Seja T (1) = 1 e T (2) = 3. Vamos provar o resultado para todo n ≥ 2. Assim, temos
que
T (2) ≥ x2,
para todo x ≥√
3 ≈ 1, 732.
Suponha que T (m) ≥ xn para todo 2 ≤ m ≤ n− 1. Assim, aplicando isso a T (n)
118
temos
T (n) = T (n− 1) + T (n− 2) + 1
≥ xn−1 + xn−2
≥ xn−2(1 + x).
Note que 1 + x ≥ x2 sempre que (1 −√
5)/2 ≤ x ≤ (1 +√
5)/2. Portanto, fazendo
x = (1 +√
5)/2 e substituindo em T (n), obtemos
T (n) ≥
(1 +√
5
2
)n−2(1 +
(1 +√
5
2
))
≥
(1 +√
5
2
)n−2(1 +√
5
2
)2
=
(1 +√
5
2
)n
≈ (1, 618)n.
Portanto, acabamos de provar que o algoritmo Fibonacci e de fato muito ineficiente,
tendo tempo de execucao T (n) = Ω((1, 618)n
).
Mas como podemos evitar que o algoritmo repita trabalho ja realizado? Uma forma
possıvel e salvar o valor da solucao de um subproblema em uma tabela na primeira vez
que ele for calculado. Assim, sempre que precisarmos desse valor, a tabela e consultada
antes de resolver o subproblema novamente. O seguinte algoritmo e uma variacao
de Fibonacci onde cada vez que um subproblema e resolvido, o valor e salvo no vetor F .
Algoritmo 32: Fibonacci-TD(n)
1 Cria vetor F [1..n]
2 F[1] = 1
3 F[2] = 1
4 para i = 3 ate n faca
5 F [i] = −1
6 retorna Fib-recursivo-TD(n)
119
Algoritmo 33: Fib-recursivo-TD(n)
1 se F [n] ≥ 0 entao
2 retorna F [n]
3 F [n] = Fib-recursivo-TD(n− 1) + Fib-recursivo-TD(n− 2)
4 retorna F [n]
O algoritmo Fibonacci-TD inicializa o vetor F [0..n] com os valores para F [0] e
F [1], e todos os outros valores sao inicializados com −1. Feito isso, o procedimento
Fib-recursivo-TD e chamado para calcular F [n]. Note que Fib-recursivo-TD
tem a mesma estrutura do algoritmo recursivo natural Fibonacci, com a diferenca
que em Fib-recursivo-TD, e realizada uma verificacao em F antes de tentar resolver
F [n].
Como cada subproblema e resolvido somente uma vez em uma execucao de Fib-
recursivo-TD e todas as operacoes realizadas levam tempo constante, entao, no-
tando que existem n subproblemas (F [0], F [1], . . . , F [n− 1]), o tempo de execucao de
Fibonacci-TD e Θ(n).
Note que no calculo de Fib-recursivo-TD(n) e necessario resolver Fib-recursivo-
TD(n − 1) e Fib-recursivo-TD(n − 2). Como o calculo do n-esimo numero da
sequencia de Fibonacci precisa somente dos dois numeros anteriores, podemos desenvol-
ver um algoritmo nao recursivo que calcula os numeros da sequencia em ordem crescente.
Dessa forma, nao e preciso verificar se os valores necessarios ja foram calculados, pois
temos a certeza que isso ja aconteceu.
Algoritmo 34: Fibonacci-BU(n)
1 Cria vetor F [1..n]
2 F [1] = 1
3 F [2] = 1
4 para i = 3 ate n faca
5 F [i] = F [i− 1] + F [i− 2]
6 retorna F [n]
120
13.2 Aplicacao e caracterısticas principais
Problemas em que a programacao dinamica pode ser aplicada em geral sao problemas
de otimizacao, i.e., problemas onde estamos interessados em maximizar ou minimizar
certa quantidade dadas algumas restricoes. Algumas vezes a programacao dinamica
pode ser usada em problemas onde estamos interessados em determinar uma quantidade
recursivamente.
Abaixo definimos subestrutura otima e sobreposicao de problemas, duas carac-
terısticas que um problema deve ter para que programacao dinamica seja aplicada com
sucesso.
Definicao 13.1: Subestrutura otima
Um problema tem subestrutura otima se uma solucao otima para o problema
pode ser obtida atraves de solucoes otimas de subproblemas.
Definicao 13.2: Sobreposicao de subproblemas
Um problema tem sobreposicao de problemas quando pode ser dividido em
subproblemas que sao utilizados repetidamente em um algoritmo recursivo que
resolve o problema.
Se um problemas possui subestrutura otima e sobreposicao de subproblemas, dizemos
que e um problema de programacao dinamica. Para clarear o entendimento sobre as
Definicoes 13.1 e 13.2, vamos analisar um classico problema de decidir em que ordem
multiplicamos uma sequencia de matrizes. No que segue, assuma que a multiplicacao
AB de uma matriz A de ordem k × ` por uma matriz B de ordem `×m realiza cerca
de k`m operacoes. O problema a seguir servira para exemplificar os topicos discutidos
nesta secao.
121
Problema 13.3: Multiplicacao de sequencias de matrizes
122
Dadas matrizes M1, . . . ,Mk tais que Mi e uma matriz mi×mi+1, para 1 ≤ i ≤ k,
encontrar a ordem em que precisamos multiplicar as matrizes para que o produto
M1M2 . . .Mk seja feito da forma mais eficiente possıvel.
Perceba que a ordem em que multiplicamos as matrizes e essencial para garantir a
eficiencia do produto total. Por exemplo, considere k = 3, i.e., matrizes M1, M2 e M3,
onde m1 = 1000, m2 = 2, m3 = 1000 e m4 = 2. Se fizermos primeiro o produto M1M2,
i.e., estamos realizando a multiplicacao ((M1M2)M3), entao a quantidade de operacoes
realizadas e de cerca de
m1m2m3 +m1m3m4 = m1m3(m2 +m4) = 4000000.
Porem, se calcularmos primeiro M2M3, i.e., multiplicamos (M1(M2M3)), entao a
quantidade de operacoes realizadas e de cerca de
m2m3m4 +m1m2m4 = m2m4(m1 +m3) = 8000.
Claramente, pode haver uma grande diferenca na eficiencia dependendo da ordem em
que as multiplicacoes sao realizadas.
Uma forma de ver que o problema de multiplicar sequencia de matrizes possui
subestrutura otima e notar o seguinte: Uma forma otima de multiplicar matrizes
M1 . . .Mk e encontrar o ındice 1 ≤ i ≤ k tal que a forma otima de multiplicar
M1 . . .Mk e multiplicar (M1 . . .Mi) e (Mi+1 . . .Mk) de forma otima e depois efetuar o
produto (M1 . . .Mi)(Mi+1 . . .Mk). Portanto, para multiplicar (M1M2 . . .Mi) de forma
otima, precisamos resolver os subproblemas de multiplicar de forma otima (M1 . . .Mi)
e (Mi+1 . . .Mk).
Para encontrar o melhor ındice i para dividir o problema, precisamos considerar
todas as possibilidades, i.e., i = 1, i = 2, . . ., i = k − 1. Assim, ja para escolhermos o
primeiro ındice i para dividir o problema inicial em dois subproblemas, ja precisamos
considerar o problema de multiplicar de forma otima a sequencia M1 . . .Mi, para
1 ≤ i ≤ k − 1. Mas, por exemplo, para resolver o subproblema (M1 . . .Mi) precisamos
considerar todos os subproblemas de multiplicar (M1 . . .Mj) para 1 ≤ j ≤ i− 1, que
sao subproblemas que ja foram analisados antes. Portanto, e facil notar que o problema
possui a propriedade de sobreposicao de subproblemas. A programacao dinamica salva
123
cada subproblema analisado em uma tabela (ou uma matriz) evitando a resolucao de
um mesmo subproblema repetidas vezes.
As propriedades de subestrutura otima e sobreposicao de subproblemas definem se
um problema de otimizacao pode ser atacado de forma eficiente por um algoritmo de
programacao dinamica.
Em geral, o tempo de execucao de algoritmos de programacao dinamica e deter-
minado por dois fatores: (i) a quantidade de subproblemas que uma solucao otima
utiliza; (ii) quantidade de possibilidades analisadas para determinar que subproblemas
sao utilizados em uma solucao otima. No exemplo do problema de multiplicacao
de uma sequencia de matrizes, temos que (i) o problema sempre e dividido em dois
subproblemas, e (ii) se o subproblema possui k matrizes, analisamos k−1 subproblemas
para decidir quais duas subsequencias compoem a solucao otima.
Dado um problema, podemos dividir os passos para a elaboracao de um algoritmo
de programacao dinamica para o problema como na definicao abaixo.
Definicao 13.4: Construindo algoritmos de programacao dinamica
Os seguintes tres passos compoem as etapas de construcao de um algoritmo de
programacao dinamica.
(1) Caracterizacao da estrutura otima e do valor de uma solucao otima recursi-
vamente;
(2) Calculo do valor de uma solucao otima;
(3) Construcao de uma solucao otima.
Antes de resolvermos alguns problemas utilizando a tecnica de programacao dinamica
seguindo os passos acima, vamos discutir brevemente duas formas de implementar essa
tecnica, que sao as abordagens top-down e bottom-up.
Na abordagem top-down, o algoritmo e desenvolvido de forma recursiva natural,
com a diferenca que, sempre que um subproblema for resolvido, o resultado e salvo em
uma tabela. Assim, sempre que o algoritmo precisar da solucao de um subproblema,
ele consulta a tabela antes de resolver o subproblema. Em geral, algoritmos top-down
sao compostos por dois procedimentos, um que faz uma inicializacao de variaveis e
124
prepara a tabela, e outro procedimento que compoe o analogo a um algoritmo recursivo
natural para o problema. Veja os Algoritmos 32 e 33.
Na abordagem bottom-up, e necessario entender quais os tamanhos dos subproble-
mas que precisam ser resolvidos antes de resolvermos o problema. Assim, resolvendo os
subproblemas em ordem crescente de tamanho, i.e., comecando pelos menores, conse-
guimos garantir que ao resolver um subproblema de tamanho n, todos os subproblemas
menores necessarios ja foram resolvidos. Essa abordagem dispensa verificar se um dado
subproblema ja foi resolvido, dado que temos a certeza que isso ja aconteceu.
Em geral as duas abordagens fornecem algoritmos com mesmo tempo de execucao
assintotico. No final deste capıtulo apresentamos uma comparacao entre aspectos de
algoritmos top-down e bottom-up.
13.3 Utilizando programacao dinamica
Nesta secao vamos desenvolver e analisar algoritmos de programacao dinamica para
diversos problemas de programacao dinamica, discutindo algoritmos top-down e bottom-
up para alguns desses problemas.
13.3.1 Corte de barras
Imagine que uma empresa corta e vende pedacos de barras de ferro. As barras sao
vendidas em pedacos de tamanho inteiro, onde uma barra de tamanho i tem preco de
venda pi. Por alguma razao, barras de tamanho menor podem ter um preco maior que
barras maiores. A empresa deseja cortar uma barra de tamanho inteiro e vender os
pedacos de modo a maximizar o lucro obtido.
Problema 13.1: Corte de barras
Sejam p1, . . . , pn inteiros positivos que correspondem, respectivamente, ao preco
de venda de barras de tamanho 1, . . . , n. Dado um inteiro positivo n, o problema
consiste em maximizar o lucro `n obtido com a venda de uma barra de tamanho
n, que pode ser vendida em pedacos de tamanho inteiro.
Para exemplificar o problema, considere uma barra de tamanho 6 com precos dos
125
pedacos como na tabela abaixo.
n p1 p2 p3 p4 p5 p6
6 3 8 14 15 10 20
Tabela 13.1: Precos para o problema do corte de uma barra de tamanho 6.
Note que se a barra for vendida sem nenhum corte, entao temos lucro `6 = 20.
Caso cortemos um pedaco de tamanho 5, entao a unica possibilidade e vender uma
parte de tamanho 5 e outra de tamanho 1, que fornece um lucro de `6 = p5 + p1 = 13,
o que e pior que vender a barra inteira. Caso efetuemos um corte de tamanho 4, o
que aparentemente e uma boa opcao (dado que p4 e um valor alto), entao o melhor
a se fazer e vender uma parte de tamanho 4 e outra de tamanho 2, obtendo lucro
`6 = p4 + p2 = 23. Porem, se vendermos dois pedacos de tamanho 3, obtemos um lucro
total de `6 = 2p3 = 28, que e o maior lucro possıvel. De fato, vender somente pedacos
de tamanho 2 ou 1 garantira um lucro menor.
Primeiro vamos construir um algoritmo de divisao e conquista natural para o
problema do corte de barras. Podemos definir `n recursivamente definindo onde aplicar
o primeiro corte na barra. Assim, se o melhor lugar para realizar o primeiro corte na
barra e no ponto i (onde 1 ≤ i ≤ n), entao o lucro total e dado por `n = pi + `n−i, que
e o preco do pedaco de tamanho i somado ao maior lucro possıvel obtido com a venda
do restante da barra, que tem tamanho n− i. Portanto, temos
`n = max1≤i≤n
pi + `n−i. (13.1)
A igualdade (13.1) sugere o seguinte algoritmo para resolver o problema, onde p e
um vetor contendo os precos dos pedacos de uma barra de tamanho n.
126
Algoritmo 35: Corte barras-DV(n,p)
1 se n = 0 entao
2 retorna 0
3 lucro = 0
4 para i = 1 ate n faca
5 valor = pi + Corte barras-DV(n− i,p)6 se lucro < valor entao
7 lucro = valor
8 retorna lucro
Apesar de ser um algoritmo intuitivo e calcular corretamente o lucro maximo
possıvel, ele e extremamente ineficiente, pois muito trabalho e repetido pelo algoritmo.
De fato, seja T (n) o tempo de execucao de Corte barras-DV(n,p). Vamos utilizar
o metodo da substituicao para provar que T (n) ≥ 2n. Claramente temos T (0) = 1 = 20.
Suponha que T (m) ≥ 2m para todo 0 ≤ m ≤ n − 1. Portanto, notando que T (n) =
1 + T (0) + T (1) + . . .+ T (n− 1), obtemos
T (n) = 1 + T (0) + T (1) + . . .+ T (n− 1)
≥ 1 + (20 + 21 + . . .+ 2n−1)
= 2n.
Assim, o problema possui a propriedade de sobreposicao de subproblemas. Cla-
ramente, o problema tambem possui a propriedade de subestrutura otima, dado que
inclusive ja modelamos o valor de uma solucao otima baseado em solucoes otimas
de subproblemas (veja (13.1)). Portanto, o problema tem os ingredientes necessarios
para que um algoritmo de programacao dinamica o resolva de forma eficiente. Abaixo
apresentamos um algoritmo com abordagem top-down para o problema do corte de
barras. Esse algoritmo mantem a estrutura de Corte barras-DV(n,p), salvando
os valores de solucoes otimas de subproblemas em um vetor r[0..n], de modo que r[i]
contem o valor de uma solucao otima para o problema de corte de uma barra de
tamanho i. Ademais, vamos manter um vetor s[0..n] tal que s[j] contem o primeiro
127
lugar que deve-se efetuar o corte em uma barra de tamanho j.
Algoritmo 36: Corte barras-TD(n, p)
1 Cria vetores r[0..n] e s[0..n]
2 r[0] = 0
3 para i = 1 ate n faca
4 r[i] = −1
5 retorna Corte barras-aux(n, p, r, s)
Algoritmo 37: Corte barras-aux(n,p,r,s)
1 se r[n] ≥ 0 entao
2 retorna r[n]
3 lucro = −1
4 para i = 1 ate n faca
5 (valor, s) = Corte barras-aux(n− i,p,r,s)6 se lucro < pi + valor entao
7 lucro = pi + valor
8 s[n] = i
9 r[n] = lucro
10 retorna (lucro, s)
O algoritmo Corte barras-TD(n) inicialmente cria os vetores r e s, faz r[0] = 0 e
inicializa todas as outras entradas de r com −1, representando que ainda nao calculamos
esses valores. Feito isso, Corte barras-aux(n,p,r,s) e executado.
Inicialmente, nas linhas 1 e 2, o algoritmo Corte barras-aux(n,p,r,s) verifica
se o subproblema em questao ja foi resolvido. Caso o subproblema nao tenha sido
resolvido, entao o algoritmo vai fazer isso de modo muito semelhante ao algoritmo 35.
A diferenca e que agora salvamos o melhor local para fazer o primeiro corte em uma
barra de tamanho n em s[n].
Vamos analisar agora o tempo de execucao de Corte barras-TD(n,p,r,s), que
obviamente tem, assintoticamente, o mesmo tempo de execucao de Corte barras-
128
aux(n,p,r,s). Note que cada chamada recursiva de Corte barras-aux a um
subproblema que ja foi resolvido retorna imediatamente, e todas as linhas sao execu-
tadas em tempo constante. Como salvamos o resultado sempre que resolvemos um
subproblema, cada subproblema e resolvido somente uma vez. Na chamada recursiva
em que resolvemos um subproblema de tamanho m (para 1 ≤ m ≤ n), o laco para
na linha 4 e executado m vezes. Assim, como existem subproblemas de tamanho
0, 1, . . . , n, o tempo de execucao T (n) de Corte barras-aux e assintoticamente dado
por
T (n) = 1 + 2 + . . .+ n = Θ(n2).
Caso precise imprimir os pontos em que os cortes foram efetuados, basta executar
o seguinte procedimento.
Algoritmo 38: Imprime cortes(n,p)
1 (lucroTotal, s) = Corte barras-TD(n, p)
2 enquanto n > 0 faca
3 Imprime s[n]
4 n = n− s[n]
Vamos ver agora como e um algoritmo com abordagem bottom-up para o problema
do corte de barras. A ideia e simplesmente resolver os problemas em ordem de tamanho
de barras, pois assim quando formos resolver o problema para uma barra de tamanho
j, temos a certeza que todos os subproblemas menores ja foram resolvidos. Abaixo
temos o algoritmo que torna esse raciocınio preciso.
129
Algoritmo 39: Corte barras-BU(n,p)
1 Cria vetores r[0..n] e s[0..n]
2 r[0] = 0
3 para i = 1 ate n faca
4 lucro = −1
5 para j = 1 ate i− 1 faca
6 se lucro < pj + r[i− j − 1] entao
7 lucro = pj + r[i− j − 1]
8 s[i] = j
9 r[i] = lucro
10 retorna (r[n], s)
13.4 Comparando algoritmos top-down e bottom-
up
Nesta curta secao comentamos sobre alguns aspectos positivos e negativos das abor-
dagens top-down e bottom-up. Algoritmos top-down possuem a estrutura muito
semelhante a de um algoritmo recursivo cuja construcao se baseia na estrutura re-
cursiva da solucao otima. Ja na abordagem bottom-up, essa estrutura nao existe, de
modo que o codigo pode ficar complicado no caso onde muitas condicoes precisam
ser analisadas. Por outro lado, algoritmo bottom-up sao geralmente mais rapidos,
por conta de sua implementacao direta, sem que diversas chamadas recursivas sejam
realizadas, como no caso de algoritmos top-down.
Por fim, mencionamos que embora na maioria dos casos, as duas abordagens levam
a tempos de execucao assintoticamente iguais, e possıvel que a abordagem top-down
seja assintoticamente mais eficiente no caso onde varios subproblemas nao precisam
ser resolvidos. Nesse caso, um algoritmo bottom-up resolveria todos os subproblemas,
mesmo os desnecessarios, diferentemente do algoritmo top-down, que resolve somente
os subproblemas necessarios.
130
Parte
V
Algoritmos em grafos
Capıtulo
14
Grafos
Um grafo G e uma estrutura formada por um par (V,E), onde V e um conjunto finito
e E e um conjunto de pares de elementos de V . O conjunto V e chamado de conjunto
de vertices e E e o conjunto de arestas de G. Um digrafo D = (V,A) e definido como
um conjunto de vertices V e um conjunto de arcos A, que e um conjunto de pares
ordenados de V , i.e., um grafo cujas arestas tem uma direcao associada. Um grafo com
conjunto de vertices V = v1, . . . , vn e dito simples quando nao existem arestas do tipo
vi, vi e para cada par de ındices 1 ≤ i < j ≤ n existe no maximo uma aresta vi, vj.De modo similar, um digrafo com conjunto de vertices V = v1, . . . , vn e dito simples
quando nao existem arestas do tipo (vi, vi) e para cada par de ındices 1 ≤ i < j ≤ n
existe no maximo uma aresta (vi, vj) e no maximo uma aresta (vj, vi). Todos os grafos
e digrafos considerados aqui, a menos que dito explicitamente o contrario, sao simples.
Note que o maximo de arestas que um grafo (resp. digrafo) com n vertices pode ter e
n(n− 1)/2 (resp. n(n− 1)). Dado um grafo G, denotamos o conjunto de vertices de G
e o conjunto de arestas de G, respectivamente, por V (G) e E(G). Por simplicidade,
vamos muitas vezes denotar arestas u, v de um grafo por uv. No caso de digrafos,
vamos utilizar uv para aresta orientada (u, v).
Um grafo (ou subgrafo) G e maximal com respeito a uma propriedade P (por
exemplo, uma propriedade de um grafo G pode ser G nao conter um triangulo ou G
ter pelo menos k arestas) se G possui a propriedade P mas nenhum grafo que contem
G possui a propriedade P .
Um grafo G e conexo se para todo par de vertices u, v de G existe um caminho
Figura 14.1: Representacao grafica de um grafo G e um digrafo D.
entre u e v. Um grafo que nao e conexo e dito desconexo. Os subgrafos conexos de um
grafo G que sao maximais com respeito a conexidade sao chamados de componentes.
A Teoria de Grafos, que estuda essas estruturas, tem aplicacoes em diversas areas
do conhecimento, como Bioinformatica, Sociologia, Fısica, Computacao e muitas outras,
e teve inıcio em 1736 com Leonhard Euler, que estudou um problema conhecido como
o problema das sete pontes de Konigsberg.
14.1 Formas de representar um grafo
Certamente podemos representar grafos simplesmente utilizando conjuntos para vertices
e arestas. Porem, e desejavel utilizar alguma estrutura de dados que nos permita
ganhar em eficiencia dependendo da tarefa que necessitamos.
As duas formas mais comuns de se representar um grafo utilizam listas de adjacencias
ou matrizes de adjacencias. Por simplicidade vamos assumir que um grafo com n vertices
tem conjunto de vertices 1, 2, . . . , n. Na representacao por listas de adjacencias, um
grafo G = (V,E) consiste em um vetor LG com |V | listas de adjacencias, uma para
cada vertice, onde LG(u) contem uma lista encadeada com todos os vizinhos de u em
G. Em LG(u) temos a cabeca da lista que contem N(u).
134
Figura 14.2: Representacao grafica de um grafo G e um digrafo D e suas listas deadjacencias.
Na representacao por matriz de adjacencias, um grafo G = (V,E) e uma matriz
simetrica A = (aij) de tamanho |V | × |V | onde aij = 1 se ij ∈ E, e aij = 0 caso
contrario. No caso de grafos direcionados, temos aij = 1 se (i, j) ∈ E, e aij = 0 caso
contrario.
Em geral, o uso das listas de adjacencias sao preferidas para representar grafos
esparsos, que sao grafos com n vertices e o(n2) arestas, pois nao e necessario alocar n2
espacos de memoria somente para representar o grafo. Ja a representacao por matriz
de adjacencias e muito usada para representar grafos densos, que sao grafos com Θ(n2)
arestas. Porem, ressaltamos que esse nao e o unico fator importante na escolha da
estrutura de dados utilizada para representar um grafo, pois determinados algoritmos
precisam de propriedades da representacao por listas e outros da representacao por
matriz para serem eficientes.
14.2 Conceitos essenciais
No que segue, considere um grafo G = (V,E). Dizemos que u e v sao vizinhos (ou
adjacentes se u, v ∈ E. A vizinhanca de um vertice u, denotada por NG(u) (ou
135
Figura 14.3: Representacao grafica de um grafo G e um digrafo D e suas matrizes deadjacencias.
simplesmente N(u)) e o conjunto dos vizinhos de u. Dizemos ainda que u e v sao
extremos da aresta u, v, que u e adjacente a v (e vice versa). Ademais, dizemos que a
aresta u, v incide em u e em v. Arestas que dividem o mesmo extremo sao chamadas
de adjacentes.
O grau de um vertice v, denotado por dG(v) (ou simplesmente d(v)) e a quantidade
de vertices na vizinhanca de v, i.e., |N(v)|. O grau mınimo de um grafo G, denotado
por δ(G), e o menor grau de um vertice de G dentre todos os vertices de G, i.e.,
δ(G) = mindG(v) : v ∈ V .
O grau maximo de um grafo G, denotado por ∆(G), e o maior grau de um vertice de
G dentre todos os vertices de G, i.e.,
∆(G) = maxdG(v) : v ∈ V .
O grau medio de G, denotado por d(G), e a media dos graus de todos os vertices de G,
136
i.e.,
d(G) =
∑v∈V (G) d(v)
|V (G)|.
14.3 Trilhas, passeios, caminhos e ciclos
Dado um grafo G = (V,E), um passeio em G e uma sequencia nao vazia de vertices
P = (v0, v1, . . . , vk) tal que vivi+1 ∈ E para todo 0 ≤ i < k. Dizemos que P e um passeio
de v0 a vk e que P passa pelos vertices vi (1 ≤ i ≤ k) e pelas arestas vivi+1 (1 ≤ i < k).
Os vertices v0 e vk sao, respectivamente, o comeco e o fim de P , e os vertices v1, . . . , vk−1
sao os vertices internos do passeio P . Denotamos por V (P ) o conjunto de vertices que
fazem parte de P , i.e., V (P ) = v0, v1, . . . , vk, e denotamos por E(P ) o conjunto de
arestas que fazem parte de P , i.e., E(P ) =v0v1, v1v2, . . . , vk−1vk
. O comprimento
de P e a quantidade de arestas de P . Denotamos um caminho de comprimento n por
Pn. Note que na definicao de passeio podem existir arestas repetidas.
Passeios em que nao ha repeticao de arestas sao chamados de trilhas. Caso um
passeio nao tenha nem vertices repetidos, dizemos que esse passeio e um caminho. Um
passeio e dito fechado se seu comeco e fim sao o mesmo vertice. Uma trilha fechada
em que o inıcio e os vertices internos sao dois a dois distintos e chamada de ciclo.
Denotamos um ciclo de comprimento n por Cn.
Um subgrafo H = (VH , EH) de um grafo G = (VG, EG) e um grafo com VH ⊂ VG
e EH e um conjunto de pares em VH tal que EH ⊂ EG. O subgrafo H e gerador se
VH = VG, e dado um conjunto de vertices W ⊂ VG, dizemos que um subgrafo H de G
e induzido por W se VH = W e uv ∈ VH se e somente se uv ∈ EG. Dado F ⊂ EG, um
subgrafo H de G e induzido por F se EH = F e v e um vertice de H se e somente se
existe alguma aresta de F que incide em v.
Um grafo G = (VG, EG) e conexo se existe um caminho entre quaisquer dois vertices
de VG. Uma arvore T com n vertices e um grafo conexo com n − 1 arestas ou,
alternativamente, e um grafo conexo sem ciclos.
137
Figura 14.4: Passeios, trilhas, ciclos e caminhos.
Figura 14.5: Exemplos de arvores.
138
Capıtulo
15
Buscas
Algoritmos de busca sao importantıssimos em grafos. Eles permitem inspecionar as
arestas do grafo de forma sistematica de modo que todos os vertices do grafo sao
visitados. Ademais, algoritmos de busca servem de “inspiracao” para varios algoritmos
importantes. Dentre eles, mencionamos o algoritmo de Prim para encontrar arvores
geradoras mınimas em grafos e o algoritmo de Dijkstra para encontrar caminhos mais
curtos.
15.1 Busca em largura
Dado um grafo G = (V,E) e um vertice s ∈ V , o algoritmo de busca em largura
visita todos os vertices v que sao alcancaveis por algum caminho partindo de s. Por
simplicidade, ao longo desta secao assumimos que o grafo G em que aplicamos a busca
em largura e conexo.
Apesar de estarmos considerando um grafo G = (V,E), o algoritmo para digrafos
e essencialmente o mesmo. O nome do algoritmo vem do fato de, nesse processo,
primeiramente serem explorados os vertices a distancia 1 de s, seguido pelos vertices a
distancia 2 de s e assim por diante. Para possibilitar a exploracao dos vertices de G
dessa maneira, vamos utilizar uma fila como estrutura de dados auxiliar.
Inicialmente, colocamos o vertice s na fila. Enquanto a fila nao ficar vazia remove-
mos um elemento u da fila (inicialmente, s e removido), adicionamos os vizinhos de u
a fila e repetimos o procedimento. Note que apos s, os proximos vertices removidos
da fila sao os vizinhos de s, depois os vizinhos dos vizinhos de s e assim por diante.
Manteremos, para cada vertice v, um atributo v.pai que indicara o caminho percorrido
de s ate v, e um atributo v.visitado indicando se v ja foi explorado pelo algoritmo.
Para a busca em largura, veremos que sera conveniente utilizar a representacao de
grafos em listas de adjacencias. Abaixo temos o pseudocodigo para esse procedimento.
Algoritmo 40: Busca Largura(G = (V,E), s)
1 para todo vertice v ∈ V \ s faca
2 v.visitado = 0
3 v.pai = null
4 s.visitado = 1
5 cria fila vazia F
6 Fila-adiciona(F, s)
7 enquanto Fila F nao e vazia faca
8 u = Fila-remove(F )
9 para todo vertice v ∈ N(u) faca
10 se v.visitado = 0 entao
11 v.visitado = 1
12 v.pai = u
13 Fila-adiciona(F, v)
Vamos agora explicar o algoritmo de Busca Largura em detalhes: o algoritmo
primeiramente inicializa todas as distancias como infinito e todos os pais como null.
Feito isso, criamos a fila F , indicamos que s foi visitado e enfileiramos s. A partir
daı vamos repetir o seguinte procedimento: desenfileiramos um vertice, chamado de u;
para todo vizinho v de u que nao foi visitado ainda (i.e., com v.visitado = 0) vamos
marcar esse vertice como visitado, atualizar a distancia de s a v, atualizar v.pai para o
vertice imediatamente antes de v em um caminho mınimo de s a v e colocar v na fila.
Na Figura 15.1 simulamos uma execucao da busca em largura comecando no
vertice s.
Seja n = |VG| e m = |EG|. Vamos analisar o tempo de execucao do algoritmo
140
Figura 15.1: Execucao de Busca Largura(G = (V,E), s).
Busca Largura aplicado em um grafo G = (V,E). Na inicializacao (linhas 1–6) e
gasto tempo Θ(n) e todas as outras operacoes levam tempo constante. Note que antes
de um vertice v entrar na fila, atualizamos v.visitado de 0 para 1 (linha 11) e depois
que o laco enquanto e iniciado, nenhum vertice possui o atributo visitado mudado
de 1 para 0. Assim, uma vez que um vertice entra na fila, ele ele nunca mais passara
no teste da linha 10. Portanto, todo vertice entra somente uma vez na fila, e como a
linha 8 sempre remove alguem da fila, o laco enquanto e executado n vezes, sendo
uma execucao para cada vertice.
O ponto essencial da analise e a quantidade total de vezes que o laco para e
executado. Esse e o ponto do algoritmo onde e essencial o uso de lista de adjacencias
para um algoritmo eficiente. Se utilizarmos matriz de adjacencias, entao o laco para
e executado n vezes em cada iteracao do laco enquanto, o que leva a um tempo de
execucao total de Θ(n2). Porem, se utilizarmos lista de adjacencias, entao em cada
execucao do laco para, ele e executado |N(u)| vezes, de modo que no total, e executado∑u∈V |N(u)| = 2m vezes, de modo que o tempo total de execucao e Θ(n+m).
Observe tambem que e facil construir um caminho mınimo de s a qualquer vertice
v. Basta seguir o caminho a partir de v, voltando para v.pai, depois (v.pai).pai e
assim por diante ate chegarmos em s. De fato, a arvore T com conjunto de vertices
141
VT = v ∈ V : v.pai 6= null∪s e conjunto de arestas ET = v.pai, v : v ∈ VT \scontem um unico caminho entre s e qualquer v ∈ VT .
15.1.1 Distancia entre vertices
Lembre-se que, dado um grafo G, a distancia entre dois vertices u e v, denotada por
distG(u, v) e a quantidade de arestas do menor caminho entre u e v. Ao percorrer o
grafo, o algoritmo de busca em largura visita os vertices de acordo com sua distancia
ao vertice inicial s. Assim, durante esse processo, o algoritmo pode facilmente calcular
a distancia entre s e v, para todo vertice v. O algoritmo salva essa distancia em um
atributo v.dist. O algoritmo Busca Largura-dist abaixo contem duas linhas novas
com relacao ao algoritmo Busca Largura, as linhas 4, 6 e 14. Essas linhas salvam
as distancias de s aos outros vertices do grafo. Quando nao existe caminho entre s e v,
definimos a distancia entre s e v como distG(s, v) =∞.
Algoritmo 41: Busca Largura-dist(G = (V,E), s)
1 para todo vertice v ∈ V \ s faca
2 v.visitado = 0
3 v.pai = null
4 v.dist =∞
5 s.visitado = 1
6 s.dist = 0
7 cria fila vazia F
8 Fila-adiciona(F, s)
9 enquanto Fila F nao e vazia faca
10 u = Fila-remove(F )
11 para todo vertice v ∈ N(u) faca
12 se v.visitado = 0 entao
13 v.visitado = 1
14 v.dist = u.dist + 1
15 v.pai = u
16 Fila-adiciona(F, v)
142
Seja T a arvore com conjunto de vertices VT = v ∈ V : v.pai 6= null ∪ s e
conjunto de arestas ET = v.pai, v : v ∈ VT \ s. Em T existe um unico caminho
entre s e qualquer v ∈ VT e esse caminho e um caminho mınimo.
A seguir mostramos que ao fim do algoritmo Busca Largura-dist(G = (V,E), s),
o atributo v.dist contem a distancia entre s e v, para todo vertice v do grafo G.
Comecamos apresentando um resultado (veja Lema 15.2 abaixo) que garante que
as estimativas obtidas pelo algoritmo para as distancias nunca sao menores que as
distancias. No lema usaremos o seguinte fato que pode ser mostrada de forma simples.
Fato 15.1
Seja G = (VG, EG) um grafo. Para todo s ∈ VG e toda aresta uv ∈ EG temos
distG(s, u) ≤ distG(s, v) + 1.
Lema 15.2
Sejam G = (VG, EG) um grafo e s ∈ VG. Apos Busca Largura-dist(G, s)
calcular v.dist, temos o seguinte para todo v ∈ VG:
v.dist ≥ distG(s, v).
Demonstracao. Comece notando que cada vertice e adicionado a fila somente uma
vez. A prova segue por inducao na quantidade de vertices adicionados a fila, i.e., na
quantidade de vezes que a rotina Fila-adiciona e executada. O primeiro vertice
adicionado a fila e o vertices s, antes do laco enquanto. Nesse ponto, temos s.dist =
0 ≥ distG(s, s) e v.dist =∞ para todo v ∈ V \ s, de modo que o resultado e valido.
Suponha agora que o enunciado do lema vale para os primeiros k − 1 vertices
adicionados a fila. Considere o momento em que o algoritmo acaba de realizar a k-
esima insercao na fila, onde v e o vertice que foi adicionado. O vertice v foi considerado
no laco para por estar na vizinhanca de um vertice u, que foi removido da fila. Por
hipotese de inducao, como u foi um dos k − 1 primeiros vertices a ser inserido na fila,
143
temos que u.dist ≥ distG(s, u). Mas note que, pela linha 14, utilizando o Fato 15.1
temos
v.dist = u.dist + 1 ≥ distG(s, u) + 1 ≥ d(s, v).
Como cada vertice entra na fila somente uma vez, o valor em v.dist nao muda mais
durante a execucao do algoritmo.
O proximo resultado, Lema 15.3, garante que se um vertice u entra na fila antes de
um vertice v, entao no momento em que v e adicionado a fila temos u.dist ≥ v.dist.
Como uma vez que a estimativa v.dist de um vertice v e calculada ela nunca muda,
concluımos que a relacao entre as estimativas para as distancias de s a u e v nao
mudam ate o final da execucao do algoritmo.
Lema 15.3
Sejam G = (VG, EG) um grafo e s ∈ VG. Considere uma execucao de Busca
Largura-dist(G, s). Para todos os pares de vertices u e v na fila tal que u
entrou na fila antes de v, vale que no momento em que v entra na fila temos
u.dist ≤ v.dist ≤ u.dist + 1.
Demonstracao. Vamos mostrar o resultado por inducao na quantidade de iteracoes do
laco enquanto. Antes da primeira iteracao nao ha o que provar, pois a fila contem
somente o vertice s. Suponha agora que logo apos a (k − 1)-esima iteracao do laco
enquanto temos u.dist ≤ v.dist ≤ u.dist + 1 para todos os pares de vertices u e v
na fila, onde u entrou na fila antes de v.
Considere agora a k-esima execucao do laco enquanto. Seja F = (u, v1, . . . , v`)
a fila no inıcio dessa execucao do laco enquanto. Na execucao do laco, o algoritmo
remove u de F , e adiciona os vizinhos nao visitados de u a fila F . O algoritmo entao
faz v.dist = u.dist + 1 para todo vizinho v nao visitado de u (executando o laco
para). Utilizando a hipotese de inducao, sabemos que para todo 1 ≤ i ≤ ` temos
u.dist ≤ vi.dist ≤ u.dist + 1.
Assim, ao adicionar a fila um vizinho v de u (lembre que u foi removido da fila) temos,
144
pela desigualdade acima, que, para todo 1 ≤ i ≤ `,
vi.dist ≤ u.dist + 1 = v.dist = u.dist + 1 ≤ vi.dist + 1.
Por hipotese de inducao (lembrando que o valor em v.dist nao muda depois de
modificado), sabemos que os pares em u, v1, . . . , v` satisfazem a conclusao do lema.
Ademais, pares dos vizinhos de u que entraram na fila tem a mesma estimativa de
distancia (u.dist+1). Portanto todos os pares de vertices da fila satisfazem a conclusao
do lema.
Com os Lemas 15.2 e 15.3, temos todas as ferramentas necessarias para mostrar
que Busca Largura-dist calcular corretamente as distancias de s a todos os vertices
do grafo.
Teorema 15.4
Sejam G = (VG, EG) um grafo conexo e s ∈ VG. Apos a execucao de Busca
Largura-dist(G, s), vale o seguinte para todo v ∈ VG:
v.dist = distG(s, v).
Demonstracao. Suponha por contradicao que ao fim da execucao de Busca Largura-
dist(G, s) exista um vertice v ∈ VG com v.dist 6= distG(s, v). Seja v o vertice com
menor v.dist tal que v.dist 6= distG(s, v). Pelo Lema 15.2, sabemos que
v.dist > distG(s, v). (15.1)
Seja u o vertice que precede v em um caminho mınimo de s a v. Entao, distG(s, v) =
distG(s, u) + 1. Assim, usando (15.1), temos que
v.dist > distG(s, v) = distG(s, u) + 1 = u.dist + 1. (15.2)
Vamos analisar o momento em que Busca Largura-dist(G, s) remove u da fila
F . Se nesse momento o vertice v esta na fila, entao note que v entrou na fila por
ser vizinho de um vertice w que ja tinha sido removido de F (antes de u). Logo,
temos v.dist = w.dist + 1. Pelo Lema 15.3, w.dist ≤ u.dist. Portanto, temos
145
v.dist ≤ u.dist+ 1, uma contradicao com (15.2). Podemos entao assumir que quando
u foi removido da fila F , o vertice v nao estava em F . Se v tinha entrado em F
anteriormente e foi removido de F , temos, pelo Lema 15.3, v.dist ≤ u.dist, uma
contradicao com (15.2). Assim, assuma que v nao tinha entrado em F quando u foi
removido de F . Nesse caso, quando v entrar na fila (certamente entra, pois e vizinho
de u), teremos v.dist = u.dist + 1, uma contradicao com (15.2).
15.2 Busca em profundidade
Na busca em profundidade os vertices sao explorados de forma diferente de como e feito
na busca em largura, que explora primeiramente os vizinhos de s para somente depois
explorar os vertices a distancia 2 de s e assim por diante. Na busca em profundidade,
exploramos os vertices seguindo um caminho a partir de s, enquanto for possıvel fazer
isso sem repetir vertices. Ao fim desse caminho, volta-se um passo e seguimos outro
caminho, e assim por diante.
Cada vertice que e descoberto (visitado pela primeira vez) pelo algoritmo e inserido
na pilha. A cada iteracao, o algoritmo consulta o topo u da pilha, segue por um vizinho
v de u ainda nao explorado e adiciona v na pilha. Caso todos os vizinhos de u ja
tenham sido explorados, u e removido da pilha.
O algoritmo vai manter uma variavel “encerrado” com a ordem em que cada vertice
teve sua toda vizinhanca visitada. Cada vertice u possui tres atributos: u.pai, u.fim
e u.visitado. O atributo u.pai indica que vertice antecede u no caminho explorado,
u.fim indica o momento em que o algoritmo termina a verificacao da lista de adjacencias
de u (e remove u da pilha). Por fim, u.visitado e um atributo que tem valor 1 se o
vertice u ja foi visitado pelo algoritmo e 0 caso contrario. Abaixo temos o pseudocodigo
para esse procedimento, lembrando que, dada uma pilha P , os procedimentos Empi-
lha(P, u), Desempilha(P ) e Consulta(P) fazem, respectivamente, insercao de um
elemento u, remocao do elemento no topo da pilha, e consulta ao ultimo valor inserido
em P .
146
Algoritmo 42: Busca Profundidade(G = (V,E), s)
1 para todo vertice v ∈ V \ s faca
2 v.visitado = 0
3 v.pai = null
4 s.visitado = 1
5 encerramento = 0
6 cria pilha vazia P
7 Empilha(P, s)
8 enquanto P 6= ∅ faca
9 u = Consulta(P)
10 se existe uv ∈ E e v.visitado = 0 entao
11 v.visitado = 1
12 v.pai = u
13 Empilha(P, v)
14 senao
15 encerramento = encerramento+ 1
16 u.fim = encerramento
17 u = Desempilha(P )
O grafo A = (VA, EA) com conjunto de vertices VA = v ∈ V (G) : v.pai 6=null ∪ s e conjunto de arestas EA = (v.pai, v) : v ∈ VA e v.pai 6= null e uma
arvore geradora de G e e chamado de Arvore de Busca em Profundidade.
Nas linhas 1-7 inicializamos alguns atributos, criamos a pilha e colocamos s na
pilha. Entao, nas linhas 10-13 o algoritmo visita um vizinho de u ainda nao visitado, o
colocando na pilha. Se u nao tem vizinho nao visitado, entao u e encerrado e retirado
da pilha (linhas 15-17).
Prosseguiremos agora com a analise do tempo de execucao do algoritmo, onde
assumimos que o grafo G esta representado por uma lista de adjacencias. Note que
imediatamente antes de um vertice x ser empilhado (linhas 7 e 13), modificamos
x.visitado de 0 para 1. Assim, tal vertice x so sera empilhado uma vez em toda a
147
execucao do algoritmo. Dessa forma, fica simples analisar o tempo de execucao do
algoritmo: a inicializacao feita nas linhas 1–7 leva tempo O(|V |), a condicao na linha
10 verifica os vizinhos de cada vertice, de modo que e executada O(|E|) vezes ao todo,
e todas as outras instrucoes sao executadas em tempo constante. Assim, o tempo total
de execucao da Busca em Profundidade e O(|V |+ |E|), como na Busca em Largura.
Na Figura 15.2 simulamos uma execucao da busca em profundidade comecando no
vertice s.
Figura 15.2: Execucao de Busca Profundidade(G = (V,E), s), indicando a pilha eo tempo de encerramento de cada vertice.
Uma observacao interessante e que, dada a estrutura em que os vertices sao visi-
tados (sempre visitando um vizinho de u, e assim por diante), e simples escrever um
algoritmo recursivo para a busca em profundidade. Abaixo descrevemos o pseudocodigo
148
para esse algoritmo, com uma pequena variacao com relacao ao algoritmo anterior,
que e forcar o algoritmo a ser executado ate que todos os vertices sejam visitados,
mesmo vertices de diferentes componentes (veja linhas 7-8 de Busca Profundidade
- Recursivo(G = (V,E))).
Algoritmo 43: Busca Profundidade - Recursivo(G = (V,E))
1 para todo vertice v ∈ V \ s faca
2 v.visitado = 0
3 v.pai = null
4 s.visitado = 1
5 encerramento = 0
6 Busca - visita(G = (V,E), s)
7 para todo u com u.visitado = 0 faca
8 Busca - visita(G = (V,E), u)
Algoritmo 44: Busca - visita(G = (V,E), u)
1 u.visitado = 1
2 para todo vizinho v de u faca
3 se v.visitado == 0 entao
4 v.pai = u
5 Busca - visita(G, v)
6 encerramento = encerramento+ 1
7 u.fim = encerramento
Note que o algoritmo de busca em profundidade funciona da mesma forma em um
grafo orientado. O grafo F = (VF , EF ) com conjunto de vertices VF = V (G) e conjunto
de arestas EF = (v.pai, v) : v ∈ VF e v.pai 6= null e uma floresta geradora de G e e
chamado de Floresta de Busca em Profundidade.
149
15.2.1 Ordenacao topologica
Consideraremos agora um grafo orientado, i.e., um grafo em que suas arestas sao pares
ordenados. Assim, um grafo orientado G = (V,E) e um grafo com conjunto de vertices
V e suas arestas sao pares ordenados (u, v) de E. O grafo que vamos considerar nao
tem ciclos que respeitam a orientacao, i.e., nao existe uma sequencia de pelo menos tres
vertices (v1, v2, . . . , vk) tal que (vi, vi+1) e uma aresta para todo 1 ≤ i ≤ k − 1, e (vkv1)
e uma aresta. Um grafo orientado sem ciclos e chamado de grafo orientado acıclico.
Uma ordenacao topologica de um grafo orientado G e uma ordenacao dos vertices
de G tal que, para toda aresta (u, v), o vertice u aparece antes de v na ordenacao.
Assim, podemos pensar em cada uma das arestas orientadas (u, v) como representando
uma relacao de dependencia, indicando que v depende de u. Por exemplo, os vertices
podem representar tarefas e uma arestas (u, v) indica que a tarefa u deve ser executada
antes da tarefa v.
Diversos problemas no “mundo real” necessitam do uso da ordenacao topologica para
serem resolvidos de forma eficiente. Isso se da pelo fato de muitos problemas precisarem
lidar com uma certa hierarquia de pre-requisitos ou dependencias. Por exemplo,
para montar qualquer placa eletronica composta de diversas partes, e necessario
saber exatamente em que ordem devemos colocar cada componente da placa. Isso
pode ser feito de forma simples modelando o problema em um grafo orientado que
representa tal dependencia e fazendo uso da ordenacao topologica. Outra aplicacao
que exemplifica bem a importancia da ordenacao topologica e o problema de escalonar
tarefas respeitando todas as dependencias entre as tarefas.
O seguinte algoritmo encontra uma ordenacao topologica de um grafo ordenado G.
Algoritmo 45: Ordenacao topologica(G = (V,E))
1 cria uma lista de elementos L inicialmente vazia
2 executa Busca Profundidade(G) e toda vez que um vertice v e encerrado ele
e inserido no comeco da lista L
3 retorna L
Nas Figuras 15.3 e 15.4 abaixo temos um exemplo de execucao do algoritmo
Ordenacao topologica.
150
Figura 15.3: Um grafo orientado acıclico com vertices representando topicos de estudode uma disciplina, e uma aresta (u, v) indica que o topico u deve ser compreendidoantes do estudo referente ao topico v. Para cada vertice u, indicamos o valor de u.fim.
Figura 15.4: Uma ordenacao topologica obtida com uma execucao de Ordenacaotopologica no grafo da Figura 15.3
151
15.2.2 Componentes fortemente conexas
Dado um grafo orientado G = (V,E), uma componente fortemente conexa de G
e um subgrafo G′ = (V ′, E ′) maximal de G com respeito a seguinte propriedade:
para todo par u, v ∈ V ′ existe um caminho de u para v e outro de v para u em G′.
Sejam G1, . . . , Gk o conjunto de todas as componentes fortemente conexas de G. Pela
maximalidade das componentes, cada vertice pertence somente a uma componente e,
mais ainda, entre quaisquer duas componentes Gi e Gj existem arestas apenas em uma
direcao, caso contrario, a uniao de Gi e Gj formaria uma componente maior que as
duas sozinhas, contradizendo a maximalidade da definicao.
Um simples algoritmo para encontrar componentes fortemente conexas faz uso da
busca em profundidade. Dado um grafo direcionado G, vamos executar duas buscas em
profundidade, sendo uma em G e uma no grafo G, que e o grafo obtido de G invertendo
o sentido de todas suas arestas. No algoritmo que segue, G e o grafo descrito acima.
Algoritmo 46: Componentes fortemente conexas(G = (V,E))
1 executa Busca Profundidade - Recursivo(G)
2 Seja v.encerramento como calculado na linha 1 para todo v ∈ V (G)
3 Visitando os vertices em ordem decrescente de v.encerramento como na linha 2,
executa Busca Profundidade - Recursivo(G)
Se o grafo estiver representado com lista de adjacencias, entao o algoritmo acima
funciona em tempo O(|V |+ |E|).
15.2.3 Outras aplicacoes dos algoritmos de busca
Tanto a busca em largura como a busca em profundidade podem ser aplicadas em
varios problemas. Alguns exemplos sao testar se um dado grafo e bipartido, detectar
circuitos em grafos, encontrar caminhos entre vertices, e listar todos os vertices de uma
componente conexa. Ademais, podem ser usados como ferramenta na implementacao
do metodo de Ford-Fulkerson, que calcula o fluxo maximo em uma rede de fluxos.
Uma outra aplicacao interessante do algoritmo de Busca em Profundidade e resolver de
forma eficiente (tempo O(|V |+ |E|)) o problema de encontrar um caminho ou circuito
152
Euleriano.
Algoritmos importantes em grafos tem estrutura semelhante ao algoritmo de busca
em largura, como e o caso do algoritmo de Prim para encontrar uma arvore geradora
mınima, e o algoritmo de Dijkstra, que encontra caminhos mınimos em grafos com
pesos nao-negativos nas arestas.
Alem de todas essas aplicacoes dos algoritmos de busca em problemas classicos
da Teoria de Grafos, esses algoritmos continuam sendo de extrema importancia no
desenvolvimentos de novos algoritmos. O algoritmo de Busca em Profundidade, por
exemplo, vem sendo muito utilizado em algoritmos que resolvem problemas em Teoria
de Ramsey, uma vertente da Teoria de Grafos e Combinatoria.
153
154
Capıtulo
16
Arvores geradoras mınimas
Uma arvore geradora de um grafo G e uma arvore que e um subgrafo gerador de G,
i.e., uma arvore que contem todos os vertices de G. Dado um grafo G = (VG, EG) e
uma funcao w : EG → R de pesos nas arestas de G, diversas aplicacoes necessitam
encontrar uma arvore geradora T = (VT , ET ) de G que tenha peso total w(T ) mınimo
dentre todas as arvores geradoras de G, i.e., uma arvore T tal que
w(T ) =∑e∈ET
w(e) = minw(T ) : T e uma arvore geradora de G.
Uma arvore T com essas propriedades e uma arvore geradora mınima de G.
Figura 16.1: Exemplo de um grafo G e uma arvore geradora mınima (representadapelas arestas ressaltadas).
Apresentaremos alguns conceitos e propriedades relacionadas a arvores geradoras
mınimas e depois discutiremos algoritmos gulosos que encontram uma arvore geradora
mınima de G.
Dado um grafo G = (VG, EG) e um conjunto de vertices S ⊆ VG, um corte (S, VG\S)
de G e uma particao de VG. Uma aresta uv cruza o corte (S, VG\S) se u ∈ S e v ∈ VG\S.
Por fim, uma aresta que cruza um corte (S, VG \ S) e mınima se tem peso mınimo
dentre todas as arestas que cruzam (S, VG \ S).
Antes de discutirmos algoritmos para encontrar arvores geradoras mınimas vamos
entender algumas caracterısticas de arestas que cruzam cortes para obter uma estrategia
gulosa para o problema.
Lema 16.1
Sejam G = (VG, EG) um grafo e w : E → R uma funcao de pesos. Se e e uma
aresta de um ciclo C e cruza um corte (S, VG \ S), entao existe outra aresta de C
que cruza o corte (S, VG \ S).
Demonstracao. Seja e = u, v uma aresta de G como no enunciado, onde u ∈ S e
v ∈ (VG \ S). Como e esta em um ciclo C, existem dois caminhos distintos em C
entre os vertices u e v. Um desses caminho e a propria aresta e, e o outro caminho
necessariamente contem uma aresta f que cruza o corte (S, VG \ S), uma vez que u e v
estao em lados distintos do corte.
Uma implicacao clara do Lema 16.1 e que se e e a unica aresta que cruza um dado
corte, entao e nao pertence a nenhum ciclo.
Dado um corte (S, VG \S) de um grafo G, o seguinte teorema indica uma estrategia
para se obter uma arvore geradora mınima.
Teorema 16.2
Sejam G = (VG, EG) um grafo conexo e w : E → R uma funcao de pesos. Dado
um conjunto A de arestas de uma arvore geradora mınima e um corte (S, VG \ S).
Se e ∈ EG \ A e uma aresta que cruza o corte e tem peso mınimo dentre todas as
arestas que cruzam o corte, entao existe uma arvore geradora mınima que contem
A ∪ e.
156
Demonstracao. Sejam G = (VG, EG) um grafo conexo e w : E → R uma funcao de
pesos. Considere um conjunto A de arestas de uma arvore geradora mınima T e seja
(S, VG \ S) um corte de G.
Seja e = u, v ∈ EG \ A uma aresta que cruza o corte e tem peso mınimo dentre
todas as arestas que cruzam o corte. Suponha por contradicao que e nao esta em
nenhuma arvore geradora mınima. Note que como T e uma arvore geradora, adicionando
e a T geramos exatamente um ciclo. Assim, pelo Lema 16.1, sabemos que existe outra
aresta f de T que cruza o corte (S, VG \ S). Portanto, o grafo obtido da remocao
da aresta f de T e da adicao da aresta e a T e uma arvore (geradora). Seja T ′ essa
arvore. Claramente, temos w(T ′) = w(T )− w(f) + w(e) ≤ w(T ), onde usamos o fato
de w(e) ≤ w(f), que vale pela escolha de e. Como T e uma arvore geradora de peso
mınimo e temos w(T ′) ≤ w(T ), entao concluımos que T ′ e uma arvore geradora mınima,
uma contradicao.
Nas secoes a seguir veremos os algoritmos de Prim e Kruskal que utilizam a ideia
do Teorema 16.2 para obter arvores geradoras mınimas de grafos conexos.
16.1 Algoritmo de Prim
Dado um grafo conexo G = (VG, EG) e uma funcao de pesos nas arestas de G, o
algoritmo de Prim comeca obtendo uma arvore que consiste de somente uma aresta e, a
cada iteracao, acrescenta uma aresta a arvore obtida, aumentando assim a quantidade
de arestas da arvore. O algoritmo termina quando temos uma arvore geradora de G.
Para garantir que uma arvore geradora mınima e encontrada, o algoritmo comeca
com uma arvore vazia T = (VT , ET ), e a cada passo adiciona uma aresta mınima que
cruza o corte (VT , VG \ VT ). Pelo Teorema 16.2, ao se obter uma arvore geradora, tal
arvore e mınima.
O algoritmo de Prim mantem uma fila de prioridades de mınimo F que contem os
vertices que nao estao na arvore T = (VT , ET ) que estamos construindo (inicialmente,
F = VG). A fila de prioridades F e baseada na estimativa, para cada vertice v, do
peso da aresta de menor peso que conecta v a arvore T . Essa informacao fica salva no
atributo v.estimativa. Mantendo esses atributos atualizados, e simples encontrar uma
aresta mınima que cruza (VT , VG \ VT ), aumentando o tamanho da arvore geradora. O
157
atributo v.pai indica o vizinho de v na arvore T . Assim, utilizando os atributos v.pai,
ao fim do algoritmo de Prim, a arvore geradora mınima T tera conjunto de arestas
ET =v, v.pai : v ∈ VG \ s
,
onde s e o primeiro vertice analisado pelo algoritmo, passado como entrada. O algo-
ritmo de Prim vai manter tambem um atributo v.arvore para cada vertice, indicando
se o vertice pertence ou nao a arvore T , de modo que v.arvore = 1 se v esta em T e
v.arvore = 0 caso contrario.
Algoritmo 47: Prim(G = (VG, EG), w, s)
1 para todo vertice v ∈ V faca
2 v.estimativa =∞3 v.pai = null
4 v.arvore = 0
5 s.estimativa = 0
6 cria fila de prioridades (min) F com conjunto VG baseada em v.estimativa
7 enquanto F 6= ∅ faca
8 u = Remocao-min(F )
9 u.arvore = 1
10 para todo vertice v ∈ N(u) faca
11 se v.arvore = 0 (v esta em F ) e w(u, v) < v.estimativa entao
12 v.pai = u
13 v.estimativa = w(u, v)
14 Diminui-chave(F, v.indice, w(u, v))
A Figura 16.2 mostra um exemplo de execucao do algoritmo de Prim.
O algoritmo de Prim toma, a cada passo, a decisao mais apropriada no momento
(a escolha da aresta a ser incluıda na arvore) e nunca muda essa decisao. Algoritmos
dessa forma sao conhecidos como algoritmos gulosos.
Perceba a semelhanca na estrutura do algoritmo de Prim e no algoritmo de busca
em largura. O tempo de execucao depende de como o grafo G e a fila de prioridades F
158
Figura 16.2: Execucao do algoritmo de Prim. Um vertice fica preenchido no momentoem que e removido da fila de prioridades.
sao implementados. Vamos assumir que G e representado por uma lista de adjacencias,
que e a forma mais eficiente para o algoritmo de Prim, e que F e uma fila de prioridades
implementada atraves do uso de um heap binario como no Capıtulo 6.
No que segue, temos n = |VG| e m = |EG|. Na inicializacao, o algoritmo leva tempo
Θ(n) para executar as linhas 1–5, tempo Θ(n) para construir a fila de prioridades F na
linha 6, pois um heap com n elementos pode ser construıdo em tempo Θ(n) (basta criar
o vetor F com os elementos de V e executarConstrua-heap(F ). O laco enquanto
na linha 7 e executado n vezes, uma execucao para cada elemento de F . Como a
operacao Remocao-min(F ) executa em tempo O(log n), o tempo total gasto com as
operacoes na linha 8 e
O(n log n). (16.1)
A linha 9 e claramente executada em tempo constante. O laco para na linha 10 e
executado, para cada v, |N(v)| vezes, de modo que no total e executado Θ(m) vezes.
Para finalizar a analise precisamos saber o tempo gasto com a execucao das linhas 11,
12 e 13. As linhas 11, 12 e 13 sao claramente executadas em tempo constante, de
modo que levam tempo Θ(m) ao todo. A linha 14 executa o procedimento Diminui-
chave(F, v.indice, w(u, v)) que leva tempo O(log n). Assim, o tempo total gasto com
159
execucoes da linha 14 e
O(m log n). (16.2)
Portanto, por (16.1) e (16.2), temos que o tempo total de execucao do algoritmo de
Prim e
O(n log n) +O(m log n) = O((m+ n) log n
).
Como o grafo G e conexo, sabemos que G possui m ≥ n− 1 arestas. Logo, concluımos
que o tempo de execucao do algoritmo de Prim e
O((m+ n) log n
)= O(m log n).
16.2 Algoritmo de Kruskal
Dado um grafo conexo G = (VG, EG) e uma funcao de pesos nas arestas de G, o
algoritmo de Kruskal, assim como o algoritmo de Prim, comeca com um conjunto
vazio A de arestas e a cada passo adiciona uma aresta e a A garantindo que A ∪ ee um subconjunto de uma arvore geradora mınima. Porem, diferente do que ocorre
no algoritmo de Prim, o conjunto A nao e uma arvore em todo momento da execucao
do algoritmo. O algoritmo de Kruskal vai adicionando a A sempre a aresta de menor
peso que nao forma ciclos com as arestas que ja estao em A. Dessa forma, cada aresta
adicionada pertence a uma arvore geradora mınima junto com as arestas de A. O
algoritmo termina quando A tem n− 1 arestas, de modo que e o conjunto de arestas
de uma arvore geradora mınima de G.
Para o algoritmo a seguir lembre que dado um, grafo G = (V,E) e um subconjunto
A ⊆ E, o grafo G[A] e o subgrafo de G com conjunto das arestas A e os vertices de V
sao todos os extremos de arestas de A.
160
Algoritmo 48: Kruskal(G = (VG, EG), w, s)
1 Crie um vetor C[1..|EG|] e copie as arestas para C
2 Ordene C de modo nao-decrescente de pesos das arestas
3 Crie conjunto A = ∅4 para i = 1 ate |EG| faca
5 se G[A ∪ C[i]] nao contem ciclos entao
6 A = A ∪ C[i]
7 retorna (A)
Nas linhas 1 e 2 o conjunto das arestas e copiado para um vetor C[1..|EG|] e
ordenado. Assim, para considerar arestas de menor peso, basta percorrer o vetor C em
ordem. Na linha 3 criamos o conjunto A que recebera iterativamente as arestas que
compoem uma arvore geradora mınima. Nas linhas 4, 5 e 6 sao adicionadas, passo a
passo, aresta de peso mınimo que nao formam ciclos com as arestas que ja estao em A.
Seja G = (V,E) um grafo com n vertices e m arestas. Se o grafo esta representado
por listas de adjacencias, entao e simples executar a linha 1 em tempo Θ(n + m).
Utilizando algoritmos de ordenacao como Merge sort ou Heapsort, podemos
executar a linha 2 em tempo O(m logm). A linha 3 leva tempo O(1) e o laco para
(linha 4) e executado m vezes. O tempo gasto na linha 5 depende de como identificamos
os ciclos. Utilizando algoritmos de busca para verificar a existencia de ciclos em
A∪C[i] levamos tempo O(n+ |A|). Mas note que A possui no maximo n− 1 arestas,
de modo que a linha 5 e executada em tempo O(n). Portanto, como o laco e executado
m vezes, no total o tempo gasto nas linhas 4–6 e O(mn). Se T (n,m) e o tempo de
execucao de Kruskal(G = (VG, EG), w, s), entao vale o seguinte.
T (n,m) = O(n+m) +O(m logm) +O(mn)
= O(m) +O(m log n) +O(mn) (16.3)
= O(mn).
Para entender as igualdades acima, note que como G e conexo, temos m ≥ n− 1,
161
de modo que vale que n = O(m). Tambem note que como m = O(n2) (em qualquer
grafo simples) temos que m logm ≤ m log(n2) = 2m log n = O(m log n).
Mas e possıvel melhorar o tempo de execucao em (16.3) atraves do uso de uma
estrutura de dados apropriada. Vamos agora enxergar o algoritmo de Kruskal sob outra
perspectiva: ao adicionar uma aresta que nao forma ciclos com as arestas que estavam
em A, o que o algoritmo faz e adicionar uma aresta entre duas componentes conexas do
grafo que contem somente as arestas de A. Assim, se fizermos o algoritmo de Kruskal
manter uma particao de A em componentes conexas, e a cada passo adicionar a A
sempre a aresta de menor peso que conecta duas dessas componentes, nao precisamos
verificar a existencia de ciclos, que e o fator determinante para o tempo obtido em (16.3).
Para manter essas componentes conexas de modo eficiente, vamos utilizar a estrutura
de dados union-find (veja Capıtulo 7). Abaixo temos uma versao do algoritmo de
Kruskal utilizando a estrutura union-find.
Algoritmo 49: Kruskal-UF(G = (VG, EG), w, s)
1 Crie um vetor C[1..|EG|] e copie as arestas para C
2 Ordene C de modo nao-decrescente de pesos das arestas
3 Crie conjunto A = ∅4 para todo v ∈ VG faca
5 Cria conjunto(v)
6 para i = 1 ate |EG| faca
7 se Find(u) 6= Find(v), onde C[i] = u, v entao
8 A = A ∪ u, v9 Union(u, v)
10 retorna (A)
A ideia e muito semelhante a do algoritmo Kruskal. Nas tres primeiras linhas as
arestas sao ordenadas e o conjunto A e criado. Nas linhas 4 e 5 criamos um conjunto
para cada um dos vertices. Esses conjuntos sao nossas componentes conexas iniciais.
Nas linhas 6–9 sao adicionadas, passo a passo, aresta de peso mınimo que conecta
162
duas componentes conexas (considerando apenas as arestas de A). Note que o teste da
linha 7 falha para uma aresta cujos extremos estao no mesmo conjunto. Ao adicionar
uma aresta u, v ao conjunto A (linha 8), vamos juntar as componentes que contem u
e v (linha 9).
Seja G = (V,E) um grafo com n vertices e m arestas. Como na analise do algoritmo
Kruskal, executamos a linha 1 em tempo Θ(n+m) e a linha 2 em tempo O(m logm).
A linha 3 leva tempo O(1) e levamos tempo O(n) nas linhas 4 e 5. O laco para (linha
6) e executado m vezes. Como a linha 7 tem somente operacoes find, e executada
em tempo O(1) e a linha 8 tambem e executada em tempo O(1). Precisamos analisar
com cuidado o tempo de execucao gasto na linha 9. Para isso, vamos estimar quantas
vezes essa linha pode ser executada no total, ao fim de todas as execucoes do laco
para. Lembrando de como a operacao Union e realizada (veja Capıtulo 7), sabemos
que ao utilizar Union(x, y) com x ∈ X, y ∈ Y e |X| ≤ |Y |, gastamos tempo O(|X|)atualizando os representantes de todos os elementos de X. A pergunta importante a ser
respondida agora e: quantas vezes um vertice pode ter seu representante atualizado?
Como na operacao Union somente os elementos do conjunto de menor tamanho sao
atualizados, entao toda vez que isso acontece com um elemento x, o seu conjunto dobra
de tamanho. Assim, como o grafo tem n vertices, cada vertice x tem seu representante
atualizado no maximo log n vezes. Logo, de novo pelo fato do grafo ter n vertices, o
tempo total gasto nas linhas 6–9 e de O(n log n). Se T (n,m) e o tempo de execucao
de Kruskal-UF(G = (VG, EG), w, s), entao vale o seguinte.
T (n,m) = O(n+m) +O(m logm) +O(n log n)
= O(m) +O(m log n) +O(m log n)
= O(m log n).
163
164
Capıtulo
17
Trilhas Eulerianas
Uma trilha em um grafo G e uma sequencia de vertices v1, . . . , vk tal que vivi+1 ∈ E(G)
para todo 1 ≤ i ≤ k − 1 e todas essas arestas sao distintas (pode haver repeticao
de vertices). Uma trilha e dita fechada se tem comprimento nao nulo e tem inıcio e
termino no mesmo vertice. Se a trilha inicia em um vertice e termina em outro vertice,
entao dizemos que a trilha e aberta. Um classico problema em Teoria dos Grafos e o
de, dado um grafo conexo G, encontrar uma trilha que passa por todas as arestas de
G. Uma trilha com essa propriedade e chamada de trilha Euleriana, em homenagem a
Euler, que observou que propriedades um grafo deve ter para que contenha uma trilha
Euleriana. O seguinte classico teorema fornece uma condicao necessaria e suficiente
para que existe uma trilha Euleriana fechada em um grafo conexo.
Teorema 17.1
Um grafo conexo G contem uma trilha Euleriana fechada se e somente se todos
os vertices de G tem grau par.
O seguinte resultado trata de trilhas Eulerianas abertas.
Teorema 17.2
Um grafo conexo G contem uma trilha Euleriana aberta se e somente se G
contem exatamente dois vertices de grau ımpar.
A seguir veremos um algoritmo guloso que encontra uma trilha Euleriana fechada
em grafos conexos em que todos os vertices tem grau par. Uma ponte em um grafo e
uma aresta cuja remocao aumenta a quantidade de componentes do grafo. O algoritmo
de Fleury, descrito abaixo, comeca uma trilha em um vertice arbitrario do grafo e segue
por uma aresta evitando pontes sempre que possıvel. A cada aresta visita, essa aresta
e removida do grafo e a trilha continua por uma aresta que, se possıvel, nao seja ponte
do grafo atual.
Algoritmo 50: Fleury-Euleriano(G = (VG, EG))
1 para todo vertice v ∈ VG faca
2 se d(v) e ımpar entao
3 retorna “Nao existe trilha Euleriana em G”
4 v = vertice qualquer de VG
5 cria vetor T [1..|EG|]6 T [1] = v
7 i = 1
8 Seja G1 = G
9 enquanto dGi(T [i]) ≥ 1 faca
10 se existe aresta T [i], w para algum w ∈ VG que nao seja ponte em Gi entao
11 T [i+ 1] = w
12 senao
13 T [i+ 1] = z, onde T [i], z e ponte de Gi.
14 i = i+ 1
15 Gi+1 = Gi − T [i]T [i+ 1] /* Removendo a aresta utilizada */
16 retorna T
A Figura ?? contem um exemplo de execucao do algoritmo de Fleury.
Para encontrar uma trilha Euleriana aberta em um grafo G, caso tal trilha exista,
basta executar o algoritmo de Fleury comecando em um vertice de grau ımpar.
Um ponto chave no algoritmo e como descobrir se uma dada aresta e uma ponte.
Uma maneira simples de descobrir se uma aresta u, v e uma ponte em um grafo H
166
e remover u, v e executar uma busca em profundidade comecando de u em H. A
aresta u, v e uma ponte se e somente se v nao e alcancado na execucao da busca em
profundidade. Uma maneira mais eficiente e utilizar um algoritmo desenvolvido por
Tarjan.
Claramente, o primeiro laco para faz com que o algoritmo retorne “Nao existe
trilha Euleriana em G” caso isso seja verdade (veja Teorema teo:Euler). O seguinte
resultado vai ser util na prova de corretude do algoritmo de Fleury,
Teorema 17.3
Seja G um grafo onde dG(v) e par para todo v ∈ V (G). Entao G nao contem
pontes.
A seguir mostramos que o algoritmo de Fleury encontra uma trilha Euleriana
fechada no caso de grafos onde todos os vertices tem grau par.
Teorema 17.4
Seja G = (VG, EG) um grafo onde todos seus vertices tem grau par. Entao o
algoritmo Fleury-Euleriano(G) retorna uma trilha euleriana T de G.
Demonstracao. Seja Ti a sequencia de vertices T [1], T [2], . . . , T [i] construıda pelo
algoritmo.
Inicialmente, observamos que no inıcio da execucao da i-esima iteracao do laco
enquanto, Ti e uma trilha. De fato, essa afirmacao e trivialmente valida para i = 1.
Ademais, considere o inıcio da da i-esima iteracao do laco enquanto (inıcio da linha 8)
e suponha que Ti−1 e uma trilha. Como o algoritmo chegou ate este ponto de sua
execucao, sabemos que a (i−1)-esima iteracao do laco foi realizada com sucesso. Assim,
dGi−1(T [i− 1]) ≥ 1. Mas note que na (i− 1)-esima iteracao o algoritmo adiciona um
vizinho x de T [i− 1] a trilha atual (veja linhas 10 e 12), e a aresta xT [i] nao esta
contida em Ti−1, pois sempre que uma aresta e adicionada a trilha atual ela e removida
de EG (veja linha 13). Portanto, concluımos que
no inıcio da execucao da i-esima iteracao do laco enquanto, Ti e uma trilha.
167
A seguir vamos utilizar o seguinte fato que pode ser provado facilmente: uma
trilha T de um grafo G cujo vertice final tem grau par em T e uma trilha fechada.
O algoritmo termina sua execucao quando analisa um vertice T [i] sem vizinhos no
grafo Gi. Como ao fim da execucao do algoritmo temos dGi(T [i]) = 0 e todos os vertices
do grafo inicial G tem grau par, sabemos que o vertice T [i] tem grau par na trilha Ti.
Logo, Ti e fechada.
Em resumo, ate o momento, sabemos que o algoritmo termina sua execucao
retornando uma trilha fechada T . Resta mostrar que T e Euleriana. Suponha por
contradicao que T nao e Euleriana. Assim, existem arestas no grafo final H =
(VG, EG \ E(T )). Seja V≥1 os vertices v de H com dH(v) ≥ 1. Seja V0 := VG \ V≥1.Assim, para todo vertice v ∈ V0 temos dH(v) = 0 (nao confunda dH(v) com dG(v)).
Como o grafo inicial G e conexo, em G existe pelo menos uma aresta entre V0 e
V≥1. Assim, seja xy a ultima aresta da trilha T tal que x ∈ V≥1 e y ∈ V0. Esse fato
juntamente com o fato do vertice final de T estar em V0 (isso segue da condicao do
laco enquanto), sabemos que a aresta xy de T foi “atravessada” por T de x para y,
i.e., x vem antes de y em T . Como xy e a ultima aresta entre V0 e V≥1 e a trilha T
termina em um vertice de V0, no momento em que v e adicionado em T , xy e uma
ponte. Mas note que todo vertice v de V≥1 tem grau par em H, pois todo vertice
tem grau par em G e foram removidas somente as arestas da trilha fechada T . Assim,
temos dH(v) ≥ 2 para todo v em V≥1. Logo, pelo Teorema 17.3, nao existem pontes
em H. Portanto, quando o algoritmo escolheu a aresta xy, essa aresta nao era ponte
do grafo, uma contradicao com a escolha do algoritmo.
168
Capıtulo
18
Caminhos mınimos
Dado um grafo ou digrafo G = (VG, EG) e um vertice s ∈ VG, o algoritmo de busca em
largura explora os vertices de G calculando a quantidade de arestas em um caminho
mınimo de s a qualquer outro vertice de G alcancavel a partir de s. Porem, diversas
aplicacoes sao modeladas atraves de grafos que possuem pesos nas arestas. Assim, e
interessante encontrar caminhos mınimos em grafos levando em conta os pesos nas
arestas. Dados um grafo G = (VG, EG) e uma funcao w : EG → R de pesos, definimos o
peso de um caminho P = (v0, v1, . . . , vk) como a soma dos pesos das arestas de P , i.e.,
w(P ) =k−1∑i=0
w(vivi+1).
Assim, dados u, v ∈ VG, o peso de um caminho mınimo de u a v em G, denotado por
distG(u, v), e definido como
distG(u, v) =
minw(P ) : P e caminho de u a v, se existe caminho de u a v,
∞, caso contrario.
Pesos de ciclos sao definidos da mesma forma, i.e., e igual a soma dos pesos das arestas
do ciclo. No restante desta secao vamos considerar um grafo G = (VG, EG) e uma
funcao w : EG → R de pesos nas arestas de G.
Antes de analisarmos algoritmos para encontrar caminhos mınimos, precisamos
tratar de algumas tecnicalidades envolvendo ciclos: se existe um ciclo de peso negativo
em uma trilha de u a v, entao ao percorrer uma trilha que passa repetidamente por tal
ciclo, conseguimos obter uma trilha de u a v de peso tao pequeno quanto quisermos.
Assim, no problema de caminhos mınimos vamos assumir que nao existem ciclos de
peso negativo no grafo em questao.
18.1 Algoritmo de Dijkstra
Um classico algoritmo para resolver o problema de caminhos mınimos e o algoritmo
de Dijkstra. Esse algoritmo e muito eficiente, mas tem um ponto fraco, que e o fato
de nao funcionar quando o grafo contem arestas de peso negativo. Assim, nesta secao
vamos assumir que o digrafo G em que queremos encontrar caminhos mınimos nao
contem arestas de peso negativo.
Esse e mais um algoritmo inspirado pela estrategia utilizada no algoritmo de busca
em largura, de modo que a estrutura do algoritmo de Dijkstra e bem semelhante a
estrutura do algoritmo de busca em largura e do algoritmo de Prim (para encontrar
arvores geradoras mınimas).
Dado um vertice s ∈ VG, que sera o vertice inicial, o Algoritmo de Dijkstra calcula a
distancia de s a todos os vertices de G, salvando tambem um caminho mınimo de s aos
vertices de G. Cada vertice v do grafo vai ter um atributo v.dist que contem a melhor
estimativa de distancia entre s e v conhecida pelo algoritmo ate o momento. Vamos
fazer uso de uma fila de prioridades F baseada nas chaves v.dist de cada vertice v ∈ VG.
O algoritmo funciona como segue: a cada iteracao o algoritmo atualiza as informacoes
sobre caminhos mınimos de s aos outros vertices, de acordo com as arestas exploradas
ate o momento. A cada iteracao, o algoritmo garante que o peso de um caminho
mınimo de s a algum vertice v e calculado corretamente. Tal vertice v e removido da
fila de prioridades F , indicando que o caminho mınimo ate ele ja foi calculado. Isso
e feito de forma iterativa, de modo que a cada iteracao o algoritmo encontra o peso
de um caminho mınimo de s a um vertice v que ainda esta em F (i.e., um vertice v
cujo peso do caminho mınimo a partir de s ainda nao foi garantido pelo algoritmo).
Em cada iteracao, o vertice v escolhido sera sempre aquele que tem o menor peso
estimado em v.dist pelo algoritmo no momento. Veremos que essa escolha garante
que, no momento em que v e escolhido para sair de F , temos v.dist = distG(s, v) (veja
Teorema 18.2).
170
O algoritmo tambem mantera atributos v.pai que permitem se obter um caminho
mınimo de s a v, e os atributos v.indice contendo o ındice de v dentro da fila de
prioridades F . Ao fim do algoritmo a fila F fica vazia, garantindo que a distancia de s
a todos os vertices do grafo foi calculada.
Algoritmo 51: Dijkstra(G = (VG, EG), w, s)
1 para todo vertice v ∈ VG faca
2 v.dist =∞3 v.pai = null
4 s.dist = 0
5 cria fila de prioridades F com conjunto VG baseada em v.dist
6 para i = 1 ate |VG| faca
7 u = Remocao-min(F )
8 para todo vertice v ∈ N(u) em F faca
9 se v.dist > u.dist + w(u, v) entao
10 v.pai = u
11 v.dist = u.dist + w(u, v)
12 Diminui-chave(F, v.indice, u.dist + w(u, v))
A Figura 18.1 contem um exemplo de execucao do algoritmo de Dijkstra.
Figura 18.1: Execucao do algoritmo de Dijkstra. Vertices se tornam vermelhos quandosao removidos da fila de prioridades. Cada uma das quatro ultimas ilustracoes indicauma completa iteracao do primeiro laco para.
171
Assim como o algoritmo de Prim, o algoritmo de Dijkstra toma, a cada passo, a
decisao mais apropriada no momento. Mais precisamente, o algoritmo escolhe o vertice
v ∈ F incidente a aresta de menor peso entre vertices de F e vertices fora de F e essa
decisao nao e modificada no restante da execucao do algoritmo. Assim, tambem e
considerado um algoritmo guloso.
O tempo de execucao depende de como o grafo G e a fila de prioridades F sao
implementados. Assim, como na busca em largura e no algoritmo de Prim, a forma
mais eficiente e representar o grafo G atraves de uma lista de adjacencias. Vamos
assumir que F e uma fila de prioridades implementada atraves do uso de um heap
binario como no Capıtulo 6.
Seja n = |VG| e m = |EG|. Dado que o primeiro laco para e executado n vezes, o se-
gundo laco para e executado |N(v)| vezes para cada v ∈ VG, cada operacao Remocao-
min(F ) e executada em tempo O(log n), e cada operacao Diminui-chave(F, v, u) que
leva tempo O(log n), uma analise muito similar a feita no algoritmo de Prim mostra
que o tempo de execucao de Dijkstra(G = (VG, EG), w, s) e O((m+ n) log n
).
O seguinte lema sera usado na prova da corretude do algoritmo de Dijkstra.
Lema 18.1
Sejam G = (VG, EG) um grafo, w uma funcao de pesos nao negativos em EG, e
s ∈ VG. Em qualquer ponto da execucao de Dijkstra(G = (VG, EG), w, s), temos
que v.dist ≥ distG(s, v) para todo v ∈ VG.
O seguinte resultado mostra que o algoritmo de Dijkstra calcula corretamente os
caminhos mınimos.
Teorema 18.2
Ao final da execucao de Dijkstra(G = (VG, EG), w, s) temos v.dist = dist(s, v)
para todo v ∈ VG.
Demonstracao. Nessa prova consideramos uma execucao de Dijkstra(G = (VG, EG), w, s).
Inicialmente perceba que como a cada iteracao do primeiro laco para um vertice e
removido de F e nenhum vertice e adicionado a F (apos a criacao de F ), o algoritmo e
encerrado apos |VG| iteracoes desse laco e a fila F e vazia. Precisamos mostrar que
172
quando isso acontece, temos v.dist = dist(s, v) para todo v ∈ VG.
Uma vez que o algoritmo nunca modifica o atributo v.dist depois que v sai de F ,
basta provarmos que
quando um vertice v e removido de F , temos v.dist = dist(s, v) nesse momento.
Suponha por contradicao que existe um vertice u com
u.dist > dist(s, u) (18.1)
no momento em que u saiu de F . Seja u o primeiro vertice com u.dist > dist(s, u)
a ser removido de F . Assim, para todo vertice v removido de F antes de u, temos
v.dist = dist(s, v).
Analisaremos a situacao do algoritmo no inıcio da iteracao do laco enquanto que
removeu u de F . Seja P um caminho mınimo de s a u e seja w o primeiro vertice de
P que pertence a F . Ademais, seja v o vertice imediatamente antes de w em P .
Note que a parte inicial de P que vai de s a w e um caminho mınimo de s a w,
pois caso contrario P nao seria um caminho mınimo de s a u. Pela escolha de u, temos
v.dist = dist(s, v). Portanto, quando o algoritmo analisou a aresta vw (ela certamente
foi analisada, pois pela escolha de w sabemos que v ja foi removido da F ), obtemos
w.dist = v.dist + w(v, w) = dist(s, v) + w(v, w) = dist(s, w).
Como nao existem arestas de peso negativo, dist(s, w) ≤ dist(s, u). Logo,
w.dist = dist(s, w) ≤ dist(s, u), (18.2)
mas, no momento em que u e escolhido para ser removido de F , os vertices u e w
ainda estao em F . Assim, pela linha 7, temos u.dist ≤ w.dist. Combinando esse fato
com (18.2), temos u.dist ≤ dist(s, u), uma contradicao com (18.1).
173
18.2 Algoritmo de Bellman-Ford
O algoritmo de Bellman-Ford resolve o problema de caminhos mınimos mesmo quando
ha arestas de peso negativo no grafo ou digrafo em questao. Mais ainda, quando existe
um ciclo de peso total negativo, o algoritmo identifica a existencia de tal ciclo. Dessa
forma, e um algoritmo que funciona para mais instancias que o algoritmo de Dijkstra.
Por outro lado, como veremos a seguir, e menos eficiente que o algoritmo de Dijkstra.
O algoritmo de Bellman-Ford recebe um grafo G = (VG, EG), uma funcao w de pesos
nas arestas de G e um vertice s inicial. Assim como no algoritmo de Dijkstra, dado um
vertice v, o atributo v.dist sempre contem a menor distancia de s a v conhecida pelo
algoritmo. Porem, a forma como essas distancias sao atualizadas ocorre de forma bem
diferente. O algoritmo vai tentar, em |VG| − 1 iteracoes, melhorar a distancia conhecida
de s a todos os vertices v analisando todas as |EG| arestas de G em cada iteracao.
O algoritmo mantem atributos v.pai que permitem se obter um caminho mınimo
de s a v. No final de sua execucao, o algoritmo retorna “verdade” se G nao contem
ciclos de peso negativo, e retorna “falso” caso exista algum ciclo de peso negativo em G.
Algoritmo 52: Bellman-Ford(G = (VG, EG), w, s)
1 para todo vertice v ∈ V faca
2 v.dist =∞3 v.pai = null
4 s.dist = 0
5 para i = 1 ate |VG| − 1 faca
6 para toda aresta uv ∈ EG faca
7 se v.dist > u.dist + w(u, v) entao
8 v.pai = u
9 v.dist = u.dist + w(u, v)
10 para toda aresta uv ∈ EG faca
11 se v.dist > u.dist + w(u, v) entao
12 retorna “falso”
13 retorna “verdade”
174
A Figura 18.2 mostra um exemplo de execucao do algoritmo Bellman-Ford(G =
(VG, EG), w, s).
Figura 18.2: Execucao do algoritmo de Bellman-Ford.
Antes de entendermos qual a razao do algoritmo de Bellman-Ford funcionar corre-
tamente, vamos analisar seu tempo de execucao. Seja n = |VG| e m = |EG| e considere
que o grafo G esta implementado utilizando uma lista de adjacencias. Por causa
do laco para na linha 1, as linhas 1–4 sao executadas em tempo Θ(n). Ja os lacos
aninhados nas linhas 5 e 6 fazem com que a linha 7 seja executada nm vezes (note
que as linhas 8 e 9 sao executadas no maximo nm vezes). Assim, o tempo gasto nas
execucoes das linhas 5–9 e Θ(nm). Por fim, o laco da linha 10 garante que o teste na
linha 11 seja executado no maximo m vezes. Logo, o tempo gasto nas linhas 10–12
e O(m). Portanto, o tempo de execucao de Bellman-Ford(G = (VG, EG), w, s) e
Θ(n) + Θ(nm) +O(m), que e igual a Θ(nm).
Voltemos nossa atencao agora para a corretude do algoritmo. O lema abaixo e a
peca chave para entender a razao pela qual o algoritmo funciona corretamente. Por
simplicidade, vamos nos referir a execucao das linhas 7–9 para uma aresta uv como
175
relaxacao da aresta uv, i.e., dizemos que a aresta uv e relaxada quando verificamos se
v.dist > u.dist + w(u, v), atualizando, em caso positivo, o valor de v.distancia para
u.dist + w(u, v).
Lema 18.1
Seja G = (VG, EG) um grafo com uma funcao de pesos w em suas arestas e seja
s ∈ VG. Considere s.dist = 0 e v.dist =∞ para todo vertice v ∈ VG \ s. Se
P = (s, v1, v2, . . . , vk) e um caminho mınimo de s a vk, entao o seguinte vale.
Se as arestas sv1, v1v2, . . ., vk−1vk forem relaxadas nessa ordem, entao temos
vk.dist = dist(s, vk) apos essas relaxacoes.
Demonstracao. Provaremos o resultado por inducao na quantidade de arestas de um
caminho mınimo P = (s, v1, v2, . . . , vk). Se o comprimento do caminho e 0, i.e., nao
ha arestas, entao o caminho e formado somente pelo vertice s. Logo, tem distancia 0.
Para esse caso, o teorema e valido, dado que temos s.dist = 0 = dist(s, s).
Seja k ≥ 1 e suponha que para todo caminho mınimo com k − 1 arestas o teorema
e valido. Considere o caminho mınimo P = (s, v1, v2, . . . , vk) de s a vk com k arestas e
suponha que as arestas sv1, v1v2, . . ., vk−1vk foram relaxadas nessa ordem. Note que
como P ′ = (s, v1, v2, . . . , vk−1) e um caminho dentro de um caminho mınimo, entao P ′
tambem e um caminho mınimo. Assim, como as arestas de P ′, a saber sv1, v1v2, . . .,
vk−2vk−1, foram relaxadas na ordem do caminho e P ′ tem k− 1 arestas, concluımos por
hipotese de inducao que vk−1.dist = dist(s, vk−1). Caso vk.dist = dist(s, vk), entao a
prova esta concluıda. Assim, podemos assumir que
vk.dist > dist(s, vk) = dist(s, vk−1) + w(vk−1, vk).
Logo, ao relaxar a aresta vk−1vk, o algoritmo vai verificar que vk.dist > dist(s, vk) =
dist(s, vk−1) + w(vk−1, vk), atualizando o valor de vk.dist como abaixo.
vk.dist =vk−1.dist + w(vk−1, vk)
= dist(s, vk−1) + w(vk−1, vk)
= dist(s, vk).
176
Com isso, a prova esta concluıda.
Note que, no Lema 18.1, nao importa que arestas tenham sido relaxadas entre
quaisquer das relaxacoes sv1, v1v2, . . ., vk−1vk. O Lema 18.1 garante que se as arestas
de um caminho mınimo de s a v forem relaxadas na ordem correta, entao o algoritmo
de Bellman-Ford calcula corretamente o valor de um caminho mınimo de s a v. Mas
como o algoritmo de Bellman-Ford garante isso para todo vertice v ∈ VG? A chave
e notar que todo caminho tem no maximo n − 1 arestas, de modo que relaxando
todas as arestas n − 1 vezes, e garantido que qualquer que seja o caminho mınimo
P = (s, v1, v2, . . . , vk) de s a um vertice vk, as arestas desse caminho vao ser relaxadas
na ordem correta. A Figura 18.3 mostra um exemplo ilustrando que as arestas de um
caminho mınimo P sempre sao relaxadas na ordem do caminho P . O Lema 18.2 abaixo
torna a discussao acima precisa, mostrando que o algoritmo Bellman-Ford calcula
corretamente os caminhos mınimos, dado que nao exista ciclo de peso negativo.
Figura 18.3: Ordem de relaxacao das arestas de um caminho mınimo de s a v.
Lema 18.2
Seja G = (VG, EG) um grafo com uma funcao de pesos w em suas arestas e seja
s ∈ VG. Se G nao contem ciclos de peso negativo, entao apos terminar a execucao
177
das linhas 5–9 de Bellman-Ford(G = (VG, EG), w, s) temos v.dist = dist(s, v)
para todo vertice v ∈ VG.
Demonstracao. Seja G um grafo sem ciclos de peso negativo, e considere o momento
apos o termino da execucao das linhas 5–9 de Bellman-Ford(G = (VG, EG), w, s). Se
vk nao e alcancavel a partir de s, entao temos v.dist =∞ e nao e difıcil verificar que
o algoritmo nunca vai modificar o valor de v.dist. Como nao existem ciclos de peso
negativo, sabemos que existe algum caminho mınimo de s a qualquer vertice alcancavel
a partir de s. Assim, seja P = (s, v1, v2, . . . , vk) um caminho mınimo de s a um vertice
arbitrario vk que pode ser alcancavel a partir de s. Note que como P e um caminho
mınimo, entao P tem no maximo |VG| − 1 arestas.
Seja v0 = s. Como a cada uma das |VG| − 1 iteracoes do laco para na linha 5 todas
as arestas do grafo sao relaxadas, temos que certamente, para 1 ≤ i ≤ k, a aresta
vi−1vi e relaxada na iteracao i. Assim, as arestas v0v1, v1v2, . . ., vk−1vk sao relaxadas
nessa ordem. Pelo Lema 18.1, temos vk.dist = dist(s, vk). Assim, a prova do lema
esta concluıda.
Usando o Lema 18.2, podemos facilmente notar que o algoritmo identifica um ciclo
de peso negativo.
Corolario 18.3
Seja G = (VG, EG) um grafo com uma funcao de pesos w em suas arestas e seja
s ∈ VG. Se Bellman-Ford(G = (VG, EG), w, s) retorna “falso”, entao G contem
um ciclo de peso negativo.
Demonstracao. Se Bellman-Ford(G = (VG, EG), w, s) retorna “falso”, entao apos
a execucao das linhas 5–9, existe uma aresta uv tal que v.dist > u.dist + w(u, v).
Mas e facil mostrar que a qualquer momento do algoritmo, se o valor em v.dist
e finito, entao ele representa o peso de algum caminho entre s e v. Logo, como
v.dist > u.dist + w(u, v), sabemos que o peso em v.dist e maior do que o peso de
um caminho de s a v passando por u. Portanto, v.dist > dist(s, v). Assim, usando a
contrapositiva do Lema 18.2, concluımos que G contem um ciclo de peso negativo.
Agora que sabemos que o algoritmo de Bellman-Ford funciona corretamente, vamos
178
compara-lo com o algoritmo de Dijkstra, que tambem resolve o problema de caminhos
mınimos de um vertice s para os outros vertices do grafo. Dado um grafo G com n
vertices e m arestas, o algoritmo de Dijkstra e executado em tempo O((n+m) log n),
que e assintoticamente mais eficiente que o algoritmo de Bellman-Ford sempre que
m = Ω(log n), dado que o algoritmo de Bellman-Ford leva tempo Θ(mn) para ser
executado. Porem, o algoritmo de Bellman-Ford funciona em grafos que contem arestas
de peso negativo, diferentemente do algoritmo de Dijkstra. Por fim, observamos que o
algoritmo de Bellman-Ford tambem tem a capacidade de identificar a existencia de
ciclos negativos no grafo.
18.3 Caminhos mınimos entre todos os pares de
vertices
Considere agora o problema de encontrar caminhos mınimos (e calcular seus pesos)
entre todos os pares de vertices de um grafo ou digrafo G = (VG, EG) com n vertices
e m arestas. Certamente uma opcao simples para resolver esse problema e executar
Dijkstra ou Bellman-Ford n vezes, passando cada um dos vertices v em VG como vertice
inicial do algoritmo. Dessa forma, a cada uma das n execucoes de Dijkstra ou Bellman-
Ford, encontramos um caminho mınimo de um vertice v a todos os outros vertices do
grafo G. Note que, como o tempo de execucao de Dijkstra(G = (VG, EG), w, s) e
O((m+n) log n
), entao ao executar Dijkstra n vezes, terıamos um tempo de execucao
total de O((mn + n2) log n
). Ressaltamos que, caso a fila de prioridades utilizada
no algoritmo de Dijkstra seja implementada com um heap de Fibonacci, o tempo de
execucao total e da ordem de
O(n2 log n+ nm
). (18.3)
Para grafos densos (i.e., grafos com Θ(n2) arestas), esse valor representa um tempo de
execucao da ordem de
O(n3).
Porem, se existirem arestas de peso negativo em G, entao o algoritmo de Dijkstra nao
funciona. Se em vez de Dijkstra executarmos o algoritmo de Bellman-Ford n vezes,
179
terıamos um tempo de execucao total de Θ(n2m), que no caso de grafos densos e da
ordem de
Θ(n4).
18.3.1 Algoritmo de Floyd-Warshall
O algoritmo de Floyd-Warshall, que e um algoritmo de programacao dinamica, encontra
caminhos mınimos (e calcula seus pesos) entre todos os pares de vertices de um grafo
ou digrafo G em tempo Θ(n3).
Dado um grafo G = (VG, EG) com n vertices e m arestas, o algoritmo de Floyd-
Warshall recebe como entrada uma matriz W com n linhas e n colunas, onde o elemento
W (i, j) na i-esima linha e j-esima coluna contem o peso da aresta ij, caso ela exista.
Temos W (i, i) = 0 para 1 ≤ i ≤ n, e se ij nao e uma aresta de G, entao W (i, j) =∞. O
algoritmo retorna matrizes n×n D e Π tal que D(i, j) e Π(i, j) contem, respectivamente,
o peso de um caminho mınimo de i a j, e o vertice que esta imediatamente antes de j
em um caminho mınimo de i a j.
Primeiramente vamos analisar a estrutura de caminhos mınimos para descrever
tal estrutura e definir recursivamente o peso dos caminhos mınimos baseados nessa
estrutura. No que segue, seja VG = v1, v2, . . . , vn. Note que, dado um caminho
mınimo P de vi a vj tal que todos os vertices internos de P estao no conjunto dos
primeiros k vertices de VG, i.e., v1, . . . , vk, temos as duas seguinte possibilidades:
(i) se vk nao e vertice interno de P , entao existe um caminho mınimo de vi a vj com
vertices internos em v1, . . . , vk−1; (ii) se vk e vertice interno de P , entao P e formado
por um caminho mınimo de vi a vk, e um caminho mınimo de vk a vj, ambos com
vertices internos no conjunto v1, . . . , vk−1.
Dada a discussao acima, ja conseguimos definir a estrutura recursiva que vamos
utilizar. Defina a matriz n× n Dk tal que Dk(i, j) armazena o peso de um caminho
mınimo dado que todos os vertices internos do caminho estejam no conjunto v1, . . . , vk.Note que D = D0 e que Dn contem os pesos dos caminhos mınimos entre todos os
pares de vertices. A seguinte definicao recursiva para o peso de um caminho mınimo
180
Dk(i, j) de vi a vj cujos vertices internos estao em v1, . . . , vk e dada por
Dk(i, j) =
W (i, j), se k = 0,
minDk−1(i, j), Dk−1(i, k),+Dk−1(k, j), se 1 ≤ k ≤ n.
Lembre que queremos manter o vertice que esta imediatamente antes de vj em um
caminho mınimo de vi a vj na posicao Π(i, j) de Π. O seguinte algoritmo Floyd-
Warshall-pre(W,n) (versao Bottom-up) implementa a discussao acima. O parametro
n passado para o algoritmo e a quantidade de linhas (e colunas) de W .
Algoritmo 53: Floyd-Warshall-pre(W,n)
1 D0 = W
2 Cria matriz Π com n linhas e n colunas, todas contendo null
/* Para toda aresta vivj, vamos fazer Π(i, j) = i */
3 para i = 1 ate n faca
4 para j = 1 ate n faca
5 se W (i, j) 6=∞ entao
6 Π(i, j) = i
7 para k = 1 ate n faca
8 Cria matriz Dk = Dk−1
9 para i = 1 ate n faca
10 para j = 1 ate n faca
11 valor = Dk−1(i, k) +Dk−1(k, j)
12 se Dk(i, j) > valor entao
13 Dk(i, j) = valor
14 Π(i, j) = Π(k, j)
15 retorna (Dn,Π)
Note que, devido a ordem em que os tres lacos aninhados sao executados, podemos
utilizar somente uma matriz D durante todo o algoritmo em vez de usar as matrizes
D0, D1, . . . , Dn, pois a matriz Dk−1 e usada somente na k-esima iteracao do laco para
181
na linha 7. Assim, podemos simplificar o algoritmo acima.
Algoritmo 54: Floyd-Warshall(W,n)
1 D = W
2 Cria matriz Π com n linhas e n colunas
3 para i = 1 ate n faca
4 para j = 1 ate n faca
5 se W (i, j) 6=∞ entao
6 Π(i, j) = i
7 para k = 1 ate n faca
8 para i = 1 ate n faca
9 para j = 1 ate n faca
10 se D(i, j) > D(i, k) +D(k, j) entao
11 D(i, j) = D(i, k) +D(k, j)
12 Π(i, j) = Π(k, j)
13 retorna (D,Π)
Por causa dos tres lacoes aninhados, claramente o tempo de execucao de Floyd-
Warshall(W,n) e Θ(n3), que e bem melhor que o tempo Θ(n4) gasto em n execucoes
do algoritmo de Bellman-Ford. Porem, note que para grafos esparsos (i.e., com
m = o(n2) arestas), a opcao mais eficiente assintoticamente e executar o algoritmo de
Dijkstra repetidamente, gastando tempo total o(n3) (veja (18.3)). Mas, novamente,
temos o empecilho de que o algoritmo de Dijkstra funciona somente para grafos sem
arestas de peso negativo. Na proxima secao veremos o algoritmo de Jonhson, que tem
tempo de execucao igual a repetidas execucoes de Dijkstra, i.e., tempo O(n2 log n+nm
),
que e igual a o(n3) para grafos esparsos. O algoritmo de Johnson combina execucoes
de Bellman-Ford e Dijkstra, funcionando mesmo para grafos que contem arestas de
peso negativo.
182
18.3.2 Algoritmo de Johnson
O algoritmo de Johnson faz uso de um truque para converter um grafo G = (VG, EG)
com funcao de pesos w : EG → R em um novo grafo G′ = (VG′ , EG′) que contem
somente um vertice a mais que G e suas arestas tem pesos de acordo com uma funcao
de pesos nao negativos w′ : EG′ → R≥0.
O algoritmo de Johnson adiciona um vertice s a VG e todas as arestas sv, para todo
v ∈ VG. Todas as novas arestas tem peso 0, i.e., faca w(s, v) = 0 para todo v ∈ VG.
Feito isso, executamos Bellman-Ford(G,w, s) para obter o peso de um caminho
mınimo, dist(s, v) entre s e todo vertice v ∈ VG. Agora vem um passo importantıssimo,
que e transformar os pesos da funcao w em pesos nao negativos, formando a funcao w′.
O novo peso de cada aresta uv sera dado por
w′(u, v) =(
dist(s, u) + w(u, v))− dist(s, v). (18.4)
Note que dada uma aresta uv, sempre temos dist(s, u) +w(u, v) ≥ dist(s, v). Portanto,
a funcao w′ e composta por pesos nao negativos. Podemos aplicar Dijkstra(G′, w′, s)
n vezes, passando em cada uma dessas vezes um dos vertices de G como vertice inicial
s, calculando os caminhos mınimos de u a v no grafo G′ com funcao de pesos w′ para
todo par de vertices u, v.
Nao e difıcil mostrar que dado um caminho P = (v1, . . . , vk) de u a v em G e um
caminho mınimo com funcao w se e somente se P e um caminho mınimo com a funcao
w′. Para calcular o valor dos caminhos mınimos em G com a funcao de pesos original
w basta fazer, para cada par uv,
dist(u, v) = dist′(u, v) + dist(s, v)− dist(s, u).
O seguinte fato garante que a igualdade acima coloca o peso correto em dist(u, v):
seja P = (u = v1, . . . , vk = v) um caminho mınimo de u a v com funcao w′. Assim,
183
utilizando (18.4), obtemos
dist′(u, v) = w′(v1, v2) + . . .+ w′(vk−1, vk)
= w(v1, v2) + . . .+ w(vk−1, vk)
+ dist(s, v1) + dist(s, v2) + · · ·+ dist(s, vk−1)
− dist(s, v2)− · · · − dist(s, vk−1)− dist(s, vk)
= w(v1, v2) + . . .+ w(vk−1, vk) + dist(s, u)− dist(s, v)
= dist(u, v) + dist(s, u)− dist(s, v).
Portanto, de fato temos dist(u, v) = dist′(u, v) + dist(s, v)− dist(s, u). Abaixo temos o
algoritmo de Johnson, que, caso nao exista ciclo de peso negativo no grafo, retorna
uma matriz D com n linhas e n colunas tal que D(i, j) contem o peso de um caminho
mınimo de vi a vj.
Algoritmo 55: Johnson(G = (VG, EG), w)
1 Crie grafo G′ = (VG′ , EG′), onde VG′ = VG ∪ s e EG′ = EG ∪ sv : v ∈ VG2 Estenda a funcao w fazendo w(s, v) = 0 para todo v ∈ VG3 Crie uma matriz D com n linhas e n colunas
4 se Bellman-Ford(G,w, s) == “falso” entao
5 retorna “O grafo G contem ciclo de peso negativo”
6 crie vetor A = [1..n] para todo vertice u ∈ VG faca
7 Execute Bellman-Ford(G,w, s) para fazer u.dist-s = dist(s, u)
8 para toda aresta uv ∈ EG′ faca
9 w′(u, v) = u.dist-s + w(u, v)− v.dist-s
10 para todo vertice u ∈ VG faca
11 Execute Dijkstra(G,w′, u) para fazer v.dist = dist′(u, v) ∀v ∈ VG12 para todo vertice v ∈ VG faca
13 D(u, v) = v.dist + v.dist-s− u.dist-s
14 retorna D
O tempo de execucao de Johnson(G = (VG, EG), w) e o mesmo de n execucoes
184
de Dijkstra. De fato, a linha 11, que e executada para cada vertice do grafo e o que
determina o tempo de execucao de Johnson(G = (VG, EG), w).
185
186
Parte
VI
Teoria da computacao
Capıtulo
19
Complexidade computacional
Um algoritmo e dito eficiente se seu tempo de execucao e O(nk), onde n e o tamanho
da entrada do algoritmo e k e um inteiro positivo que nao depende de n. Todos os
problemas que vamos tratar nesta secao sao problemas de decisao, que definimos abaixo.
Definicao 19.1
Um problema de decisao e um problema cuja solucao e uma resposta sim ou nao.
Por exemplo, decidir se um numero e par e um problema de decisao. Outro problema
de decisao e decidir se existe um caminho entre dois vertices de um grafo. Um problema
que nao e problema de decisao e exibir um caminho mınimo entre dois vertices de um
grafo.
No que segue vamos classificar problemas de decisao e discutir as relacoes entre
essas classes de problemas. As principais classes de problemas sao P, NP e co-NP.
Mas antes precisamos de algumas definicoes relacionadas a verificacao de solucoes para
problemas.
19.1 Classes P, NP e co-NP
Considere o problema Clique-k abaixo.
Problema 19.1: Clique-k
Dados um grafo G e um inteiro positivo k, o problema Clique-k(G, k) consiste
em determinar se G contem um subgrafo isomorfo a um grafo completo com pelo
menos k vertices.
Nesse problema, a resposta e sim caso exista o grafo completo e nao caso contrario.
Note que, se de alguma forma recebermos um subgrafo completo H de G com k vertices,
e facil escrever um algoritmo Alg eficiente para verificar se H e realmente um grafo
completo: basta verificar se todos seus pares de vertices formam arestas. Nesse caso,
dizemos que H e um certificado positivo para Clique-k(G,k), e o algoritmo Alg e
um verificador que aceita o certificado positivo H.
Um grafo e bipartido se e possıvel particionar seu conjunto de vertices em duas
partes tal que todas as arestas do grafo estao entre essas partes. Considere agora
o problema Bipartido(G) que consiste em determinar se um grafo G e bipartido.
Nesse problema, a resposta e sim caso G seja bipartido e nao caso contrario. Um
classico resultado da Teoria dos Grafos afirma que um grafo e bipartido se e somente se
nao contem um ciclo com uma quantidade ımpar de vertices. Note que uma particao
dos vertices do grafo em duas partes tal que todas as arestas estao entre as partes
e um verificador positivo para Bipartido(G) e e facil escrever um verificador para
esse certificado. Mas observe tambem que um ciclo ımpar C e o que chamamos de
certificado negativo, que e um conjunto de dados tal que existe um algoritmo eficiente
que verifica que a resposta de Bipartido(G) e nao. Tal algoritmo e um verificador
que aceita o certificado negativo C.
Definicao 19.2: Certificado positivo
Um certificado positivo para um problema de decisao P e uma instancia I e um
conjunto de dados D tal que existe um algoritmo eficiente que recebe D e verifica
se a resposta de P para a instancia I e sim. Tal algoritmo e um verificador que
aceita o certificado positivo D.
190
Definicao 19.3: Certificado negativo
Um certificado negativo para um problema de decisao P e uma instancia I e um
conjunto de dados D tal que existe um algoritmo eficiente que recebe D e verifica
se a resposta de P para a instancia I e nao. Tal algoritmo e um verificador que
aceita o certificado negativo D.
Agora estamos prontos para definir as classes P, NP e co-NP.
Definicao 19.4: Classe P
P e a classe dos problemas de decisao que podem ser resolvidos por um algoritmo
eficiente.
Portanto, sabemos que o problema de determinar se existe um caminho entre dois
vertices de um grafo esta na classe P, pois, por exemplo, os algoritmos de busca em
largura e profundidade sao algoritmos eficientes que resolvem este problema.
Outro exemplo de problema na classe P e o problema de decidir se um grafo possui
uma arvore geradora de peso total menor que k. Pois se executarmos, por exemplo, o
algoritmo de Prim e verificarmos se uma arvore geradora mınima tem peso menor que
k entao a resposta para o problema e sim, caso contrario a resposta e nao. Portanto,
todos os problemas para os quais conhecemos um algoritmo eficiente que o resolva
estao na classe P.
Para definir as classes NP e co-NP precisamos usar os conceitos de verificadores e
certificados positivos e negativos.
Definicao 19.5: Classe NP
NP e a classe dos problemas de decisao em que existe um verificador que aceita
um certificado positivo.
A definicao da classe co-NP e similar a da classe NP.
191
Definicao 19.6: Classe co-NP
co-NP e a classe dos problemas de decisao em que existe um verificador que
aceita um certificado negativo.
Como discutido anteriormente, existe um verificador que aceita um certificado
positivo para o problema Clique-k(G, k). Assim, Clique-k(G, k) esta em NP.
Tambem mencionamos que existem verificadores que aceitam certificados positivos e
negativos para Bipartido(G), que garante que Bipartido(G) esta em NP e em
co-NP. Na verdade, todo problema da classe P esta em NP e em co-NP. Isso se da
pelo fato de que um algoritmo eficiente que resolve o problema e um verificador que
aceita certificados positivos e negativos, onde os certificados sao a propria entrada do
algoritmo, pois o algoritmo recebe a entrada e verifica se a resposta do problema e sim
ou nao em tempo polinomial. Portanto, temos o seguinte resultado.
Teorema 19.7
Vale que P ⊆ NP e P ⊆ co-NP.
Uma questao natural (e muito importante!) e saber se e verdade que NP ⊆ P.
Porem, essa questao continua em aberto ate os dias atuais. Dada sua importancia,
esse problema e um dos Problemas do Milenio e o Clay Institute oferece um premio
monetario de $1.000.000, 00.
19.2 NP-completude
Muitas vezes e possıvel resolver um problema de decisao P utilizando para isso um
problema de decisao Q que sabemos resolver. Para isso, precisamos converter a entrada
E1 de P para uma entrada de E2 Q de modo que a resposta de E2 em Q e sim se
e somente se a resposta para E1 em P e sim. Dessa forma, se sabemos resolver Q,
entao automaticamente obtemos a resposta para P . A definicao abaixo torna essa ideia
precisa.
192
Definicao 19.1: Reducao polinomial
Sejam P e Q problemas de decisao. O problema P e redutıvel a Q se existe
um algoritmo eficiente que converte uma entrada E1 para P em uma entrada E2
para Q de modo que a resposta para P com entrada E1 e sim se e somente se a
resposta para Q com entrada E2 e sim.
Escrevemos P ≤ Q para denotar que P e redutıvel a Q.
Dadas variaveis booleanas x1, . . . , xn, i.e., que so recebem valores 0 ou 1, e uma
formula composta por conjuncoes (operadores e) de conjuntos de disjuncoes (operadores
ou) das variaveis dadas e suas negacoes. Exemplos dessas formulas sao
(x1 ∨ x2 ∨ x3 ∨ x4)∧ (x1 ∨ x2) e (x1 ∨ x2 ∨ x3)∧ (x1 ∨ x2 ∨ x4 ∨ x5)∧ (x4 ∨ x5 ∨ x6).
Cada conjunto de disjuncoes e chamado de clausula e um literal e uma variavel x
ou sua negacao x. Uma formula booleana composta por conjuncoes de clausulas que
contem exatamente 3 literais e chamada de 3-CNF. Por exemplo, as formulas abaixo
sao 3-CNF.
(x1 ∨ x2 ∨ x3) ∧ (x1 ∨ x2 ∨ x4) e (x1 ∨ x2 ∨ x3) ∧ (x1 ∨ x2 ∨ x4) ∧ (x4 ∨ x5 ∨ x6).
Considere o seguinte problema conhecido como 3-satisfabilidade ou 3-sat.
Problema 19.2: 3-SAT
Dada uma formula 3-CNF φ contendo literais de variaveis booleanas x1, . . . , xn,
o problema 3-Sat(φ) consiste em decidir se existe uma atribuicao de valores a
x1, . . . , xn tal que φ e satisfatıvel, i.e., φ tem valor 1.
O resultado abaixo mostra que 3-Sat ≤ Clique-k, i.e., existe uma reducao
polinomial de 3-Sat para Clique-k, ou ainda, 3-Sat e redutıvel a Clique-k.
Teorema 19.3
3-Sat ≤ Clique-k.
193
Demonstracao. Precisamos exibir um algoritmo eficiente que converte uma 3-CNF φ
em um grafo G tal que φ e satisfatıvel se e somente se G contem um grafo completo
com k vertices.
O grafo G que construiremos possui 3k vertices, de modo que cada uma das k
clausulas tem 3 vertices representando cada um de seus literais. Um par de vertices
v e w de G forma uma aresta se e somente se v e w estao em clausulas diferentes, v
corresponde a um literal x, e w nao corresponde ao literal x. Veja Figura 19.1 para um
exemplo de construcao de G.
Figura 19.1: Construcao de um grafo G dada uma instancia de 3-Sat.
O proximo passo e verificar que φ e satisfatıvel se e somente se G contem um grafo
completo com k vertices. Para mostrar um lado dessa implicacao note que se φ e
satisfatıvel, entao em cada uma das k clausulas existe um literal com valor 1. Como
194
um literal e sua negacao nao podem ter valor 1, sabemos que em todo par x, ydesses k literais temos x 6= y. Portanto, existe uma aresta entre quaisquer dois vertices
representando esses literais em G, de modo que formam um grafo completo com k
vertices dentro de G.
Para verificar a volta da implicacao, suponha que G contem um grafo completo
H com k vertices. Assim, como existe uma aresta entre quaisquer dois vertices de
H, sabemos que qualquer par de vertices de H representa dois literais que nao sao a
negacao um do outro e estao em diferentes clausulas. Logo, φ e satisfatıvel.
A definicao abaixo descreve quando um problema esta na classe dos problemas
NP-completos.
Definicao 19.4: NP-completude
Um problema de decisao R e NP-completo se R ∈ NP e todo problema Q ∈ NP
e redutıvel a R, i.e., R ≤ Q.
Portanto, uma solucao eficiente de um problema NP-completo resolve todos os
problemas da classe NP. De fato, isso segue direto da definicao de reducao polinomial
e da definicao de NP-completude.
A forma mais utilizada para mostrar que um problema R e NP-completo e reduzindo
um problema Q que e NP-completo a R. Porem, para que essa estrategia funcione, e
necessario um ponto de partida, i.e., e necessario que exista uma prova de que algum
problema e NP-completo que nao necessite de outro problema NP-completo. Esse
ponto de partida e o problema 3-Sat. Foi provado por Cook e Levin que 3-Sat e
NP-completo. Assim, note que o Teorema 19.3 prova o seguinte resultado.
Teorema 19.5
Clique-k e NP-completo.
Note que para mostrar que NP ⊆ P, e suficiente provar que existe um algoritmo
eficiente que resolve um problema NP-completo Q, pois como todo problema da classe
NP e redutıvel a Q, terıamos um algoritmo eficiente para resolver todos os problemas
de NP.
195
