Exercícios de Fixação 01 - Conceitos Fundamentais - Parte II - Gabarito

Prévia do material em texto

ANÁLISE DE ALGORITMOS
Bacharelado em Ciência da Computação
Lista de Exercícios de Fixação 01
Conceitos Fundamentais – Parte II
Observação: se não especificado na questão, considere a complexidade computacional assintótica para o
pior caso.
1. Considere o algoritmo, a seguir, e responda às questões seguintes.
algoritmo(n)
entrada: Um inteiro não-negativo
T ← 0
for i ← 1 to n do
T ← T + i*i*i*i
return T
a. O que o algoritmo calcula?
∑ i 4
b. Qual é a operação básica que ele realiza?
Multiplicação
c. O número de vezes que a operação básica é realizada depende somente do tamanho da entrada?
Explique.
Sim, pois o algoritmo possui um laço cujas instruções são executadas n vezes.
d. Quantas vezes a operação básica é executada? Dica: estabeleça um somatório ou uma relação de
recorrência para indicar o número de vezes que a operação básica é executada e resolva-o(a). 
F (n)=3 [n−1+1]=3n
e. Qual é a classe de eficiência do algoritmo? Represente a classe utilizando a notação assintótica
adequada.
(n), afinal não há situações de pior ou melhor casos.
2. Encontre a T(n) e, em seguida, determine a complexidade assintótica do seguinte trecho de
programa.
1
 ANÁLISE DE ALGORITMOS
Bacharelado em Ciência da Computação
for (i = 0; i < n; i++) { 
//sequência de instruções
} 
for (j = 0; j <= n; j++) { 
//sequência de instruções
} 
T(n) = n + (n + 1) = 2n + 1 → (n)
3. Calcule a T(n) e determine a complexidade assintótica do pior caso para o seguinte código.
Sugestão de solução: para os laços, seguem as considerações.
i → 1 a 2 → (2 – 1 + 1) = 2 iterações
j → i a n → (n – i + 1) iterações
k → i a j → (j – i + 1) iterações
Portanto, tem-se para o laço mais interno, o seguinte somatório:
∑
j=i
n
( j−i+1)=(i−i+1)+(i+1−i+1)+⋯+(n−i+1)
1+2+⋯+(n−i+1)=(1+(n−i+1))(n−i+1)
2
=
(n−i+2)(n−i+1)
2
Logo, para o segundo laço, temos o seguinte somatório:
∑
i=1
2 (n−i+2)(n−i+1)
2
=1
2∑i=1
2
(n−i+2)(n−i+1)=(n−1+2)(n−1+1)+(n−2+2)(n−2+1)
1
2
[(n+1)n+n (n−1)]=1
2
[n(n+1+n−1)]=1
2
[n(2n)]= 2n ²
2
=n ²
Portanto, a complexidade assintótica do pior caso, para o algoritmo, é O(n2).
4. Determine a complexidade assintótica para o seguinte código. 
Dica: ∑
i=1
n
i2=1²+...(n)²=n(n+1)(2n+1)
6
2
 ANÁLISE DE ALGORITMOS
Bacharelado em Ciência da Computação
soma = 0;
for (int k = 0; k < n; k++)
soma++;
for (int i = 0; i < n; i++)
for (int j = 0; j < i*i; j++)
soma++;
Sugestão de solução: para o primeiro laço, tem-se que k → 0 a n – 1 → (n – 1) – 0 + 1 = n iterações.
Portanto, o tempo de execução do primeiro loop é O(n). 
No loop duplamente aninhado, o número de iterações do laço mais interno, em função de i, é i2. Veja:
i → 0 a n-1 = (n-1) – 0 + 1 = n iterações. Para o laço mais interno, temos que j → 0 a i2 – 1 → (i2 – 1) – 0 + 1
= i2. 
Portanto, o tempo de execução dessa parte é ∑
i=0
n−1
i2=0²+1²+...(n−1) ²=n (n−1)(2n−1)
6
que é O(n3).
Assim, O(n) + (n3) = O(max(n, n3)) = O(n3).
5. Calcule a T(n) e determine a complexidade assintótica do pior caso para o seguinte código.
T(n) = n3 + T(2n/3) = T(2n/3) + O(n3), usando o Teorema Mestre, considera-se que a = 1, b = 3/2 e d = 3.
Sendo assim, temos log ab
=log 1
3/2
=0<d=3. Portanto, T(n) é O(nd) = O(n3).
6. Sabendo que T(1) = 1, encontre a ordem de complexidade das relações abaixo usando o
Teorema Mestre, caso aplicável.
a. T(n) = 4T(n/4) + 2n
3
 ANÁLISE DE ALGORITMOS
Bacharelado em Ciência da Computação
Sugestão de solução: Uma vez que T(n) = 4T(n/4) + O(n1), tem-se a = 4, b = 4 e d = 1. Sendo
assim, log ab
=log 4
4
=1=d=1. Portanto, T(n) é O(ndlgn) → O(nlgn).
b. F(n) = F(n – 1) + n para todo n ≥ 2
Sugestão de solução: Neste caso, não se pode aplicar o Teorema Mestre. Sendo assim, aplicando
a expansão telescópica, temos que:
F(n) = F(n – 1) + n
 = F(n – 2) + (n – 1) + n
 = F(n – 3) + (n – 2) + (n – 1) + n
 ⁝
 = F(n – k) + … + (n – 2) + (n – 1) + n
Uma vez que T(1) = 1, pode-se determinar a condição de parada da recorrência quando n – k
= 1 → k = n – 1. Substituindo k = n – 1 em F(n), temos: 
F(n) = F(n – (n – 1)) + … + (n – 2) + (n – 1) + n
 = F(1) + … + (n – 2) + (n – 1) + n = 1 + … + (n – 2) + (n – 1) + n = (1 + n)(n)/2 → O(n2).
7. Considere a função definida pela recorrência: 
f(n) = 2f(n-1), f(0) = 1 
O professor Pardau afirma que f(n) = O(n), e que isso pode ser verificado simplesmente da forma
f(n) = 2f(n-1) = 2O(n-1) = O(n)
Sendo assim, pergunta-se: o professor Pardau está certo? Justifique.
Sugestão de solução: Para provar que fn = O(n) temos que provar que existe um c tal que fn ≤ cn a partir um
ponto n0. É importante que a constante c seja a mesma para todo n. Na verificação do professor Pardau, a
constante c muda implicitamente, e por isso ela não é válida. Em adição, aplicando a expansão telescópica,
temos que:
f(n) = 2f(n – 1)
 = 2(2f(n-2)) = 4f(n-2) = 22f(n-2)
 = 4(2f(n-3)) = 8f(n-3) = 23f(n-2)
 ⁝
 = 2kf(n-k)
Uma vez que f(0) = 1, pode-se determinar a condição de parada da recorrência quando n – k = 0 → k = n.
Substituindo k = n em f(n), temos: 
f(n) = 2nf(n – n) = 2nf(0) = 2n → O(2n).
4
 ANÁLISE DE ALGORITMOS
Bacharelado em Ciência da Computação
8. Responda o que se pede.
a. A recorrência T(n) = 7T(n/2) + n2 descreve o tempo de execução do algoritmo da Alice. Um
algoritmo alternativo proposto por Bob tem um tempo de execução T(n) = aT(n/4) + n 2. Qual é o
maior número inteiro a que faz com que o algoritmo do Bob seja assintoticamente mais rápido
que o algoritmo da Alice? Justifique.
Sugestão de solução: a = 4, pois log 44
<log 7
2
.
b. O Teorema Mestre pode ser aplicado à recorrência T(n) = 4T(n/2) + n2lgn? Justifique a resposta. 
Sim, tendo complexidade O(n2lgn). 
Sugestão de solução: não, pois n2lng é O(n2lgn) – não é uma complexidade polinomial conforme a requisição
do Teorema Mestre.
c. Considere que você tenha um problema para resolver e duas opções de algoritmos. O primeiro
algoritmo é quadrático tanto no pior caso quanto no melhor caso. Já o segundo algoritmo é linear
no melhor caso e cúbico no pior caso. Considerando que o melhor caso ocorre 90% das vezes
que você executa o programa enquanto o pior caso ocorre apenas 10% das vezes, qual algoritmo
você escolheria? Justifique a sua resposta em função do tamanho da entrada.
Sugestão de solução: O segundo algoritmo, em função da probabilidade maior na execução para o melhor
caso.
9. Quando um algoritmo possui uma chamada recursiva, seu tempo de execução pode ser descrito por
uma recorrência. Utilize um dos métodos estudados para encontrar a ordem de complexidade da
recursão: T(n) = 3T(n/2) + n e T(1) = 1.
Sugestão de solução: Uma vez que T(n) = 3T(n/4) + O(n1), tem-se a = 3, b = 2 e d = 1. Sendo assim,
log a
b
=log 3
2
=1,58496>d=1. Portanto, T(n) é O( n
log a
b ) → O( n
log 3
2 ) → O(n1,58496).
10. Apresente a complexidade assintótica das seguintes relações de recorrência:
a. T(n) = T(n – 1) + (n – 1), T(1) = 0
 = T(n – 2) + (n – 2) + (n – 1)
 = …
 = T(n – k) + … (n – 2) + (n – 1) 
Uma vez que T(1) = 0, pode-se determinar a condição de parada da recorrência quando n – k = 1 → k = n –
1. Substituindo k = n – 1 em T(n), temos:
5
 ANÁLISE DE ALGORITMOS
Bacharelado em Ciência da Computação
T(n) = T(n – (n – 1)) + … + (n – 2) + (n – 1) 
= T(1) + … + (n – 2) + (n – 1) 
= 0 + … + (n – 2) + (n – 1) 
= (0 + (n-1))n/2 → (n – 1)n/2, portanto O(n2).
b. T(n) = T(n-1) + n, T(1) = 1
 = T(n-2) + n-1 + n
 = T(n-3) + n-2 + n-1 + n
 = …
 = T(n-k) + … + n-1 + n
Uma vez que T(1) = 1, pode-se determinar a condição de parada da recorrência quando n – k = 1 → k = n –
1.Substituindo k = n – 1 em T(n), temos:
 T(n) = T(n – (n – 1)) + … + n-1 + n
 = T(1) + … + n-1 + n
 = 1 + 2 + … + n-1 + n = (1 + n)n/2 → O(n2)
c. T(n) = 8T(n/2) + n2, T(1) = 1
Sugestão de solução: Uma vez que T(n) = 8T(n/2) + O(n2), tem-se a = 8, b = 2 e d = 2. Sendo assim,
log a
b
=log 8
2
=3>d=2. Portanto, T(n) é O( n
log a
b ) → O(n3).
d. T(n) = 2T(N/2) + N, para N ≥ 2 e T(1) = 0
Sugestão de solução: Uma vez que T(N) = 2T(N/2) + O(N1), tem-se a = 2, b = 2 e d = 1. Sendo assim,
log a
b
=log 2
2
=1=d=1. Portanto, T(N) é O(Ndlgn) → O(nlgn).
e. T(N) = 2T(N-1) + 1, para N≥ 2 e T(1) = 1
 = 2(2T(N-2) + 1) + 1 = 4T(N-2) + 2 + 1 = 4T(N-2) + 3 = 22T(N-2) + 22 - 1 
 = 4(2T(N-3) + 1) + 3 = 8T(N-3) + 4 + 3 = 8T(N-3) + 7 = 23T(N-3) + 23 - 1 
 = …
 = 2kT(N-k) + … + 2k – 1
Uma vez que T(1) = 1, pode-se determinar a condição de parada da recorrência quando N – k = 1 → k = n –
1. Substituindo k = n – 1 em T(N), temos:
6
 ANÁLISE DE ALGORITMOS
Bacharelado em Ciência da Computação
T(N) = 2N-1T(N-(N-1)) + 2N-1 – 1
= 2N-1T(1) + 2N-1 – 1
= 2*2N-1 – 1 → 2N – 1 → O(2N)
f. T(n) = 2T(n/2) + (n – 1), T(1) = 1
Sugestão de solução: Uma vez que T(n) = 2T(n/2) + O(n), tem-se a = 2, b = 2 e d = 1. Sendo assim,
log a
b
=log 2
2
=1=d=1. Portanto, T(n) é O(ndlgn) → O(nlgn).
11. Considere o algoritmo, a seguir. Suponha que a operação crucial é o fato de inspecionar um
elemento. O algoritmo inspeciona os n elementos de um conjunto e, de alguma forma, isso permite
descartar a metade dos elementos e então fazer uma chamada recursiva sobre os n/2 elementos
restantes. 
void pesquisa(int n){
if (n <= 1)
inspecione elemento e termine
else{
para cada um dos n elementos, inspecione elemento;
pesquisa(n/2);
 }
}
a. Escreva uma relação de recorrência que descreve esse comportamento;
T (n)={ 1, se n⩽1n+T (n/2), caso contrário}
b. Apresente a complexidade computacional do algoritmo para o melhor e o pior caso.
Sugestão de solução: Uma vez que T(n) = T(n/2) + O(n), tem-se a = 1, b = 2 e d = 1. Sendo assim,
log a
b
=log 1
2
=0<d=1. Portanto, T(n) é O(nd) → O(n). Para o melhor caso, têm-se Ω(1).
12. Considere o algoritmo, a seguir, e responda o que se pede, fornecendo justificativas.
algoritmo segredo(n)
entrada: Um número natural n.
saída: não revelada.
7
 ANÁLISE DE ALGORITMOS
Bacharelado em Ciência da Computação
 se n = 1 entao 
devolva 1
 senao 
devolva segredo(piso(n/2)) + 1
 fimse
fimalgoritmo
a. Seja s : N → Z≥, a função que descreve o tempo de execução do algoritmo segredo em função do
valor de n. Então, defina a relação de recorrência que descreve o valor s(n).
s (n)={ 1, sen=1s(n/2)+c , casocontrário}
b. Resolva a recorrência que você definiu em b.
Sugestão de solução: Podemos considerar que s(n) = s(n/2) + O(1) → s(n/2) + O(n 0), tem-se que a = 1, b = 2
e d = 0. Sendo assim, log ab
=log 1
2
=0=d=0. Portanto, s(n) é O(ndlgn) → O(n0lgn) → O(lgn).
13. Elabore um algoritmo para determinar se um inteiro positivo, n, é primo. Determine a complexidade
computacional assintótica do algoritmo.
Sugestão de solução: Um número n > 1 é composto se e somente se ele tem um divisor menor ou igual a
√n . Isso é óbvio, uma vez que n é composto se e somente se ele pode ser escrito como um produto n =
porque, onde p, q > 1. Portanto, p ou q deve ser menor ou igual a √n , caso contrário esse produto
excederia n.
Segue um trecho de código em Java baseado nessa ideia.
result = true; 
if (n == 1)
result = false;
else
r = (int)sqrt((double)n);
for (int i = 2; i <= r; i++)
if (n % i == 2){
8
 ANÁLISE DE ALGORITMOS
Bacharelado em Ciência da Computação
result = false;
break;
}
if (result)
System.out.println(n + “é primo!”);
A complexidade assintótica do código é O( √n ).
9
	Lista de Exercícios de Fixação 01