Exercicios de Fixação 01 - Conceitos Fundamentais - Parte I - 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 I
1. Um algoritmo é executado em 10 segundos para uma entrada de tamanho 50. Se o algoritmo
é quadrático, quanto tempo em segundos ele gastaria, aproximadamente, no mesmo
computador, se a entrada tiver tamanho 100? 
Sugestão de solução: Para o algoritmo quadrático (n2) e para n = 50 e t = 10s, tem-se (50 * 50)/10 =
250 elementos/s. Portanto, podemos efetuar a seguinte consideração:
250 elementos/s = (100 * 100)/t para encontrar quanto tempo a máquina gastaria para processar n =
100. Sendo assim, temos que 25t = 1000 → t = 40s
2. Considere o algoritmo a seguir e responda as perguntas que seguem, fornecendo
justificativas:
algoritmo enigma(n, ref A)
entrada: um número natural n e uma referência para o vetor A com n valores reais
saída: não revelada
   para i de 1 a n­1 faca
      k   i←
      para j de i+1 a n faca
       se (A[j] < A[i]) entao
k   j←
fimse
 fimpara
      troca(A[k], A[i])
   fimpara
fimalgoritmo
a. Supondo que a função troca() faz a troca de valores de seus 2 argumentos, o que o
algoritmo enigma faz?
Sugestão de solução: O algoritmo enigma tenta ordenar o vetor A em ordem crescente.
b. Caracterize as instâncias de pior caso do algoritmo.
Sugestão de solução: A situação de pior caso do algoritmo enigma compreende um vetor
1
 ANÁLISE DE ALGORITMOS
Bacharelado em Ciência da Computação
de elementos distintos dois a dois e ordenado em ordem decrescente. Nesse caso, o teste
A[j] < A[k] sempre resultará no valor lógico verdadeiro e a linha que atribui j a k sempre
será executada. Como as demais linhas do algoritmo são sempre executadas, o número
máximo de operações primitivas ocorre no caso descrito (pior caso).
3. Um problema algorítmico está definido quando estabelecemos os seguintes três aspectos: o
conjunto de entradas; o conjunto de saídas válidas; e, finalmente, a relação entre cada
entrada e suas correspondentes saídas válidas. Todos os demais aspectos são irrelevantes,
pois as medidas de eficiência O,  e  não dependem de constantes multiplicativas
associadas ao artefato computacional. É correta tal afirmação? Justifique.
Sugestão de solução: Sim, pois as notações O,  e  são ditas assintóticas sendo aplicadas
para determinar a complexidade computacional de um algoritmo, com base em n ‘muito
grande’ e desconsiderando constantes (por sua vez independentes do tamanho da entrada). 
4. É verdade que ½n2 é O(n)? Justifique.
Sugestão de solução: Não. A notação O é indicada para denotar o limite superior de uma
função. No caso, ½n2 é O(n2), uma vez que para se dizer que f(n) é O(g(n)), tem-se que obter
f(n) ≤ cg(n) para alguma constante real c > 0 e n ≥ n0. Se consideramos c = ½ e n0 = 1,
podemos afirmar que ½n2 é O(n2). Observe:
½ n2 ≤ cn2 → ½ n2 ≤ ½ n2 → ½ 12 ≤ ½12. Portanto, ½n2 é O(n2).
5. Ordene as funções, a seguir, por sua taxa assintótica de crescimento.
4nlgn + 2n 210 2lgn
3n + 100nlgn 4n 2n
n2 + 10n n3 nlgn
Sugestão de solução: 210 < 2lgn < 4n < nlgn < 4nlgn + 2n < 3n + 100nlgn < n2 + 10n < n3 < 2n
6. Qual das seguintes afirmações sobre crescimento assintótico de funções não é verdadeira?
a) 2n2 + 3n + 1 é O(n2)
b) Se f(n) é O(g(n)) então g(n) é O(f(n))
c) lgn2 é O(lgn)
2
 ANÁLISE DE ALGORITMOS
Bacharelado em Ciência da Computação
d) Se f(n) é O(g(n)) e g(n) é O(h(n)) então f(n) é O(h(n))
e) 2n+ 1 é O(2n)
7. Critique a afirmação 'n2 – 100n está O(n2) para todo n ≥100'.
Sugestão de solução: A afirmação é verdadeira, pois basta considerar c = 1 que n2 – 100n ≤ cn2 será
satisfeita. Observe que se n2 – 100n ≤ cn2, para c = 1 e n0 = 100, tem-se que (100)2 – 100*100 ≤
1*(100)2 → (100)2 – (100)2 ≤ (100)2 → 0 ≤ (100)2. Portanto, n2 – 100n é O(n2).
8. Mostre que lgn não está em (n).
Sugestão de solução: Basta lembrar que  é a notação assintótica utilizada para denotar o limite
inferior de uma função. Sendo assim, afirma-se que f(n) é (g(n)) se f(n) ≥ c(g(n)), para c > 0 e n ≥
n0. Para f(n) = lgn, temos que o seu limite inferior é lgn, uma vez que se dado c = 1 e n0 = 2, temos
que lgn ≥ clgn → lg2 ≥ 1*lg2 → 1 ≥ 1. Portanto, lgn é (lgn).
9. Mostre que n(n + 1)/2 e n(n – 1)/2 estão em (n2).
Sugestão de solução: Para ambas as funções, precisamos considerar que f(n) é (g(n)) se f(n) é
O(g(n)) e f(n) é (g(n)), ou seja, cg(n) ≤ f(n) ≤ dg(n) para c, d > 0 e n suficientemente grande (n ≥
n0). Sendo assim, para n(n+1)/2, basta considerar c = 1/2, d = 2/2 = 1 e n0 ≥ 1, para satisfazer a
equação. 
cn2 ≤ n(n+1)/2 ≤ dn2 → 1/2*(1)2 ≤ n(n+1)/2 ≤ 1(1)2 → 0,5 ≤ 1 ≤ 1. Portanto, n(n+1)/2 é (n2).
Para n(n-1)/2 a ideia é similar (tarefa para você!).
10. Quais das seguintes igualdades são verdadeiras?
I. n2 = o(n3)
II. 2n + 1 = o(n2)
III. n3 = o(n2)
IV. 3n + 5nlgn = o(n)
V. lgn + n1/2= o(n)
a) somente I e II
b) somente II, III e IV
3
 ANÁLISE DE ALGORITMOS
Bacharelado em Ciência da Computação
c) somente III, IV e V
d) somente I, II e V
e) somente I, III e IV
11. Sejam duas funções f(n) que mapeiam números inteiros positivos em números reais
positivos. Com respeito às notações assintóticas de complexidade, avalie as afirmações a
seguir.
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) ≤ cg(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) < cg(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) ≥ cg(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 n0
≥ 1 tal que f(n) > cg(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
12. Alice e Bob estão discutindo sobre seus algoritmos. Alice afirma que seu método de tempo
O(nlgn) é sempre mais rápido que o método de Bob de tempo O(n2). Para decidir a questão,
eles executaram um conjunto de experimentos. Para o espanto de Alice, eles encontraram
que se n < 100, o algoritmo O(n2) executa mais rápido, e somente quando n ≥ 100 é o
4
 ANÁLISE DE ALGORITMOS
Bacharelado em Ciência da Computação
algoritmo O(nlgn) é um pouco melhor. Explique como isso é possível.
Sugestão de solução: Isso é possível em virtude da definição da própria notação assintótica que,
usada para determinar a complexidade computacional de uma função, a caracteriza para n
suficientemente grande. Sendo assim, não são relevantes os valores pequenos de n (tamanho da
entrada), no caso se n < 100, O(nlgn) representa um tempo de execução pior que O(n2).
13. Suponha que dois algoritmos, A e B, resolvem o mesmo problema, para um tamanho de
instâncias dado por n. Em quais dos seguintes casos podemos afirmar que A é mais rápido
que B? Justifique. 
a) Caso 1: A consome tempo O(lgn) no pior caso e B consome tempo O(n3) no pior caso;
b) Caso 2: A consome O(nlgn) unidades de tempo no pior caso e B consome (n2) unidades
de tempo pior caso;
c) Caso 3: No pior caso, A consome O(n2) unidades de tempo e B consome (n2lgn)
unidades de tempo.
Sugestão de solução: Para n suficientemente grande, podemos considerar que o algoritmo A é mais
rápido que B em todos os casos. Observe que lgn < nlgn < n2 < n2lgn< n3, para n suficientemente
grande!
14. Observe as funções representadas no gráfico, a seguir.
5
 ANÁLISE DE ALGORITMOS
Bacharelado em Ciência da Computação
Indique a alternativa falsa sobre o crescimento assintótico dessas funções:
a) f(n) = O(h(n)) e i(n) = (g(n))
b) f(n) = (h(n)) e i(n) = (h(n))
c) g(n) = O(i(n)) e h(n) = (g(n))
d) g(n) = O(i(n)), i(n) = O(f(n)) e, portanto, g(n) = O(f(n))
e) h(n) = (i(n)), logo, i(n) = O(h(n))
15. Considere dois algoritmos A1 e A2, cujas funções de custo são, respectivamente, T1(n) = n2 –
n + 1 e T2(n) = 6nlgn + 2n. Para simplificar a análise, assuma que n > 0 é sempre uma
potência de 2. Com relação ao enunciado, indique a alternativa correta. 
a) Como T1(n) = (n2) e T2(n) = (nlgn), então A2 é sempre mais eficiente que A1
b) O limite superior T1(n) = O(n3) é correto assintoticamente restrito
c) O limite inferior T2(n) = (n3) é correto e assintoticamente restrito
d) T1 e T2 são assintoticamente equivalentes
e) A1 é mais eficiente que A2, para n suficientemente pequeno
16. Sejam T1(n) = 100n + 15, T2(n) = 10n2 + 2n e T3(n) = 0,5n3 + n2 + 3 as equações que
descrevem a complexidade de tempo dos algoritmos Alg1, Alg2 e Alg3, respectivamente,
para entradas de tamanho n. A respeito da ordem de complexidade desses algoritmos, pode-
se concluir que
a) as complexidades assintóticas estão, respectivamente, em O(n), O(n2) e O(n3)
b) as complexidades assintóticas estão, respectivamente, em O(n), O(n2) e O(n2)
c) as complexidades assintóticas estão, respectivamente, em O(100), O(10) e O(0,5)
d) Alg2 e Alg3 pertencem as mesmas classes de complexidade assintótica
e) Alg1 e Alg2 pertencem as mesmas classes de complexidade assintótica
6
 ANÁLISE DE ALGORITMOS
Bacharelado em Ciência da Computação
17. Em relação ao limite assintótico de notação O, atribua V (verdadeiro) ou F (falso) às
afirmativas a seguir.
( ) Em uma estrutura de laço duplamente aninhado, tem-se imediatamente um limite
superior O(n2)
( ) Em uma estrutura de laço duplamente aninhado, o custo de cada iteração do laço interno
é de limite superior O(1)
( ) Em uma estrutura de laço triplamente aninhado, o custo de cada iteração do laço interno
é de limite superior O(n3)
( ) O limite O(n2) para o tempo de execução do pior caso de execução aplica-se para
qualquer entrada
( ) f(n) = O(g(n)) é uma afirmação de que algum múltiplo constante de g(n) é de limite
assintótico inferior
Indique a alternativa que contém, de cima para baixo, a sequência correta.
a) V, V, F, V, F
b) V, F, V, F, V
c) F, V, V, F, F
d) F, F, V, V, F
e) F, F, F, V, V
18. Considere o problema de encontrar o maior e o menor elemento de um vetor de inteiros
A[1..n], n > 0. O algoritmo simples para resolver este problema pode ser derivado do
Programa, a seguir.
Programa – Implementação direta para obter o máximo e o mínimo de um conjunto
procedure MaxMin1 (var A: Vetor; var Max, Min: integer);
var i: integer;
begin
Max := A[1]
7
 ANÁLISE DE ALGORITMOS
Bacharelado em Ciência da Computação
Min := A[1]
for i := 2 to n do
begin
if A[i] > Max then Max := A[i];
if A[i] < Min then Min := A[i];
end;
end.
Seja f uma função de complexidade tal que f(n) é número de comparações entre os elementos de A,
se A contiver n elementos. Portanto, f(n) = 2(n-1), para n>0.
Faça a análise de complexidade para o melhor caso, pior caso e caso médio do programa
apresentado.
Sugestão de solução: para esse programa, não há situações de pior, melhor ou médio casos, uma vez
que o laço é sempre executa e é o que mais onera em termos de quantidade de passos executados.
Sendo assim, f(n) = 2(n-1) representa o número de passos do trecho de código ‘dominante’, para
fins de complexidade computacional, do programa.
19. Bill dispõe de um algoritmo, encontre2D, para encontrar um elemento x em um arranjo Anxn.
O algoritmo encontre2D itera sobre as linhas de A e chama o algoritmo encontreArray, do
trecho de código abaixo, para cada linha, até que x seja encontrado ou todas as linhas de A
tenham sido pesquisadas.
algoritmo encontreArray(x, A): 
Entrada: Um elemento x e um arranjo A com n elementos 
Saída: O índice i tal que x = A[i], ou ­1 se nenhum elemento de A é igual a x 
i = 0; 
enquanto i < n faça 
se x = A[i] então 
retorna i
senão i = i + 1
retorna ­1 
Qual o tempo para o pior caso de encontre2D em termos de n? Qual o tempo para o pior caso de
encontre2D em termos de N, onde N é o tamanho total de A? É correto dizer que encontre2D é um
algoritmo de tempo linear? Justifique.
8
 ANÁLISE DE ALGORITMOS
Bacharelado em Ciência da Computação
Sugestão de solução: No pior caso, o algoritmo encontre2D (que invoca encontreArray para cada
linha de Anxn), em termos de n é O(n2) – no pior caso, para cada uma das n linhas, as n colunas são
visitadas). Se N é o tamanho total de A, então o pior caso é representado por O(N). Não é correto
dizer que encontre2D é linear pois N = n * n = n2 – a entrada do algoritmo é, na verdade, expressa
por n * n elementos a serem visitados.
20. Considere o código, a seguir.
void ordena (int n, int* v){
int i,j;
for (i=n­1; i>=1; i­­)
          for (j=0; j<i; j++)
            if (v[j]>v[j+1]){ /*troca*/
int temp = v[j];
v[j] = v[j+1];
v[j+1] = temp;
}
}
Apresente a análise da complexidade de tempo para o melhor, pior e médio caso. Especifique, para
tanto, o que caracteriza cada caso. 
Sugestão de solução: o pior caso se estabelece quando a entrada está em ordem descrescente de
valores, pois assim, todas as trocas serão efetuadas. No melhor caso, a entrada já está em ordem
crescente não sendo necessária qualquer troca de valores. Observem que estas afirmações dizem
respeito à quantidade de passos especificamente. De um modo geral, para todos os valores de
entrada, os laços aninhados dominam a complexidade do código. Sendo assim, podemos observar
que:
laço i → n-1 a 1 → executado (n – 1) vezes
laço j → 0 a i-1 → executado i vezes, daí temos:
∑
i=n−1
1
i=(n−1)+…+1=((n−1)+1)(n−1)
2
=
(n(n−1))
2
Aplicando as propriedades da notação assintótica, podemos considerar que independentemente dos
valores de entrada, os laços interno e externo são sempre executados. Sendo assim, o código é
O(n2), Ω(n2) e Θ(n2), para n suficientemente grande.
9
	Lista de Exercícios de Fixação 01