Lista 1

Prévia do material em texto

1 
 UNIVERSIDADE FEDERAL DE VIÇOSA 
 DEPARTAMENTO DE INFORMÁTICA 
 INF332 - Projeto e Análise de Algoritmos 
 Prof. José Elias C. Arroyo 
 
Lista de Exercícios 1 
Complexidade de Algoritmos, Crescimento Assintótico de Funções e Relações de Recorrência 
Data de entrega: 22 de setembro de 2014 
 
1. Determine as funções de complexidades de pior caso e de melhor caso dos seguintes algoritmos 
considerando o número de comparações envolvendo elementos das matrizes. Em seguida, obtenha o 
limite mais justo possível, isto é, descreva a complexidade utilizando a notação Θ. 
 
a) 
Enigma(A[0..n-1][0..n-1]){ 
for i := 0 to n-2 do 
for j := i+1 to n-1 do 
if (A[i][j] ≠ A[j][i]) 
return (false); 
return (true); 
} 
b) 
ProcedimentoQ(A[0..n-1][0..n-1]) { 
for i:= 0 to n-1 do { 
j := i+1; 
while (j < n and A[i][j] = 0) do 
j := j+1; 
if (j < n) return (false); 
} 
return (true); 
} 
 
2. Determine a função de complexidade de tempo de pior caso em termos de n e expresse essa complexidade 
usando a notação O. 
 
a) 
Mystery (n){ 
r := 0; 
for i:=1 to n-1 do 
for j:= i+1 to n do 
for k:= 1 to j do 
r := r + 1; 
return (r); 
} 
b) 
Pesky (n){ 
r := 0; 
for i:=1 to n do 
for j:= 1 to i do 
for k:= j to i+j do 
r := r + 1; 
return (r); 
} 
c) 
Conundrum (n){ 
r := 0; 
for i:=1 to n do 
for j:= i+1 to n do 
for k := i+j-1 to n do 
r := r + 1; 
return (r); 
} 
d) 
prestiferous (n){ 
r := 0; 
for i:=1 to n do 
for j:= 1 to i do 
for k := j to i+j do 
for t := 1 to i+j-k do 
r := r + 1; 
return (r); 
} 
 
 
3. Escreve um algoritmo para determinar a distância (diferença) entre os dois elementos mais próximos de 
um array com n números. Determine a complexidade de melhor e pior caso. 
 
 2 
4. Faça um algoritmo para verificar se uma sequência A de m caracteres está contida numa outra sequencia B 
de n caracteres (n ≥ m). Se A está contida em B, o algoritmo deve retornar a posição inicial de A em B, 
caso contrário o valor -1. 
 
5. Sejam duas funções f(n) e g(n) que mapeiam números inteiros positivos em números reais 
positivos. 
Com respeito às notações assintóticas de complexidade, avalie as afirmativas abaixo. 
I. Diz-se que f(n) ∈ O(g(n)) se existe uma constante real c > 0 e existe uma constante 
inteira n0 ≥1 tal que f(n) ≤ c.g(n) para todo inteiro n ≥n0. 
II. Diz-se que f(n) ∈ o(g(n)) se para toda constante real c > 0 existe uma constante inteira 
n0 ≥1 tal que f(n) < c.g(n) para todo inteiro n ≥n0. 
III. Diz-se que f(n) ∈ Ω(g(n)) se existe uma constante real c > 0 e existe uma constante 
inteira n0 ≥1 tal que f(n) ≥ c.g(n) para todo inteiro n ≥n0. 
IV. Diz-se que f(n) ∈ ω(g(n)) se para toda constante real c > 0 existe uma constante 
inteira n ≥1 tal que f(n) > c.g(n) para todo inteiro n ≥n0. 
V. Diz-se que f(n) ∈ Θ(g(n)) se, e somente se, f(n) ∈O(g(n)) e f(n) ∈ (g(n)). 
A análise permite concluir que: 
a) todas as afirmativas são falsas. 
b) todas as afirmativas são verdadeiras. 
c) apenas as afirmativas I e III são verdadeiras. 
d) apenas as afirmativas II e IV são verdadeiras. 
e) apenas a afirmativa V é falsa. 
6. Para cada uma dos seguintes pares de funções f(n) e g(n), determine uma constante c >0 tal que f(n) ≤ 
c.g(n), para todo n≥1. 
a) f(n) = n2 + n + 1, g(n) = 2n3 
b) f(n) = n n + n2, g(n) = n2 
c) f(n) = n2 – n + 1, g(n) = n2/2 
7. Para cada uma dos seguintes pares de funções f(n) e g(n), determine as constantes c >0 e n0 ≥1, tal que 
f(n) ≥ c.g(n), para todo n ≥ n0. 
a) f(n) = n2 – 4n, g(n) = 4n2 
b) f(n) = n2 – n g(n) = 5n + n 
c) f(n) = 2n, g(n) = n3 + n2 
 
8. Sejam TA(n) e TB(n) os tempos de execução de pior caso de dois algoritmos A e B propostos para um 
mesmo problema computacional, em função de um certo parâmetro n. Dizemos que o algoritmo A é mais 
eficiente que o algoritmo B assintoticamente no pior caso quando: 
a) TA(n) = o(TB(n)). 
b) TB(n) = o(TA(n)). 
c) TA(n) = O(TB(n)). 
d) TB(n) = O(TA(n)). 
e) TA(n) = Θ(TB(n)). 
 
9. Diga se a afirmação é verdadeira ou falsa. Justifique sua resposta. 
a) Se f (n)∈ω(g(n)) então f (n)∈Ω(g(n)) 
b) Se f (n)∈Ω(g(n)) então f (n)∈ω(g(n)) 
c) Se f (n)∈ο(g(n)) então f (n)∈Ο(g(n)) 
d) Se f (n)∈O(g(n)) então f (n)∈ο(g(n)) 
e) Se f (n)∈Θ(g(n)) então f (n)∈Ο(g(n)) 
f) Se f (n)∈Θ(g(n)) então f (n)∈Ω(g(n)) 
g) Se f (n)∈Θ(g(n)) então f (n)∈ο(g(n)) 
 3 
h) Se f (n)∈Θ(g(n)) então f (n)∈ω(g(n)) 
i) f (n)∈ω(g(n)) se e somente se g(n)∈ο( f (n)) 
j) Se f (n)∈Ο(g(n)) e h(n)∈Ο(p(n)) então f(n) + h(n) ∈ Ο(g(n) + p(n)) 
 
 
10. Prove (utilizando a definição formal das notações assintóticas ou apresente um contraexemplo) as 
seguintes afirmações: 
a) Se f (n) ∈ Ο(g(n)) então g(n) ∈ Ω(f(n)) 
b) Θ(c.g(n)) = Θ(g(n)), onde c>0. 
 
11. Ordenar as seguintes funções de acordo com a relação de dominância ou ordem de crescimento: 
2n+1, (n – 2)!, 5 log2 (n+100)10, 1+n , 22n, 0.01nn, 0.001n4 + 3n3 + 1, (ln n)2, 3 n , 3n, 2n, log2 n2 
 
12. Usando limites infinitos, prove que: 
a) n n = o(n log2 n) 
b) log2 n = o(n) 
c) n! = O(nn) 
d) 2n = Ω(n4) 
e) 4n2 + 2n + 8 = Θ(n2) 
f) n2 = ω(n log2 n) 
 
13. Para os seguintes pares de funções, diga se f(n) = o(g(n)), f(n) = O(g(n)), f(n) = Ω(g(n)), f(n) = 
ω(g(n)), e/ou f(n) = Θ(g(n)). 
a) f(n) = n2 + n + 1, g(n) = 2n3 
b) f(n) = log n2, g(n) = log n3 + 5 
c) f(n) = n , g(n) = log n3 
d) f(n) = n, g(n) = log2 n 
e) f(n) = 2n, g(n) = 10n2 
f) f(n) = 3n, g(n) = 2n 
g) f(n) = 3710 2 ++ nn , g(n) = 8n + 2 
h) f(n) =2n-1 g(n) = 2n 
 
14. Para cada uma das funções abaixo, determine a classe Θ(g(n)) à qual a função pertence (ou seja, 
obtenha a ordem de crescimento exata): 
a) (n2 + 1)3 
b) 2n log2(n + 2)2 
c) 3710 2 ++ nn 
d) 2n+1 + 3n-1 
 
15. Encontre a ordem de crescimento das seguintes somas (use a notação Θ): 
a) ∑
=
+
n
i
i
0
22 )1( ; b) ∑
−
=
1
2
2
2log
n
i
i ; c) ∑
=
−+
n
i
ii
1
12)1( ; d) ∑∑
−
=
−
=
+
1
0
1
0
)(
n
i
i
j
ji ; e) ∑
=
+−+
n
i
iii
1
24 )2023( 
16. Considere o algoritmo a seguir. 
PROC (n){ 
se n = 1 então retorna 1 + n; 
senão 
 retorna PROC(n/2) + PROC(n/2); 
} 
 4 
Assinale a alternativa que indica corretamente quantas somas são feitas para uma entrada n > 0, 
onde n é um número natural potência de 2. 
a) n 
b) n + log2 n 
c) n log2 n + 1 
d) n2 + n − 1 
e) 2n − 1 
 
 
 
17. Calcule a complexidade de tempo dos seguintes algoritmos 
a) 
int ALGO(int n) { //considere n potencia de 2 
if (n == 1 ) return 1; 
else{ 
for(int i = 1; i<9; i++) z = ALGO(n/2); 
for(int i =1; i<= n*n*n; i++) z = z + 1; 
return z; 
} 
} 
b) 
void ASTERISCO(int n) { 
if (n > 0 ) { 
ASTERISCO(n–1); 
for (int i = n; i > 0; i--) cout<<’*’<<endl; 
ASTERISCO(n–1); 
} 
} 
 
18. Considere a versão do problema das Torres de Hanói com três pinos (A, B e C) na qual qualquer 
movimento do pino A para o pino C (ou do pino C para o pino A) tem que colocar o disco no pino B, ou 
seja, é obrigatório passar pelo pino B. Escreva um algoritmo recursivo para este problema e apresente a 
relação de recorrência para determinar o número de movimentos. Para n = 3 discos, quantos movimentos 
são realizados? 
 
19. Considere o problema das Torres de Hanói com 4 pinos (A, B, C e D). Elabore um algoritmo recursivo 
para movimentar n discos do pino A para o pino D, usando os pinos B e C como auxiliares. Calcule a 
complexidade de tempo do seu algoritmo para valores de n par e impar. Compare o seu algoritmo com o 
algoritmo de 3 pinos com relação ao número de movimentos necessários. 
 
20. Resolva as seguintes relações de recorrências, pelo método de substituição:a) T(n) = 3T(n/3) + n, para n>1, T(1) = 1 (considere n potencias de 3) 
b) T(n) = 7T(n/7) + n, para n>1, T(1) = 1 (considere n potencias de 7) 
c) T(n) = 4T(n/2) + n2 para n>1, T(1) = 1 (considere n potencias de 2) 
d) T(n) = 8T(n/2) + n3 para n>1, T(1) = 1 (considere n potencias de 2) 
 
21. Resolva as seguintes relações de recorrências utilizando a Árvore de Recursão e apresente o limite 
assintótico justo: 
a) T(n) = 2T(n-1) + n, para n>1, T(1) = 0; 
b) T(n) = 3T(n/3) + n, para n>1, T(1) = 1 (considere n potencias de 3) 
 
 5 
22. Usando o Teorema Mestre, determine a ordem de crescimento das funções definidas pelas seguintes 
relações de recorrência: 
a) T(n) = 4T(n/2) + n , para n>1, T(1) = 1 (considere n potencias de 2) 
b) T(n) = 4T(n/2) + n2, para n>1, T(1) = 1 (considere n potencias de 2) 
c) T(n) = 10T(n/3) + n2, para n>1, T(1) = 1 (considere n potencias de 3) 
d) T(n) = 8T(n/2) + n3 para n>1, T(1) = 1 (considere n potencias de 2) 
 
23. Determine a quantidade mínima e máxima de asteriscos a serem impressos pelo seguinte algoritmo. 
void ImprimeAsteriscos (int n, bool x) { 
 int i, j, k; 
 if (x) 
for( i = 1;i< n; i++) cout<<”*”; 
 else for( i = 1; i<=n; i++) 
 for( j = 1; j<=i ;j++) cout<<”*”; 
 for( i = 1; i<n; i++) 
 for( j = 1; j <= i; j++) 
 for( k = j; k>=1 ; k--) cout<<”*”; 
}