Exercícios
Análise de algoritmos &
Ordenação
Eduardo Laber
Cap 2- Tardos
Exercício 3
f2 < f3 < f6 < f1 <f4 <f5
Cap 2- Tardos
Exercício 4
g3 < g4 < g1 < g5 < g2 < g7 < g6
Cap 2- Tardos
Exercício 5
a) Verdadeiro, assumindo g(n)>=1.
log f(n) <= log (c.g(n)) <=
log c + log g(n) <= d log g(n) para d > log c
a) Falso. f(n)=4n2 e g(n)=n2
b) Verdadeiro. f(n)2 <= c2 g(n) 2 < d.g(n) 2 para
d>c.
Cap 2- Tardos
Exercício 6
a) O(n3)
b) Para mostrar (n3), considere i variando de 1
a n/4 e j variando de n/4 a n
c) For i=1,2,...,n do
B[i,i]A[i]
For i=1,2,...,n
For j=i+1,i+2,...,n
B[i,j] B[i,j-1]+A[j]
O(n2)
Cap 2- Tardos
Exercício 8
• Enquanto o primeiro vazo não quebra,
jogar de alturas n0.5, 2n0.5,…, n0.5 n0.5
• Se ele quebrar ao jogar de altura i.n0.5
– Jogar de alturas (i-1)n0.5 , (i-1)n0.5 +1 , (i-1)n0.5
+2, … até ele quebrar
• Total de passo <= 2n0.5
Exercícios Extras
• Escreva o pseudo-código da operacão de
remover o elemento A[i] de um heap
armazenado em um vetor A[1..n]
Exercício
• Projete um algoritmo para fazer um merge
de k listas ordenadas que execute em O(n
log k), aonde n é o total de elementos nas
k listas
Solução
• Seja L(1),...,L(k) as k listas
• Remova o primeiro elemento de cada lista
e construa um heap com eles: O(k)
• Para i=1,...,n
– Remova o menor elemento do heap e insira
na lista ordenada. Assuma que este elemento
veio da lista j; O(log k)
– Remova o primeiro elemento da lista L(j) e
insira no heap. O(log k)
Exercício
• Mostre como ordenar n inteiros no
intervalo [1,n2] em tempo linear O(n)
Solução
• Solução
– Crie vetores B e C com n posições, indexadas de 0 a
n-1. Cada posição pode armazenar uma lista de
inteiros
– Percorra o vetor A inserindo A[i] na lista B[i mod n].
– Para i variando de 0 a n-1
• Para cada elemento x da lista B[i] faça
Insira x no final da lista C[ x div n]
Para i variando de 0 até n-1
• Para cada elemento x da lista C[i] faça
Imprima [x]
Exercício
• A) Mostre que para fazer o merge de duas
listas com n elementos é necesário
realizar pelo menos 2n-1 comparações no
pior caso.
• B) Mostre que para fazer o merge de duas
listas, uma com n elementos e outra com
m elementos, é necesário realizar pelo
menos comparações  mn  n  no pior caso.


Solução
• Considere as duas listas A= a(1)< ... <
a(n) e B=b(1) < ... < b(n) de n elementos
• Seja X a ordem
a(1)<b(1)<a(2)<b(2) <...<a(n)<b(n)
• Seja Y(j), j=1,...,n, a ordem idêntica a
ordem X, exceto pelo fato que a(j) > b(j)
• Seja Z(j), j=2,..,n, a ordem idêntica a
ordem X, exceto pelo fato que a(j) < b(j-1)
Solução
• Se o algoritmo não comparar a(j) com b(j)
ele não tem como diferenciar X de Y(j)
• Se o algoritmo não comparar a(j) com b(j1) ele não tem como diferenciar X de Z(j)
• Logo são necessárias 2n-1 comparações
Exercício
• Perdido em uma terra muito distante, você se encontra
em frente a um muro de comprimento infinito para os
dois lados (esquerda e direita). Em meio a uma
escuridão total, você carrega um lampião que lhe
possibilita ver apenas a porção do muro que se encontra
exatamente à sua frente (o campo de visão que o
lampião lhe proporciona equivale exatamente ao
tamanho de um passo seu). Existe uma porta no muro
que você deseja atravessar. Supondo que a mesma
esteja a n passos de sua posição inicial (não se sabe se
à direita ou à esquerda), elabore um algoritmo para
caminhar ao longo do muro que encontre a porta em
O(n) passos. Considere que n é um valor desconhecido
(informação pertencente à instância). Considere que a
ação composta por dar um passo e verificar a posição
do muro correspondente custa O(1).
Solução
p=0
Enquanto não encontrar o muro
Ande até a posição 2p. Se encontrar o muro no caminho
pare
Ande até a posição -2p. Se encontrar o muro pare
p++
Fim Enquanto
Assuma que a porta esta na posição + n. Seja p* tal que
2p*-1<n<=2p*
O algoritmo anda no máximo 3 2p*+1 +4 .2p*+1 para encontrar
o muro. Esse valor é menor que 14 n.
Exercício
Analise a complexidade do algoritmo abaixo
Leia(n);
x0
Para i  1 até n faça
Para j  i+1 até n faça
Para k  1 até j-i faça
x x + 1
Exercício
• Projete o algoritmo mais eficiente que
você conseguir para encontrar a mediana
de um vetor de n elementos. Análise sua
complexidade.
Solução
• Ordene os elementos e retorne o
elemento n/2 da lista ordenada
– Complexidade: O(n log n)
• Mais adiante no curso mostraremos um
algoritmo O(n)
Exercício
Dizemos que um vetor P[1..m] ocorre em
um vetor T[1..n]
se P[1..m] = T[s+1..s+m] para algum s.
O valor de um tal s é um deslocamento
válido.
Projete um algoritmo para encontrar todos
os deslocamentos válidos de um vetor e
analise sua complexidade.
Exercício
Seja A[1..n] um vetor que pode conter
números positivos e negativos.
Projete um algoritmo com complexidade
O(n3) determinar os índices i e j, com i<=j,
tal que A[i] + ...+A[j] é máximo. Tente
reduzir a complexidade para O(n2), depois
para O(n log n) e então para O(n)
Exercício
Resolvas as equações abaixo encontrando
uma função f(n) tal que T(n) = (f(n))
a)
b)
c)
d)
T(n)=2.T(n/2) + n2 para n>1; T(1)=1
T(n) = 2.T(n/2) + n, para n>1; T(1)=1
T(n)=T(n/2) + 1, para n>1; T(1)=1
T(n)=T(n/2) + n, para n>1; T(1)=1
Exercício
Seja uma matriz quadrada A com n2 números
inteiros que satisfaz as segintes propriedades
(i) A[i,j] <= A[i+1,j] para 1<=i<=n-1 e 1<=j<=n
(ii) A[i,j]<=A[i,j+1], para 1<=i<=n e 1<=j<=n-1
a) Dado um elemento x, descreva um
procedimento eficiente para determinar se x
pertence a A ou não. Analise a complexidade
do algoritmo proposto.
b) Mostre que este problema é (n)
Solução
a) Considere o procedimento abaixo
Seja y o elemento do canto superior direito da
matriz. Compara y e x
• Se x>y, descarte a primeira linha e aplique o
procedimento recursivamente para matriz
restante.
• Se x<y, descarte a última coluna e aplique o
procedimento recursivamente para matriz
restante.
• Se x=y devolva a posição de y
Solução
Análise
• A cada passo o número de linhas ou de
colunas da matriz diminui de 1, portanto
o algoritmo executa no máximo 2n
passos.
Solução
Lower Bound
• Considere a seguinte entrada matriz:
A[i,j] =0 se i+j<n+1,
A[i,j] =n+1 se i+j>n+1
A[i,j] é um inteiro entre 1 e n se i+j=n+1
• Se x é um número entre 1 e n que não
pertence a A, qualquer algoritmo tem que
examinar todas as entradas A[i,j], com i+j=n+1
para concluir que x não esta em A. Logo, o
problema é (n)
Exercício
Seja A={a(1) < .... < a(n)} uma lista de
números reais. A proximidade entre a(i) e
a(j) é definida como |a(i)-a(j)|.
a) Dados os inteiros j e k, encontre os k
elementos de A mais próximos de A[j] em
O(k).
Exercício
Seja A[1..n] um vetor com n números
positivos e seja S[i]=A[1]+...+A[i].
•
Encontre o índice i que minimiza
Minimiza | S[i] – (A[i+1] + ... +A[n]) |
Exercício
Mostre que
n
i
i 1
k
 (n
k 1
)
Solução
n
i
k
 nn  O(n
k
k 1
)
i 1
k 1


n
n
 
k
k 1


i  n / 2    k 1   (n )

2 2 
i n / 2
n
k