Questões do POSCOMP sobre Complexidade de Algoritmos #05

Por
|  

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

POSCOMP questões resolvidas 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)+qn 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.

Sugestões de livros para estudantes de computação na Amazon (patrocinado): Lista de Livros

Obrigado pela leitura! Se você puder, considere apoiar financeiramente o Blog Cyberini, Chave Pix: cyberpix9@gmail.com

Doar com PayPal

Siga o blog

Redes sociais: Facebook, Twitter, YouTube, Pinterest, Instagram, Telegram

Importante: utilize o bom senso na hora de comentar. Acesse a política de privacidade para maiores informações sobre comentários.

Nenhum comentário:

Postar um comentário

Este site usa cookies para fornecer serviços, analisar o tráfego e exibir publicidade personalizada, conforme a nossa política de privacidade. Seus dados, como IP e user agent, são compartilhados com nossos parceiros (como o Google). Saiba Mais

RecusarAceitar