Exercícios sobre complexidade de algoritmos

Prévia do material em texto

18/05/2022 10:04 Exercícios sobre complexidade de algoritmos: ALGORITMOS E ESTRUTURAS DE DADOS II - Engenharia de Software - U…
https://pucminas.instructure.com/courses/91650/quizzes/288772 1/6
Exercícios sobre complexidade de algoritmos
Entrega 20 mar em 23:59 Pontos 1 Perguntas 5
Disponível 17 mar em 20:30 - 20 mar em 23:59 3 dias
Limite de tempo Nenhum
Instruções
Este teste foi travado 20 mar em 23:59.
Histórico de tentativas
Tentativa Tempo Pontuação
MAIS RECENTE Tentativa 1 4 minutos 0,8 de 1
 As respostas corretas não estão mais disponíveis.
Pontuação deste teste: 0,8 de 1
Enviado 20 mar em 16:29
Esta tentativa levou 4 minutos.
Prezados alunos,
 
Esses exercícios devem ser realizados individualmente e encerrados até o dia 20/03, às
23:59. Essa atividade tem o valor de 1 ponto.
Bons estudos!
Eveline
0 / 0,2 ptsPergunta 1IncorretaIncorreta
https://pucminas.instructure.com/courses/91650/quizzes/288772/history?version=1
18/05/2022 10:04 Exercícios sobre complexidade de algoritmos: ALGORITMOS E ESTRUTURAS DE DADOS II - Engenharia de Software - U…
https://pucminas.instructure.com/courses/91650/quizzes/288772 2/6
Considere dois vetores ordenados. Assuma ainda que cada um desses
vetores apresente n elementos. Precisa-se formar então um terceiro
vetor, correspondente à junção desses dois vetores ordenados
mencionados anteriormente. Dessa forma, esse terceiro vetor
apresentará 2n elementos, que também serão armazenados de forma
ordenada. Pode-se afirmar que a ordem de complexidade desse
processo será:
 (n )2
 (1)
 (n * log n)
 (log n)
 (n)
0,2 / 0,2 ptsPergunta 2
Um ponto importante a ser considerado no projeto de um algoritmo é a
eficiência da solução proposta. Essa eficiência tradicionalmente
relaciona o tamanho da entrada com o tempo de execução ou espaço
de memória necessários para a execução do algoritmo. Sabendo que
a função de complexidade de tempo de um algoritmo é 
, analise as afirmações abaixo sobre a
ordem de complexidade desse algoritmo: 
I. . 
II. .
III. .
É correto o que se afirma em
²
³
²
 I, apenas. 
 II, apenas. 
18/05/2022 10:04 Exercícios sobre complexidade de algoritmos: ALGORITMOS E ESTRUTURAS DE DADOS II - Engenharia de Software - U…
https://pucminas.instructure.com/courses/91650/quizzes/288772 3/6
 II e III, apenas. 
 I, II e III. 
 I e II, apenas 
I. CORRETA: Como a função de complexidade de tempo do
algoritmo é , sua ordem de
complexidade é e, consequentemente, O de qualquer
função maior que .
II. CORRETA: Como a função de complexidade de tempo do
algoritmo é , sua ordem de
complexidade é .
III. ERRADA: Como a função de complexidade de tempo do
algoritmo é , sua ordem de
complexidade é , não podendo ser da ordem de uma
função menor que . 
²
²
²
0,2 / 0,2 ptsPergunta 3
Abaixo temos um gráfico que evidencia a relação de domínio
assintótico entre diversas funções de complexidade de algoritmos.
18/05/2022 10:04 Exercícios sobre complexidade de algoritmos: ALGORITMOS E ESTRUTURAS DE DADOS II - Engenharia de Software - U…
https://pucminas.instructure.com/courses/91650/quizzes/288772 4/6
 
Analisando o gráfico apresentado, podemos afirmar que:
 
 A ordem de complexidade de f3 corresponde a O(log n).2
 A complexidade de f1 corresponde a (n ).2
 
A notação O permite comparar os limites superiores dos
comportamentos de algoritmos. Assim, podemos afirmar que um
programa O(f4) é sempre melhor que um algoritmo O(f3).
 
O limite superior do comportamento do custo de uma função de
complexidade f(n) é n quando n aproxima-se de 2n.2
 f3 e f4 apresentam desempenho melhor que 2 .n
0,2 / 0,2 ptsPergunta 4
Considere o código abaixo, implementado utilizando-se a linguagem
de programação Java:
18/05/2022 10:04 Exercícios sobre complexidade de algoritmos: ALGORITMOS E ESTRUTURAS DE DADOS II - Engenharia de Software - U…
https://pucminas.instructure.com/courses/91650/quizzes/288772 5/6
public static boolean saoDisjuntos(int[] A, int[] B) {
 for (int i = 0; i < A.length; i++)
 for (int j = 0; j < B.length; j++)
 if (A[i] == B[j])
 return false;
 return true;
 }


Considere ainda que cada um dos vetores
“A” e “B” apresenta n elementos.
A ordem de complexidade desse algoritmo é:
 O(n) 
 O(2 * n) 
 O(log n) 
 O( )
 O(n * log n) 
0,2 / 0,2 ptsPergunta 5
Leia as afirmativas a seguir, considerando que f1(n) e f2(n) são
funções positivas.
 
1. Se f2(n) é O(f1(n)), um algoritmo de função de complexidade de
tempo f1(n) possui ordem de complexidade f2(n).
2. Se f2(n) é O(f1(n)), então f1(n) é um limite superior para f2(n).
3. Se a função f2(n) = 5 * log(n) + 11 , então a função f2(n) é
O(log(n)).
18/05/2022 10:04 Exercícios sobre complexidade de algoritmos: ALGORITMOS E ESTRUTURAS DE DADOS II - Engenharia de Software - U…
https://pucminas.instructure.com/courses/91650/quizzes/288772 6/6
4. Se f2(n) = n e f1(n) = (n + 2) , temos que f2(n) é O(f1(n)) e f1(n) é
O(f2(n)).
5. Se f2(n) = 2 * n + 1 e f1(n) = 2 * n, temos que f2(n) = O(f1(n)).
 
Assinale a alternativa que apresenta somente as
afirmativas CORRETAS.
2 2
 1, 3, 4, 5 
 1, 2, 4, 5 
 2, 3, 4 
 2, 3, 5 
 2, 3, 4, 5 
Pontuação do teste: 0,8 de 1