As questões desta postagem são das provas do POSCOMP 2013, 2015 e 2016 sobre Complexidade de Algoritmos.

Para mais questões resolvidas, acesse a página POSCOMP.
POSCOMP 2013
A questão a seguir é da prova do ano 2013.
Questão 33
Considere o algoritmo a seguir.
MERGESORT(V, i, j) (1) Se (i<j) então (2) m = (i+j)/2; (3) MERGESORT(v, i, m); (4) MERGESORT(v, m+1, j); (5) MESCLAR(v, i, m, j); (6) Fim;
Sobre o comportamento assintótico do algoritmo de ordenação Merge Sort
, assinale a alternativa que apresenta, corretamente, sua complexidade.
- (A) O(logn)
- (B) O(nlogn)
- (C) O(n2)
- (D) O(n3)
- (E) O(2n)
Resolução
A questão poderia ser resumida em "qual é a complexidade assintótica do Merge Sort?". O Merge Sort tradicional tem complexidade O(nlogn) em qualquer caso, que é a complexidade que está em B. Ou seja, a alternativa B é a correta.
POSCOMP 2015
As questões a seguir são do ano 2015.
Questão 22
Quais destes algoritmos de ordenação têm a classe de complexidade assintótica, no pior caso, em O(nlogn)?
- (A) QuickSort, MergeSort, e HeapSort
- (B) QuickSort e SelectionSort
- (C) MergeSort e HeapSort
- (D) QuickSort e BubbleSort
- (E) QuickSort, MergeSort e SelectionSort
Resolução
Basta lembra que o pior caso do Quicksort é O(n²), pois só isso já elimina as alternativas A, B, D e E, restando apenas a alternativa C, que é a correta.
Questão 25
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 de Alg1, Alg2 e Alg3 estão, respectivamente, em O(n), O(n2) e O(n3).
- (B) as complexidades assintóticas de Alg1, Alg2 e Alg3 estão, respectivamente, em O(n), O(n2) e O(n2).
- (C) as complexidades assintóticas de Alg1, Alg2 e Alg3 estão, respectivamente, em O(100), O(10) e O(0,5).
- (D) Alg2 e Alg3 pertencem às mesmas classes de complexidade assintótica.
- (E) Alg1 e Alg2 pertencem às mesmas classes de complexidade assintótica.
Resolução
T1(n) é O(n), T2(n) é O(n2) e T3(n) é O(n3), pois são, respectivamente, polinômios de primeiro, segundo e terceiro grau.
Dessa forma, a alternativa correta é a A.
POSCOMP 2016
As questões a seguir são do ano 2016.
Questão 21
Um algoritmo tem complexidade O(3m3+2mn2+n2+10m+m2). Uma maneira simplificada de representar a complexidade desse algoritmo é:
- (A) O(m3+mn2).
- (B) O(m3).
- (C) O(m2).
- (D) O(mn2).
- (E) O(m3+n2).
Resolução
Como são duas variáveis, então devemos considerar o maior termo de cada variável. Para a variável m, o maior termo é 3m3, que é O(m3). Já o maior termo na variável n é 2mn2, que é O(mn2). Somando ambos, obtemos
O(m3)+O(mn2)=O(m3+mn2)
Portanto, a alternativa correta é a A.
Observação: apesar de n2 ser quadrático em n, assim como 2mn2, ele é inferior a este último por causa da ausência da variável m.
Questão 22
O tempo de execução T(n) de um algoritmo, em que n é o tamanho da entrada, é dado pela equação de recorrência T(n)=8T(n/2)+q∗n se n>1. Dado que T(1)=p, e que p e q são constantes arbitrárias, a complexidade do algoritmo é:
- (A) O(n).
- (B) O(nlogn).
- (C) O(n2).
- (D) O(n3).
- (E) O(nn).
Resolução
A equação pode ser resolvida via teorema mestre, pois a mesma possui a forma
T(n)=aT(n/b)+f(n)
No caso,
a=8,b=2,f(n)=qn
Resolvendo, temos
log28=3
Como f(n) é assintoticamente inferior a n3, então T(n)=Θ(n3). Consequentemente, T(n)=O(n3), portanto a alternativa correta é a D.
Nenhum comentário:
Postar um comentário