PAA - Unidade 1 (1)

Prévia do material em texto

● RESPOSTAS: 
a) .2 (n) .2 (n), ∀n0 ≤ c1
n ≤ 2n+1 ≤ c2
n ≥ k  
0 .2≤ c1
n ≤ 2n+1  
0 ≤ c1 ≤ 2
n
2n+1
 
0 ≤ c1 ≤ 2
n
2 .2n  
0 ≤ c1 ≤ 2
1  
 
.22n+1 ≤ c2
n  
2n
2n+1 ≤ c2  
2 ≤ c2  
, c 2, 1c1 = 2
1 2 = k =  
 é Θ( ), para 22n 2n , c 2, 1c1 = 2
1 2 = k =   
b) .2 , ∀n0 ≤ 22n ≤ c n ≥ k  
, ∀n0 ≤ 2n
2 .2n n ≤ c ≥ k  
, ∀n0 ≤ 2n ≤ c ≥ k  
não é O( ), já que c é constante e n pode receber números arbitrariamente grande, então22n     2n                            
essa relação não pode ser satisfeita 
 
c) .x , ∀x0 ≤ 7x2 ≤ c 3 ≥ k  
, ∀x0 ≤ x3
7x2 ≤ c ≥ k  
, ∀x0 ≤ 7x ≤ c ≥ k  
k = 1 e c = 7 
 ​é O( ) para k = 1 e c = 77x2 x3  
 
d) ​ .7x , ∀x0 ≤ x3 ≤ c 2 ≥ k  
.7x , ∀x0 ≤ x3 ≤ c 2 ≥ k  
, ∀x0 ≤ x3
7x2
≤ c ≥ k  
, ∀x0 ≤ 7
x ≤ c ≥ k  
​não é O( ), já que c é constante e x pode receber números arbitrariamente grande,x3       7x2                          
então essa relação não pode ser satisfeita 
 
e) ​Para que seja o( ), é necessário que f(x) seja      (x) 0x 10.Log x 5f = 2 3 + +     g(x) x= 3            
insignificante em relação a g(x) quando x está próximo do infinito, logo precisamos que                           
= 0 lim
x→∞ x
3
20x3 + x3
10Log x + 5x3  
Quando x se aproxima do infinito temos que e tendem a zero, mas tende a 20,                x3
10Log x   5x3         x3
20x3      
∴ não é o( ).0x 10.Log x 52 3 + + x3  
 
f) ​ n .5, ∀n0 ≤ 2 ≤ c ≥ k  
2n não é O(5) já que c é constante e n pode receber numros arbitrariamente grande e isso                                   
impossibilita a relação. 
 
g) Seja f(x) = 270 e g(x) = e para que f(x) seja o(g(x)), é necessário que f(x) seja                x3                      
insignificante em relação a g(x) quando x está próximo do infinito, logo precisamos que                           
= ​0.lim
x→∞ x
3
270  
Quando x se aproxima do infinito temos que tende a zero, logo podemos afirmar que                x3
270                
270 é o( ) x3  
 
h) ​ .Log(x) c.x , ∀ x k0 ≤ x ≤ 2 ≥  
 c, ∀ x k0 ≤ .x2
x.Log(x) ≤ ≥  
 c, ∀ x k0 ≤ x 
Log(x) ≤ ≥  
Com isso podemos dizer que é O( ), já que x pode receber números          .Log(x)x     x2              
arbitrariamente grande e isso fará com que tenta a zero, logo a relação pode ser            x 
Log(x)                
satisfeita para c = 1 e k =2 
 
i) Seja f(x) = e g(x) = e para que f(x) seja o(g(x)), é necessário que f(x) seja        0. 1 √2 log(x)
 
      √x                      
insignificante em relação a g(x) quando x está próximo do infinito, logo precisamos que                           
= ​0.lim
x→∞ √x
10. √2 log(x)
 
 
Aplicando a propriedade dos logaritmos em f(x), temos: balog ba = (x) 10.f = √x  
Portanto temos = ​10 e com isto a relação não se satisfaz e não é o(    lim
x→∞ √x
10.√x                       0. 1 √2 log(x)
 
   
). √x  
 
j) ​ .Log(x) c.x , ∀ x k0 ≤ x2 ≤ 2 ≥  
 c, ∀ x k0 ≤ x2
x .Log(x)2 ≤ ≥  
Log(x) c, ∀ x k0 ≤ . ≤ ≥  
Como c é constante e x pode receber números arbitrariamente grande, então essa relação não                             
pode ser satisfeita. Desta forma não é O( ).Log(x)x2 x2  
 
k) 000 2.x , ∀ x k0 ≤ c.x2 ≤ 1 + 2 ≥  
 , ∀ x k0 ≤ c ≤ x2
1000 + x2
2.x2 ≥  
 , ∀ x k0 ≤ c ≤ x2
1000 + 2 ≥  
Para k =1 e c= 1002, a relação se satisfaz e é Ω( )000 2.x1 + 2 x2  
 
 
l) Seja f(x) = e g(x) = e para que f(x) sejaω(g(x)), é necessário que f(x) seja        og(x )l 2       og(x)l                      
arbitrariamente grande em relação a g(x) quando x está próximo do infinito, logo precisamos                           
que = ​∞.lim
x→∞ log(x)
log(x )2
 
lim
x→∞ log(x)
log(x )2
⇒ lim
x→∞ log(x)
2.log(x ) = 2  
Como o limite de é 2, então a relação não se satisfaz e f(x) é não ω(g(x)).f (x)g(x)  
 
m) ​ .4 .n .4 , ∀n0 ≤ c1
log(n) ≤ 2 2 ≤ c2
log(n) ≥ k  
.2 .n .2 , ∀n0 ≤ c1
2log(n) ≤ 2 2 ≤ c2
2log(n) ≥ k  
.(2 ) .n .(2 ) , ∀n0 ≤ c1
log(n) 2 ≤ 2 2 ≤ c2
log(n) 2 ≥ k  
.n .n .n , ∀n0 ≤ c1 2
 ≤ 2 2 ≤ c2 2 ≥ k  
 
Para k =1 e c= 2, a relação se satisfaz e é Θ( ).n2 2 4log(n)  
 
n) ​ .2 , ∀n0 ≤ c n ≤ 22n+1 ≥ k  
, ∀n0 ≤ c ≤ 2n
2 .2 .2n n ≥ k  
, ∀n0 ≤ c ≤ 2n+1 ≥ k  
Para k =1 e c= 1, a relação se satisfaz e​ é Ω( ).22n+! 2n  
 
o) .2 , ∀n0 ≤ 22n+1 ≤ c n ≥ k  
, ∀n0 ≤ 2n
2 .2 .2n n ≤ c ≥ k  
, ∀n0 ≤ 2n+1 ≤ c ≥ k  
​já que c é constante e n pode receber números arbitrariamente grande, não é O(2 )22n+1 n                          
então essa relação não pode ser satisfeita 
p) n .5, ∀n0 ≤ 2 ≤ c ≥ k  
2n não é O(5) já que c é constante e n pode receber números arbitrariamente grande e isso                                   
impossibilita a relação. 
 
q) ​ .n , 2n ∀n0 ≤ c ≤ n
1
log(n) + ≥ k  
, /n ∀n0 ≤ c ≤ n
1
log(n) + n
2n ≥ k  
.n , 2 ∀n0 ≤ c ≤ n
n
1
log(n) + ≥ k  
Como n pode receber números arbitrariamente grande, tenderá a zero, logo temos que              n
n
1
log(n)
             
ter c 2 e k > 1.≥  
Logo é Ω( ) para c =2 e k =22nn
1
log(n) + x  
 
r) ​ = n
1
log(n) 2 2nLog (2)x = Log (x)x =  
.8 .8, ∀n0 ≤ c1 ≤ n
1
log(n) ≤ c2 ≥ k  
.8 .8, ∀n0 ≤ c1 ≤ 2 ≤ c2 ≥ k  
Desta forma temos que ter , e k 1.c1 1/4≤ 1/4c2 ≥ ≥  
Logo é Θ( ) para , e k = 1n
1
log(n) 8 c1 1/4= 1/4c2 =  
 
Questão 2: Determine a complexidade no tempo do algoritmo abaixo que promete encontrar                         
os elementos mínimo e máximo do vetor de entrada V de tamanho n e responda os itens a                                   
seguir. Todas as respostas devem ser devidamente justificadas. 
a) Podemos dizer que o algoritmo MaxMin para e é correto? 
● RESPOSTA: 
Sim, o algoritmos percorre todo o vetor para verificar se há um elemento menor que min ou                                 
maior que max. 
b)Existe melhor e pior caso? 
● RESPOSTA: 
Não, o algoritmo percorre o todo vetor independente a dos parâmetros recebidos. 
c) O algoritmo MaxMin é eficiente? 
● RESPOSTA: 
Sim, já que o algoritmos executa a sua tarefa corretamente e possui complexidade Θ(n). 
Questão 3: Usando notação assintótica, descreva a complexidade no tempo do algoritmo                       
abaixo. Ele recebe dois vetores A e V de tamanhos n e w, respectivamente. 
● RESPOSTA: 
TESTE(A, V, n, w) 
1. para i = 1 até n faça n+1 
2. para j = 1 até w faça n(w+1) 
3. V[j] = A[i] + 2 n.w 
4. max = V[1] 1 
5. para j = 2 até w faça w+1 
6. se max < V[j] então max = V[j] 1 
T(n,w) = n+1 + n.w + n + n.w +1 + w+1 +1 
T(n,w) = 2.n.w + 2.n + w + 4 
2.n.w + 2.n + w + 4 é Θ(n.w) 
 
 
Questão 4: Considerando f ≡ f(n), g ≡ g(n) e k uma constante, determine se as sentenças                                 
abaixo são verdadeiras ou falsas. Caso sejam falsas reescreva corretamente.  
a) Falsa. max(f(n); g(n)) = O(g(n) + f(n)) 
b) Verdadeira 
c) Verdadeira 
d) Falsa. n 8n 100.n O(n )5 + 2 + 3 = 3  
 
Questão 5: ​Assumindo que cada expressão representa o tempo de processamento de um                         
algoritmo para resolver um problema de tamanho n. Selecione o termo dominante e                         
especifique a complexidade no pior caso. 
Expressão  Termo Dominante  O(. . .) 
 0.001n 0.025n5 + 3 +   n3   O( )n3  
 50n(log (n))500n 100n+ 1.5 + 10
3   n1.5   O( )n1.5  
 
Questão 6: 
Como f( n ) ≤ f( n ) + g( n ) e ​g( n ) ≤ f( n ) + g( n ), então max ( f( n ) , g( n ) )∈ O ( f( n                                                                               
) + g( n ​) ) 
Também temos que f(n)+g(n) ≤ 2max(f(n), g(n)) max(f(n),g(n)) ∈ Ω(f(n)+g(n)) 
Portanto, temos que max ( f( n ) , g( n ) ) ∈ ​Θ​ ( f( n ) + g( n ) ) 
 
 
Questão 7: ​Um algoritmo quadrático com tempo de processamento T(n) = consome                      cn2    
T(n) segundos para processar N itens. Assumindo N = 100 e T(N) = 1ms, quanto tempo este                                 
algoritmo consome para processar uma entrada de cinco mil itens? 
RESPOSTA: 
1ms = c.100²c = 1/10000 
T(n) = n
2
10000  
T(n) = 5000
2
10000  
T(n) = = 2500ms
104
25.106  
Questão 8: Os algoritmos A e B, para uma entrada de tamanho n, consomem exatamente                             
microssegundos. Informe qual algoritmo apresenta a melhor 0.1n .log(n) e T .5nT a = 2 b = 2 2                
complexidade no pior caso e encontre o valor k tal que para qualquer n > k o algoritmo                                   
5n 2.5n0.3n + 1.5 + 1.75   n1.75   O( )n1.75  
log(n) + n2 n(log(n))2   log(n)n2   O( )log(n)n2  
 + log (n)n 3 log (n)n 2   log (n)n 2   O( )log (n)n 2  
 + .log (n)3 8 og (log (log (n)))l 2 2 2   og (n)l 8   O( )og (n)l 8  
100n 0.01n+ 2   n2   O( )n2  
0.01n 100n+ 2   n2   O( )n2  
 0.5n2n n+ 0.5 + 1.25   n1.25   O( )n1.25  
.01n.log (n) n.(log (n))0 2 + 2
2   .(log (n))n 2
2   O( ).(log (n))n 2
2  
100 .(log (n)) n 100nn 3
 + 3 +   n3   O( )n3  
 + .003.log (n)0 4 og (log (n))l 2 2   )og (nl 4   O( )og (nl 4  
informado apresente melhor desempenho. Se o problema apresenta entradas n ≤ , qual                      109    
algoritmo você recomendaria para resolver o problema? 
RESPOSTA: 
 apresenta a melhor complexidade no pior caso.5nT b = 2 2  
.1k .log(k) .5k0 2 = 2 2  
0.1k .log(k) .5k ).( 2 = 2 2 1
k2
 
.1.log(k) .50 = 2  
0.1.log(k) .5).10( = 2  
og(k) 5l = 2  
33554432k = 225 =  
Como é maior que 2 , então eu escolheria T109 25 b  
 
Questão 9: Os algoritmos A e B, para uma entrada de tamanho n, consomem exatamente                             
microssegundos. Qual algoritmo apresenta a melhor 5.n .log(n) e T 5nT a = b = 2              
complexidade no pior caso? Para quais tamanhos de entrada um é melhor que o outro? 
RESPOSTA: 
 apresenta a melhor complexidade no pior caso.5nT b = 2  
.k .log(k) 5k5 = 2  
.log(k) 55 = 2  
og(k)l = 5  
 k = 3225 =  
é melhor que quando n > 32.T b T a  
 
Questão 10: Os algoritmos A e B, para uma entrada de tamanho n, consomem exatamente                             
microssegundos. Diga qual o melhor algoritmo para processar c .n .log(n) e TT a = a b = c nb 2                  
uma entrada de tamanho n = se o algoritmo A consome 10 microssegundos para            220                  
processar 1024 itens e o algoritmo B consome 1 microssegundo para processar a mesma                           
quantidade. 
RESPOSTA: 
0 c .1024 .log(2 )1 = a 10  
ca = 101024.10  
ca = 11024  
 .n .log(n) T a = 11024
  
----------------------------------------------------------------------------- 
1 = c 1024b
2  
 cb = 1220  
T b = n1220
2
 
----------------------------------------------------------------------------- 
 .2 .log(2 ) T a = 12 10
20 20 T b = . (2 )1220
20 2  
 .2 .20log(2 ) T a = 10
 T b = 2
20  
 .2 . 2 . 5 T a = 10
 2 T b = 2
20  
 .2 . 5 T a = 12
 
 T b = 2
20  
< T a T b  
 é o melhor algoritmo para processar uma entrada de tamanho n = T a 220