Lista de exercicio 4 - Cormen 2º Edição

Prévia do material em texto

Aluno: Vinícius Barcelos Silva 
Matricula: 108251 
 
4.1­1 (para esse exercício temos que [ ] representará o limite superior) 
Substituindo na expressão temos que  . Assumindo para [n/2], teremos que:(n)  lg(n )T ≤ c − b  
(n)   lg([n/2  b])  1T ≤ c −   +    
          c lg(n/2 )<   − b + 1 + 1  
           lg( )= c 2n−2b+2 + 1  
           lg(n b )  lg2= c − 2 + 2 − c + 1  
           lg(n )≤ c − b  
   
No ultimo passo temos que necessariamente ter   .   e c b ≥ 2 ≥ 1  
 
4.2­3 (para esse exercício temos que [ ] representará o limite inferior) 
 
cn (1) 
 
cn/2 cn/2 cn/2 cn/2 (2) 
 
cn/4 cn/4  cn/4  cn/4 (3) 
 
(1) cn 
(2) 2cn 
(3) 4cn 
 
O total do somatório vai ser: 
(n)  cn  cn(2 )  cn(2n ) cn  O(n )T =   ∑
lg n
i=0
2i =   1+lg n − 1 =   − 1 = 2cn2 −   =   2  
 
 
4.3­1 
i)   T(n) = 4T(n/2) + n 
Usando o teorema mestre, a = 4, b = 2  e f(n) = n teremos  . Teremos que  n²n log  ab  =    
. Isso significa que  .(n) (n  ) se e  1f = O 2−e =   (n)  Θ(n²)T =    
 
ii)  T(n) = 4T(n/2) + n² 
Aqui teremos a = 4, b = 2 e f(n) = n² teremos  . Teremos apenas uma opção nesse  n²n log  ab  =    
caso,  , isso significa que teremos  .(n)  Θ(n²)f =   (n)  Θ(n² lg n)T =    
 
iii) T(n) = 4T(n/2) + n³ 
Tendo a = 4, b = 2 e f(n) = n³ teremos  . Agora teremos  n²n log  ab  =    
será verdade para c = ½. Logo,(n) (n  ) se e , se 4f(n/2) f(n), isto é, se 4(n/2)³ n³f = Ω 2 + e = 1   ≤ c     ≤ c  
.(n)  Θ(n³)T =