Lista 1 de exercícios de Análise de Algoritmos (Com gabarito) (Ayala)

Prévia do material em texto

Ana´lise de Algoritmos
Primeira Lista de Exerc´ıcios
Fundamentos matema´ticos da ana´lise de algoritmos e Algoritmos de
Ordenac¸a˜o
26 de marc¸o de 2008
Prof. Mauricio Ayala-Rinco´n
Entrega: 16 de abril de 2008 (100%) - Grupos de cinco pesso˜as
Sera´ disponibilizado um gabarito da lista, depois do dia 16 de abril.
Listas entregues entre 17 e 23 de abril de 2008: 50%
Listas entregues apo´s 23 de abril de 2008: 0%
Esta´giario de doceˆncia: Daniel Lima Ventura: ventura at mat dot unb dot br
Fundamentos
1. Complete a seguinte tabela determinando o maior tamanho de um problema que pode
ser solucionado em tempo t por um algoritmo A, para cada func¸a˜o fA(n) na seguinte
tabela. Supor que o algoritmo A resolve um problema de tamanho n em tempo fA(n)
microsegundos.
fA(n) 1 seg. 1 min. 1 hora 1 dia 1 meˆs 1 ano 1 se´culo
×60 ×60 ×24 ×30 ×12 ×100
ln(n)√
n
n 106 6 107 3.6 109 8.64 1010 2.592 1012 3.1104 1013 3.1104 1015
nln(n)
n2 103
√
60 103 6 104
√
8.64 105
√
2.592 106
√
31.104 106
√
31.104 107
n3 102
2n 19 25 31 36 41 44 51
n! 9 11 12 13 15 16 17
Caso existesem computadores que executaram 1 instruc¸a˜o por nanosegundo, determine
o maior tamanho de um problema que pode ser tratado em tempo t por algoritmos A
com func¸o˜es correspondentes fA(n) na seguinte tabela.
fA(n) 1 seg. 1 min. 1 hora 1 dia 1 meˆs 1 ano 1 se´culo
×60 ×60 ×24 ×30 ×12 ×100
n 109 6 1010 3.6 1012 8.64 1013 2.592 1013 3.1104 1016 3.1104 1018
n2
n3
2n
n!
1
2. Resolva as seguintes relac¸o˜es de recurreˆncia:
(a) T (1) = 1, T (n) = 3T (n/2) + n2, n ≥ 2;
(b) T (1) = 1, T (n) = 2T (n− 1) + 1, n ≥ 2;
(c) T (1) = 1, T (n) = 2T (n/2) + n, n ≥ 2;
(d) T (1) ∈ Θ(1), T (n) = 3T (n/2) + nln(n);
(e) T (1) ∈ Θ(1), T (n) = 3T (n/3 + 5) + n/2;
(f) T (1) ∈ Θ(1), T (n) = 2T (n/2) + n/ln(n);
(g) T (1) ∈ Θ(1), T (n) = T (n− 1) + 1/n;
(h) T (1) ∈ Θ(1), T (n) = T (n− 1) + ln(n);
(i) T (1) ∈ Θ(1), T (n) = √nT (√n) + n;
3. A func¸a˜o de Fibonacci e´ definida pela relac¸a˜o de recurreˆncia
F (0) = 0
F (1) = 1
F (n) = F (n− 1) + F (n− 2)
Seja F , uma func¸a˜o generatriz, definida por
F(z) =
∞∑
i=0
F (i)zi
Siga os seguintes passos para resolver a relac¸a˜o de recurreˆncia da func¸a˜o de Fibonacci.
(a) Demonstre que
F(z) = z
1− z − z2 =
z
(1− φz)(1− φ˜z) =
1√
5
(
1
1− φz −
1
1− φ˜z ),
onde
φ =
1 +
√
5
2
e φ˜ =
1−√5
2
(b) Demonstre que
F(z) =
∞∑
i=0
1√
5
(φi − φ˜i)zi
(c) Prove que F (i) = φi/
√
5 para i > 0, aproximado ao inteiro mais pro´ximo.
(d) Demonstre que F (i + 2) ≥ φi, para i ≥ 0.
(e) Conclua que F (n) ∈ Θ(φn); i.e., a func¸a˜o de Fibonacci e´ de complexidade ex-
poneˆncial.
2
Observe que tambe´m e´ poss´ıvel estimar limites inferior e superior para a complexidade
de F (n) da seguinte maneira:
∀n > 2, F (n) = F (n− 1) + F (n− 2) ⇒ 2 F (n− 2) ≤ F (n) ≤ 2 F (n− 1)
Considerando os casos n par e ı´mpar obtem-se:
n par: √
2
n
/2 = 2n/2−1 = 2n/2−1F (2) ≤ F (n) ≤ 2n−1F (1) = 2n−1
n ı´mpar: √
2
n−1
= 2bn/2cF (1) ≤ F (n) ≤ 2n−1F (1) = 2n−1
Consequentemente, F (n) ∈ O(2n) e F (n) ∈ Ω(√2n). Conclui-se que F (n) e´ limitada
inferior- e superiormente por funciones de classe de complexidade exponeˆncial.
Note que a conclusa˜o inicial, F (n) ∈ Θ(φn), e´ coerente com os limites anteriores,
sempre que
√
2 < φ =
1 +
√
5
2
< 2
4. O problema das torres de Hanoi consiste em transladar n discos de diaˆmetros diferentes
de uma torre A a uma torre C usando uma torre auxiliar B. Os discos esta˜o inicialmente
organizados na torre, A, decrescentemente, segundo o diaˆmetro e devem terminar na
torre C com a mesma organizac¸a˜o. Os discos sa˜o movidos de uma torre a outra com a
restric¸a˜o de que jamais se teˆm discos de diaˆmetro maior acima de discos de diaˆmetro
menor numa mesma torre. Ademais, em um movimento na˜o podem ser transladados
varios discos simultaneamente e somente e´ permitido mover discos no tope das torres.
A soluc¸a˜o t´ıpica do problema, veja figura 1, consiste em:
• transladar recursivamente os n− 1 discos de menor diaˆmetro, da torre A a` torre
B, usando como torre auxiliar a torre C;
• mover o disco de maior diaˆmetro de A a C;
• Transladar recursivamente os n− 1 discos de B a C, usando como torre auxiliar
A.
Seja M(n) o nu´mero de movimentos necessa´rios para transladar n discos segundo o
algoritmo anterior.
(a) Explique porque a seguinte relac¸a˜o de recurreˆncia expressa o nu´mero correto de
movimentos:
M(n) =
{
1, caso n = 1
2 M(n− 1) + 1, caso n > 1
(b) Calcule M(n).
3
Torre A Torre B Torre C
Situac¸a˜o inicial
recursa˜o A → B
recursa˜o B → C
A → C
Figura 1: Torres de Hanoi
Algoritmos de Ordenac¸a˜o
Implementac¸o˜es na linguagem C dos algoritmos maxsort, bubblesort, insertionsort, binary-
insertionsort, quicksort, mergesort e heapsort podem-se achar na pa´gina
http://www.mat.unb.br/∼ayala/LECTURES/AA/AA.html no arquivo “sorting.c”.
5. Analise a complexidade, nu´mero de comparac¸o˜es, do algoritmo binary-insertionsort
(i.e., insertionsort modificado, de maneira que a inserc¸a˜o e´ realizada por meio de busca
bina´ria).
6. Demonstre formalmente que qualquer algoritmo de fusa˜o de listas faz ao menos cinco
comparac¸o˜es, para fusionar duas listas ordenadas de comprimentos quatro e dois.
Note que o nu´mero de poss´ıveis formas do merge de listas ordenadas a1, a2, a3, a4 e b1, b2
e´ quinze. Verifique isto observando que cada uma das chaves b1 e b2 pode-se inserir na
lista das a’s de cinco formas diferentes, mas estas restritas mutuamente. Veja a Figura
2.
Assim, segundo o limite inferior de otimizac¸a˜o, poder´ıamos ter algoritmos de no mı´nimo
dlog2(15)e = 4 comparac¸o˜es. Tem-se, enta˜o, que descrever um “pior caso” que precisa
ao menos de cinco comparac¸o˜es.
7. Segundo o limite inferior de otimizac¸a˜o para algoritmos de ordenac¸a˜o por comparac¸a˜o
de chaves (i.e., dlog2(n!)e, onde n e´ o comprimento da lista) examinada na aula, uma
lista de comprimento treˆs ordena-se otimamente com dlog2(6)e = 3 comparac¸o˜es. As-
sim, que os algoritmos maxsort, bubblesort, insertionsort, binary-insertionsort, quick-
4
a1 a2 a3 a4
b1 b2
Figura 2: Fusa˜o de listas ordenadas: inserc¸a˜o restrita
sort, mergesort e heapsort sa˜o o´timos para listas de comprimento treˆs, pois no pior caso
fazem treˆs comparac¸o˜es (verifique!). Listas de comprimento quatro poderiam, enta˜o,
ordenar-se com dlog2(24)e = 5 comparac¸o˜es. Note que, por exemplo, os algoritmos
maxsort, bubblesort, insertionsort e quicksort fazem seis comparac¸o˜es (em tanto que
o algoritmo heapsort faz sete comparac¸o˜es) no pior caso. Neste caso, os algoritmos
mergesort e binary-insertionsort sa˜o o´timos (verifique!). Uma simples modificac¸a˜o do
algoritmo heapsort1 precisa seis comparac¸o˜es.
Agora, para listas de comprimento cinco temos um limite de otimizac¸a˜o dlog2(120)e =
7. Verifique que os algoritmos bubblesort, insertionsort e quicksort fazem dez com-
parac¸o˜es (em tanto que o algoritmo heapsort faz doze comparac¸o˜es) e os algoritmos
mergesort e binary-insertionsort oito comprac¸o˜es, no pior caso. Com uma simples mod-
ificac¸a˜o do algoritmo heapsort podem-se atingir dez comparac¸o˜es no pior caso.
Pode-se desenhar um algoritmo de ordenac¸a˜o para listas de comprimento cinco que
precise no ma´ximo de sete comparac¸o˜es?
8. No ano de 1974 (A. H. Aho, J. E. Hopcroft and J. D. Ullman, The Design and Analysis
of Computer Algorithms. Addisson-Wesley, 1974) os melhores algoritmos conhecidos,
baseados em comparac¸a˜o de chaves, para ordenar listas de comprimento n realizabam
um nu´mero de comparac¸o˜es segundo a tabela embaixo.
comprimento 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
comparac¸o˜es 0 1 3 5 7 10 13 16 19 22 26 30 34 38 42 46 50
Utilizando os recursos e me´todos computacionais atualmente dispon´ıveisa tabela pode-
ria ser aumentada. Esquematize me´todos algor´ıtmicos que baseados estrutura das
poss´ıveis a´rvores de decisa˜o associadas com algoritmos de ordenac¸a˜o para um nu´mero
fixo de chaves, descrevam os melhores algoritmos de ordenac¸a˜o.
Conhecimento de tais algoritmos e´ relevante para refinar os me´todos gerais mais pop-
ulares. P.ex., o mergesort pode ser aprimorado modificando o mecanismo de escape
do processo recursivo de forma tal que sublistas de comprimento igual que 5 sejam
ordenadas com somente sete comparac¸o˜es, como na tabela, e na˜o com oito. Ana´lise
1Para listas de comprimento quatro a construc¸a˜o do heap precisa quatro comparac¸o˜es e a ordenac¸a˜o so´
dois, se para o primeiro fixheap usa-se toda a informac¸a˜o dispon´ıvel, i.e., a chave a inserir e´ menor que o
filho esquerdo da estrutura do heap.
5
p.ex. as vantagens, quando utilizamos mergesort assim aprimorado para ordenar uma
lista de tamanho 5× 2k.
9. Os algoritmos de ordenac¸a˜o examinados na aula sa˜o desenhados pensando no caso de
listas sem repetic¸o˜es de chaves (ou com poucas repetic¸o˜es). Para listas com repetic¸o˜es
nossos algoritmos sa˜o corretos, mas na˜o aproveitam a ocorreˆncia de repetic¸o˜es.
(a) Descreva o trabalho no pior caso (W (n)) para os algoritmos insertionsort, quick-
sort e mergesort de listas de 0’s e 1’s.
(b) Desenhe um algoritmo “eficiente” baseado em comparac¸a˜o e intercaˆmbio de chaves
(na˜o use contadores extra!) para ordenar listas de 0’s e 1’s. Calcule o W (n) de
seu algoritmo.
(c) (The Dutch National Flag Problem). Cada uma das n chaves de uma lista pode ser
vermelha, branca ou azul. Apresente um algoritmo “eficiente” para ordenar este
tipo de listas segundo a ordem vermelha < branca < azul. As u´nicas operac¸o˜es
permitidas sa˜o comparac¸a˜o e intercaˆmbio de chaves (na˜o use contadores extra!).
Existe uma soluc¸a˜o Θ(n).
10. Explique em detalhe e ana´lise a complexidade tempo espac¸o dos algoritmos de or-
denac¸a˜o Shellsort, Countingsort, Radixsort e Bucketsort na bibliografia da disciplina.
6
Ana´lise de Algoritmos
Primeira Lista de Exerc´ıcios
Fundamentos
1.
fA(n) 1 seg. 1 min. 1 hora 1 dia 1 meˆs 1 ano 1 se´culo
ln(n) e10
6
e6 10
7
e3.6 10
9
e8.64 10
10
e2.592 10
12
e3.1104 10
13
e3.1104 10
15
√
n 1012 3.6 1015 3.62 1019 8.642 1020 2.5922 1024 3.11042 1026 3.11042 1030
n ln(n) 87847 3.9501 106 1.8890 108 3.9117 109 1.0217 1011 1.1210 1012 9.6591 1013
n3 102 601/3102 3.61/3103 86.41/3103 2.5921/3104 31.1041/3104 3.11041/3105
fA(n) 1 seg. 1 min. 1 hora 1 dia 1 meˆs 1 ano 1 se´culo
n2 109/2
√
6 105
√
3.6 106
√
86.4 106
√
25.92 107
√
3.1104 108
√
3.1104 109
n3 103 601/3103 3.61/3104 86.41/3104 2.5921/3105 31.1041/3105 3.11041/3106
2n 30 36 42 46 51 55 61
n! 12 13 15 16 17 18 20
2. (a) Para a = 3, b = 2 e f(n) = n2 tem-se que n2 = f(n) ∈ Ω(nlog2 3+ǫ), onde
ǫ ≈ 0.4. Observe que 3f(n/2) = 3n2/4 ≤ cn2, onde c = 7/8. Portanto, pelo
item 3 do Teorema Master, T (n) ∈ Θ(n2).
(b) Observe que em cada chamada recursiva temos um custo adicional de 1. Ana-
lisando a a´rvore recursiva de T (n) nota-se uma a´rvore bina´ria de altura n− 1
onde em cada n´ıvel i existem 2i no´s, cada um rotulado com o valor 1. Portanto,
T (n) =
n−1∑
i=0
2i = 2n − 1 ∈ Θ(2n)
Obs: a prova por induc¸a˜o de que T (n) ∈ Θ(2n) na˜o e´ necessa´ria neste caso
porque a soluc¸a˜o do somato´rio representando T (n) foi feita diretamente. Ela
pode ser feita mostrando que c12
n ≤ T (n) ≤ c22n− 1, para constantes c1 e c2.
(c) Para a = 2, b = 2 e f(n) = n tem-se que n ∈ Θ(n) (reflexividade). Portanto,
pelo item 2 do TM, T (n) ∈ Θ(n lg(n)).
(d) Para a = 3, b = 2 e f(n) = n ln(n) tem-se que nlg 3 = n1.5+ǫ0 , onde 0 <
ǫ0 < 0.085. Observe que n
1.5 = n1/2n e que limn→∞ n
1/2
ln(n)
= ∞. Logo, f(n) ∈
O(nlg 3− ǫ0). Portanto, pelo item 1 do TM, T (n) ∈ Θ(nlg 3).
(e) A adic¸a˜o de 5 na˜o deve ser relevante para n suficientemente grande. Pode-se
enta˜o usar a a´rvore recursiva para a resoluc¸a˜o de T ′(n) = 3T ′(n/3) + n/2 e
provar por induc¸a˜o se a soluca˜o e´ um limite apropriado para T (n). Logo
T ′(n) =
log3(n)−1∑
i=0
3i
n
3i2
+ 3log3(n)Θ(1)
=
log3(n)−1∑
i=0
n
2
+ nΘ(1)
=
1
2
n log3(n) + Θ(n)
1
Por induc¸a˜o tem-se que
T (n) = 3T
(n
3
+ 5
)
+
n
2
≥ 3c1
(n
3
+ 5
)
log3
(n
3
+ 5
)
+
n
2
(HI)
> 3c1
n
3
log3
(n
3
)
+
n
2
(monot.)
= c1n(log3(n)− 1) +
n
2
= c1n log3(n) + n
( 1
2
− c1
)
≥ c1n log3(n), para c1 ≤
1
2
Portanto, T (n) ∈ Ω(n log3(n)).
(f) Analisando a a´rvore recursiva de T (n) e supondo que n = 2m tem-se que
T (n) =
lg(n)−1∑
i=0
2i
n
2i
1
ln(n/2i)
+ 2lg(n)Θ(1)
=
lg(n)−1∑
i=0
n
ln(n/2i)
+ nΘ(1)
= n
lg(n)−1∑
i=0
1
ln(n/2i)
+ Θ(n)
= n
lg(n)∑
i=1
1
ln(2i)
+ Θ(n)
=
n
ln(2)
lg(n)∑
i=1
1
i
+ Θ(n)
≤ n
ln(2)
(
lg(lg(n)) + 1
)
+ Θ(n)
∈ Θ(n lg(lg(n)))
(g) Pela a´rvore recursiva tem-se que
T (n) =
n−2∑
i=0
1
n− i + Θ(1)
=
n∑
i=2
1
i
+ Θ(1)
≤ lg(n) + Θ(1) ∗
∈ Θ(lg(n))
* Observe que de
∑n
i=1
1
i
≤ lg(n) + 1 obtem-se a desigualdade acima.
2
(h) Pela a´rvore recursiva de T (n) tem-se que
T (n) =
n−2∑
i=0
ln(n− i) + Θ(1)
=
n∑
i=2
ln(i) + Θ(1)
≥
∫ n
1
ln(i)di+Θ(1)
= n ln(n)− n+ 1 + Θ(1)
= (ln(n)− 1)n+Θ(1)
∈ Θ(n ln(n))
(i) Seja S(m) = T (2m) = 2m/2T (2m/2) + 2m. Enta˜o S(m) = 2m/2S(m/2) + 2m.
Analisando a´rvore recursiva de S(m) tem-se que
S(m) =
lg(m)∏
i=1
2m/2
i
S(m/2lg(m)) + lg(m)2m
=
lg(m)∏
i=1
2m/2
i
S(1) + lg(m)2m
= 2
Plg m
i=1 m/2
i
S(1) + lg(m)2m
= 2m
Plg m
i=1 (1/2)
i
S(1) + lg(m)2m
≤ 2mS(1) + lg(m)2m
Portanto
T (n) ≤ nT (2) + n lg(lg(n)) ∈ Θ(n lg(lg(n)))
3. (a) Para φ = (1 +
√
5)/2 e φ˜ = (1−√5)/2 tem-se que
1√
5
(
1
1− φz −
1
1− φ˜z
)
=
1√
5
φz − φ˜z
(1− φz)(1− φ˜z)
=
1√
5
(φ− φ˜)z
(1− φz)(1− φ˜z)
=
1√
5
√
5z
(1− φz)(1− φ˜z)
=
z
(1− φz)(1− φ˜z)
=
z
1− φ˜z − φz + φφ˜z2
=
z
1− z − z2
3
Por outro lado tem-se que
F(z) =
∞∑
i=0
F (i)zi
=
∞∑
i=1
F (i)zi
= z +
∞∑
i=2
F (i)zi
= z +
∞∑
i=2
(F (i− 1) + F (i− 2))zi
= z +
∞∑
i=2
F (i− 1)zi +
∞∑
i=2
F (i− 2)zi
= z + z
∞∑
i=2
F (i− 1)zi−1 + z2
∞∑
i=2
F (i− 2)zi−2
= z + z
∞∑
i=1
F (i)zi + z2
∞∑
i=0
F (i)zi
= z + zF(z) + z2F(z)
Logo,
z = F(z)− zF(z)− z2F(z) = F(z)(1− z − z2)
Portanto,
F(z) = z
1− z − z2
Consequentemente,
F(z) = 1√
5
(
1
1− φz −
1
1− φ˜z
)
(b) Para φ˜ < z < 1− φ,
∞∑
i=0
1√
5
(φi − φ˜i)zi = 1√
5
( ∞∑
i=0
(φz)i −
∞∑
i=0
(φ˜z)i
)
=
1√
5
(
1
1− φz −
1
1− φ˜z
)
= F(z)
(c) De
∑∞
i=0 F (i)z
i =
∑∞
i=0
1√
5
(φi − φ˜i)zi tem-se que F (i) = 1√
5
(φi − φ˜i), ∀i ≥ 0.
Observe que |φ˜
i|√
5
< 1√
5
< 1
2
. Portanto F (i) = φ
i√
5
, aproximado ao inteiro mais
pro´ximo.
4
(d) Para i ≥ 0,
F (i+ 2) = F (i) + F (i+ 1)
=
1√
5
(φi − φ˜i + φi+1 − φ˜i+1)
= φi
(φ+ 1)√
5
− φ˜i (φ˜+ 1)√
5
≥ φi (φ+ 1)√
5
− |φ˜|i (φ˜+ 1)√
5
Note que (1 + φ˜)/
√
5 > 0, |φ˜|i ≤ 0 e (1 + φ)/√5 > 1. Logo, se |φ˜|i (φ˜+1)√
5
≤
φi
(
(φ+1)√
5
− 1), enta˜o F (i+ 2) ≥ φi.
Observe que (φ+1)√
5
− 1 = (φ˜+1)√
5
e que |φ˜|i ≤ φi para todo i ≥ 0 (|φ˜|i → 0,
φi →∞ quando i→∞). Assim,
φi
(φ+ 1)√
5
− |φ˜|i (φ˜+ 1)√
5
≥ φi (φ+ 1)√
5
− φi
((φ+ 1)√
5
− 1
)
= φi
(e) Por (d) tem-se que, para n ≥ 2
F (n) ≥ φn−2 = 1
φ2
φn ∈ Ω(φn)
Por (c) tem-se que
F (n) =
1√
5
(φn − φ˜n) ≤ 1√
5
(φn + |φ˜n|) ∈ O(φn)
Portanto, F (n) ∈ Θ(φn).
4. (a) Para n = 1, basta mover o disco de A para C.
Para n > 1, observeque sa˜o feitos M(n − 1) movimentos para transportar
n − 1 discos de A para B, usando C como auxiliar. Um movimento do maior
disco e´ feito de A para C e depois mais M(n− 1) movimentos dos n− 1 discos
em B para C, usando A como torre auxiliar.
(b) M(n) =
∑n−1
i=0 2
i = 2
n−1
2−1 = 2
n − 1 ∈ Θ(2n).
5
Algoritmos de Ordenac¸a˜o
5.
W (n) =
n−1∑
i=1
⌊lg(i)⌋+ 1 ≤
n−1∑
i=1
lg(i) + 1
≤
∫ n
1
lg(i) + 1 di
=
1
ln(2)
∫ n
1
ln(i)di+
∫ n
1
1 di
=
1
ln(2)
(
n ln(n)− n+ 1)+ (n− 1)
= n lg(n) + n
(
1− 1
ln(2)
)
+
1
ln(2)
− 1
∈ Θ(n lg(n))
6. A seguir uma ana´lise do nu´mero de poss´ıveis soluc¸o˜es, pensando nas a´rvores de
decisa˜o associadas aos poss´ıveis algoritmos.
Assim, para a situac¸a˜o inicial a1 > a2 > a3 > a4 e b1 > b2, as poss´ıveis respostas
sa˜o 15. As a´rvores de decisa˜o com 15 folhas tera˜o no mı´nimo a altura ⌈lg 15⌉ = 4.
Existe enta˜o algum algoritmo associado a uma a´rvore de decisa˜o que precise no
pior caso de 4 comparac¸o˜es? Deve-se enta˜o analisar os passos de um algoritmo
hipote´tico.
Suponha que o primeiro passo de um algoritmo qualquer seja comparar b1 com uma
das quatro chaves a1, a2, a3 ou a4 (caso para b2 e´ ana´logo). Logo, se a primeira
comparac¸a˜o do algoritmo e´ a1 : b1 tem-se duas possibilidades: a1 < b1 e tem-se uma
lista ordenada de 5 elementos e uma pendeˆncia (o elemento b2) ou a1 > b1 com uma
lista ordenada de 3 elementos e 3 pendeˆncias. No primeiro sub-caso, as poss´ıveis
respostas sera˜o 5 e no segundo sub-caso sera˜o 10. Portanto, no pior caso tem-se
uma sub-a´rvore de decisa˜o com altura ⌈lg 10⌉ = 4. Consequentemente, tem-se uma
total para o pior caso de 5 comparac¸o˜es (no mı´nimo).
Os casos de algoritmos que realizem como primeira comparac¸a˜o a2 : b1, a3 : b1
e a4 : b1 sa˜o analisados similarmente e em todos eles tem-se pelo menos mais 4
comparac¸o˜es no pior caso.
Novamente, algoritmos que escolhem b2 para primeira comparac¸a˜o sa˜o ana´logos.
7. Para a otimizac¸a˜o do algoritmo de busca bina´ria para listas de comprimento 5
(Figura 1), a, b, c, d e e por exemplo, elementos isolados sa˜o inserido em listas
unita´rias obtendo a < b, c < d, e. Observe que desse ponto a inserc¸a˜o do elemento
isolado e em uma das duas listas de comprimento 2 na˜o e´ conveniente porque seria
melhor fazer uma inserc¸a˜o bina´ria em uma lista de tamanho 3, pois ambos tem
2 comparac¸o˜es no pior caso. Assim, as duas maiores chaves das duas listas de
tamanho 2 sa˜o comparadas, obtendo a estrutura qua´drupla ilustrada no terceiro
6
passo da Figura 1. Note que esse passo resume-se a uma inserc¸a˜o bina´ria em uma
lista unita´ria. A chave isolada e pode enta˜o ser inserida em uma lista de tamanho
3, obtendo-se o resultado ilustrado no quarto passo da figura ou um resultado mais
simples, onde a chave e e´ maior que a maior chave do quarteto. Finalmente, no
quinto passo, a chave pendente e´ inserida binariamente em uma lista de tamanho
2 ou 3. Observe que nos u´ltimos dois passo a busca bina´ria e´ usada de maneira
o´tima.
e
Binary insertion
e
e
db
a c
b
a
d
c
1. 2.
3.
4. 5.
Binary insertion
Figure 1: Ordenac¸a˜o com merge sort otimizado para listas de comprimento 5
8. Como descrito no enunciado, a ide´ia ba´sica por tra´s dos me´todos de otimizac¸a˜o dos
algoritmos de ordenac¸a˜o e´ utilizar-se de um mecanismo de escape na recursividade
de tal forma que o algortimo o´timo para uma entrada de tamanho espec´ıfico seja
chamado, evitando comparac¸o˜es desnecessa´rias.
Para o exemplo do merge otimizado tem-se
T (5 2k) =
k−1∑
i=0
2ic
n
2i
+ 7 2k = (5ck + 7)2k
enquanto o algoritmo sem otimizac¸a˜o teria uma custo de (5ck + 8)2k. Portanto, o
algoritmo otimizado faria 2k comparac¸o˜es a menos que o algoritmo usual.
9. (a) Insertion Sort
Para o insertion sort, o pior caso acontece quando tem-se zeros no fim da
lista, equivalendo a uma lista ordenada na ordem inversa (que e´ o pior caso
do algoritimo). Portanto, para uma lista de comprimento n com n/2 zeros no
7
fim da lista tem-se que
W (n) = (
n
2
− 1) + n
2
+
n∑
i=n/2+1
n
2
+ 1
= n− 1 +
n/2−1∑
i=1
n
2
+ 1
= n− 1 + n
2
− 1 +
(n
2
− 1
)n
2
=
n2
4
+ n− 2 ∈ Θ(n2)
Merge Sort
A comparac¸a˜o feita pelo merge sort usando < na˜o aproveita a informac¸a˜o de
quando duas chaves sa˜o iguais. O pior caso seria quando a lista tem 0’s e
1’s intercalados por toda lista. Assim, para cada iterac¸a˜o com uma lista de
comprimento n ter´ıam-se 3n/4 comparac¸o˜es e, para n = 2, W (2) = T (2) = 1.
Logo,
W (n) =
lg(n)−1∑
i=0
2i
3
4
n
2i
+ 2lg(n)−1
=
lg(n)−1∑
i=0
3
4
n +
n
2
=
3
4
n lg(n) +
n
2
∈ Θ(n lg(n))
Quick Sort
O pior caso, como para uma lista sem entradas repetidas, seria tal que o pro-
blema original de tamanho n seja dividido em um subproblema de tamanho
n − 1 e outro de tamanho 0. Uma lista com apenas 0’s ou 1’s teria esse
comportamento. Assim, W (n) =
∑n−1
i=1 (n− i) =
∑n−1
i=1 i =
1
2
(n+1)n ∈ Θ(n2).
(b) ENTRADA: lista L com 0’s e 1’s de tamanho n
SAI´DA: L com todos os 0’s, caso haja algum, nas primeiras posic¸o˜es.
BEGIN
zero=1;
FOR (i=1,i<=n,i++)
{
IF (L[i] == 0)
{
EXCHANGE L[i] <-> L[zero];
8
zero++;
}
}
END.
O pior caso sera´ o de uma lista com apenas 0’s. Assim, para um custo constante
c de troca de chaves,
W (n) =
n∑
i=1
1 + 1 + c = (2 + c)n = Θ(n)
(c) ENTRADA: lista L com chaves “vermelha”, “branca” e “azul” de tamanho n
SAI´DA: L ordenada por “vermelha”’s < “branca”’s < “azul”’s.
BEGIN
vermelho=1, azul=n ;
FOR (i=1,i<=azul,i++)
{
IF (L[i] == "vermelho")
{
EXCHANGE L[i] <-> L[vermelho];
vermelho++;
}
ELSE IF (L[i] == "azul")
{
EXCHANGE L[i] <-> L[azul];
azul--;
i--;
}
}
END.
Observe que o pior caso sera´ com uma lista com apenas “azul”, pois ter´ıamos
3 comparac¸o˜es e uma troca de chaves desnecessa´ria a cada iterac¸a˜o. Com um
9
custo constante c para troca de chaves tem-se
W (n) =
n∑
i=1
3 + c = (3 + c)n = Θ(n)
10. Exerc´ıcio de leitura (Verifique na Bibliografia o cap´ıtulo de [Baa88] sobre Sorting).
10
	lista1_20080326
	gabaritoL1