Questões do POSCOMP sobre Complexidade de Algoritmos #05

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(\log n)$
• (B) $O(n\log n)$
• (C) $O(n^2)$
• (D) $O(n^3)$
• (E) $O(2^n)$

Resolução

A questão poderia ser resumida em "qual é a complexidade assintótica do Merge Sort?". O Merge Sort tradicional tem complexidade $O(n \log n)$ 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(n\log n)$?

• (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 $T_1(n)=100n+15$, $T_2(n)=10n^2+2n$ e $T_3(n)=0,5n^3+n^2+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(n^2)$ e $O(n^3)$.
• (B) as complexidades assintóticas de Alg1, Alg2 e Alg3 estão, respectivamente, em $O(n)$, $O(n^2)$ e $O(n^2)$.
• (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

$T_1(n)$ é $O(n)$, $T_2(n)$ é $O(n^2)$ e $T_3(n)$ é $O(n^3)$, 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(3m^3+2mn^2+n^2+10m+m^2)$. Uma maneira simplificada de representar a complexidade desse algoritmo é:

• (A) $O(m^3 + mn^2)$.
• (B) $O(m^3)$.
• (C) $O(m^2)$.
• (D) $O(mn^2)$.
• (E) $O(m^3+n^2)$.

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 é $3m^3$, que é $O(m^3)$. Já o maior termo na variável $n$ é $2mn^2$, que é $O(mn^2)$. Somando ambos, obtemos

$$O(m^3)+O(mn^2)=O(m^3+mn^2)$$

Portanto, a alternativa correta é a A.

Observação: apesar de $n^2$ ser quadrático em $n$, assim como $2mn^2$, 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(n \log n)$.
• (C) $O(n^2)$.
• (D) $O(n^3)$.
• (E) $O(n^n)$.

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,\quad b=2, \quad f(n)=qn$$

Resolvendo, temos

$$\log_2 8=3$$

Como $f(n)$ é assintoticamente inferior a $n^3$, então $T(n)=\Theta(n^3)$. Consequentemente, $T(n)=O(n^3)$, portanto a alternativa correta é a D.