Lista 01 - Respondida

Prévia do material em texto

UNIVERSIDADE FEDERAL DE GOIÁS 
INSTITUTO DE INFORMÁTICA 
 
 
Estrutura de Dados 2 
 
Exercícios – Lista 1 
 
 
1. Suponha dois algoritmos A e B, com funções de complexidade de tempo a(n) = n2 - n 
+ 549 e b(n) = 49n + 49 respectivamente. Determine quais valores de n pertencentes 
ao conjunto de números naturais para os quais A leva menos tempo para executar 
do que B. 
n2 - n + 549 < 49n + 49, que equivale a n2 - 50n + 500 < 0. As raízes da equação 
correspondente, por Baskara: 
n = (50 +/- sqrt(502 - 4*1*500) )/2 =(50 +/- sqrt(2500-2000))/2 = (50 +/- 22.3)/2 . n1 =13.8 
e n2=36.1. Logo, a(n) < b(n) para 13 < n <37 , considerando n, números naturais. 
 
2. Encontre a função de custo para cada um dos três fragmentos de código abaixo 
considerando que a única operação a ser levada em conta é a atribuição (:=). Faça 
uma tabela, para n variando de 1 a 10, e calcule o valor das três funções de custo 
para cada caso. Faça um esboço do gráfico para cada função.Tire suas conclusões. 
sum := n^2 
sum := 0; 
para i de 1 a n faça 
 sum := sum + n; 
sum := 0; 
para i de 1 a n faça 
 para j de 1 a n faça 
 sum := sum + 1; 
 
O primeiro fragmento de código executa uma atribuição (f(n) = 1), o segundo 
executa n atribuições (f(n) = n + 1), e o terceiro executa n2 + 1 atribuições (f(n) = 
n2 +1). 
 
n 1 2 3 4 5 6 7 8 9 10 
1 1 1 1 1 1 1 1 1 1 1 
n + 1 2 3 4 5 6 7 8 9 10 11 
n2 +1 2 5 10 17 26 37 59 65 82 101 
 
 
 
Suponha que todos os três fragmentos façam a mesma coisa à variável sum. Se 
tivéssemos que escolher um fragmento com base apenas na velocidade, 
certamente escolheríamos o primeiro sobre o segundo, e o segundo sobre o 
terceiro. De acordo com nossas hipóteses simplificadas (nosso modelo), as 
atribuições são as únicas operações que importam. (Isso é falso se elevar n ao 
quadrado levar mais tempo do que fazer n adições). Neste modelo, o primeiro 
fragmento é mais barato (rápido) do que o segundo, e o segundo é mais barato 
do que o terceiro. E isso é independente do custo real de uma atribuição. Além 
do mais, existe uma grande diferença entre o primeiro e o segundo fragmento. 
Não importa o valor de n, o primeiro fragmento faz sempre uma quantidade fixa 
de trabalho. No entanto, à medida que n aumenta, o segundo fragmento leva um 
tempo proporcional a n. Assim, a relação entre o trabalho realizado pelo segundo 
fragmento sobre o trabalho realizado pelo primeiro fragmento é ilimitada. O 
segundo fragmento realiza cerca de n vezes mais trabalho do que o primeiro, e n 
pode, presumimos, tornam-se arbitrariamente grande. Além disso, a mesma 
relação é verdadeira entre o segundo e o terceiro fragmento; n2 cresce muito 
mais rápido do que n. Para ver isso, imagine se extrapolássemos os números 
para um tamanho de problema encontrado na prática. Por exemplo, se n for um 
milhão, então, n2 é um milhão de vezes maior que n. À medida que n aumenta, a 
razão entre os tempos de execução do terceiro em relação ao segundo (ou do 
segundo em relação ao primeiro) cresce sem limites. As taxas de crescimento do 
três fragmentos de código são diferentes. Pense sobre as taxas de crescimento 
em termos de mudança na quantidade de trabalho que os fragmentos tem que 
fazer quando a entrada dobra de tamanho. Se a entrada (n) dobra, o tempo de 
execução do primeiro fragmento permanece o mesmo, o tempo de execução do 
segundo fragmento dobra, e tempo de execução do terceiro fragmento 
quadruplica! Então, se para um dado programa temos que elevar n ao quadrado 
uma vez por elemento, e se o nosso modelo simplista é razoável, então devemos 
escolher o primeiro fragmento. 
 
3. Explique a diferença entre O(1) e O(2). 
 
O(1) e O(2) diferem apenas no valor da constante. Pela definição da notação O, 
isso significa que, assintoticamente falando, não há diferença entre O(1) e O(2), 
ou seja, as duas pertencem à mesma classe de complexidade. 
 
4. Indique se as afirmativas abaixo são verdadeiras ou falsas e justifique. 
a) 2n+1 = O(2n) 
b) 22n = O(2n) 
c) f(n) = O(u(n)) e g(n) = O(v(n)) => f(n) + g(n) = O(u(n) + v(n)) 
d) f(n) = O(u(n)) e g(n) = O(v(n)) => f(n) - g(n) = O(u(n) - v(n)) 
 
a) Verdadeira. Existem constante positivas c e m tais que 2(n+1) <= c.2n, para todo 
n >= m. Por exemplo, c = 3 e m = 0; 
b) Falsa. Não existem constantes positivas c e m, tais que 22n <= c.2n, para todo 
n >= m. Pois, 22n = 4n; 
c) Verdadeira. Existem constantes positivas c1, m1, c2, m2 tais que f(n) <= c1.u(n) 
qq n >=m1 e g(n) <= c2.v(n) qq n >= m2. Logo, f(n) + g(n) <= c1.u(n) + c2.v(n) para 
o maior de c1 e c2 e para o maior de m1 e m2, ou seja, f(n) + g(n) = O(u(n)) + 
O(v(n)) = O(Max(u(n), v(n)) = O(u(n) + v(n)). A adição equivale a considerar o 
máximo das duas funções. 
d) Falsa. Pois, f(n) – g(n) = O(u(n)) – O(v(n)) = O(u(n) + (-1).O(v(n)), como -1 é 
uma constante, ela pode ser desprezada. Logo, f(n) - g(n) = O(u(n)) + O(v(n)) = 
O(Max(u(n), v(n))). A notação O corresponde à relação “<=”, o que não permite 
realizar subtração nem divisão.