Questões do POSCOMP sobre Complexidade de Algoritmos #03

Continuando a série de postagens com a resolução de questões do POSCOMP, nesta postagem apresento a resolução de algumas questões dos anos 2009 e 2010 sobre Complexidade de Algoritmos.

Para mais questões resolvidas, acesse a página POSCOMP.

POSCOMP 2009

As questões a seguir são do POSCOMP 2009.

Questão 21

A sequência de Fibonacci é uma sequência de inteiros, cujo primeiro termo é 0, o segundo termo é 1, e a partir do terceiro, cada termo é igual à soma dos dois anteriores. O seguinte algoritmo recursivo retorna o n-ésimo termo da sequência

Procedimento F(n)
    se n < 3 então retornar n-1
    senão retornar F(n-1) + F(n-2)

A chamada externa é F(n), sendo n > 0.

Assinale a alternativa CORRETA:

• (A) O algoritmo não está correto, pois não retorna o n-ésimo termo da sequência.
• (B) O algoritmo é ótimo, no que diz respeito ao número de passos.
• (C) O número de passos efetuados pelo algoritmo é linear em n.
• (D) O número de passos efetuados pelo algoritmo é polinomial em n.
• (E) O número de passos efetuados pelo algoritmo é exponencial em n.

Resolução

A versão recursiva do algoritmo que calcula o n-ésimo número de Fibonacci de uma dada posição é exponencial. Portanto, a alternativa correta é a E.

Questão 22

Deseja-se efetuar uma busca para localizar uma certa chave fixa x, em uma tabela contendo n elementos. A busca considerada pode ser a linear ou binária. No primeiro caso pode-se considerar que a tabela esteja ordenada ou não. No segundo caso a tabela está, de forma óbvia, ordenada.

Assinale a alternativa CORRETA:

• (A) A busca binária sempre localiza x, efetuando menos comparações que a busca linear.
• (B) A busca linear ordenada sempre localiza x, efetuando menos comparações que a não ordenada.
• (C) A busca linear não ordenada sempre localiza x, com menos comparações que a ordenada.
• (D) A busca binária requer O(log n) comparações, no máximo, para localizar x.
• (E) A busca linear ordenada nunca requer mais do que n/2 comparações para localizar x.

Resolução

Vamos analisar cada alternativa:

(A) É falsa. Suponha que a chave esteja na primeira posição e que a tabela esteja ordenada. Neste caso, a busca linear precisaria de apenas uma comparação e a busca binária precisaria de mais de uma (considerando n > 2).

(B) e (C) são falsas. O fato de o vetor está ordenado ou desordenado não nos permite inferir que uma situação irá requerer menos comparações do que a outra.

(D) É verdadeira.

(E) É falsa. Se a chave de busca estiver na última posição, por exemplo, serão necessárias n comparações.

Portanto, a alternativa correta é a D.

Questão 34

Dado um conjunto C contendo n inteiros distintos, qual das seguintes estruturas de dados em memória principal permite construir um algoritmo para encontrar o valor máximo de C em tempo constante?

• (A) Um vetor não ordenado.
• (B) Um vetor ordenado.
• (C) Uma árvore binária de busca balanceada.
• (D) Uma lista encadeada simples ordenada em ordem crescente.
• (E) Uma árvore rubro-negra.

Resolução

Vamos analisar as alternativas:

(A) É falsa. A busca pelo valor máximo seria feita em tempo O(n), pois você precisaria verificar todos os elementos do vetor.

(B) É verdadeira. O valor máximo estará no final do vetor, portanto basta retornar o valor da última posição, algo que pode ser realizado em tempo O(1), pois o acesso aos elementos de um vetor pode ser feito em tempo constante.

(C) É falsa. A complexidade seria O(log n), isto é, a complexidade é proporcional à altura da árvore.

(D) É falsa. O valor máximo estará no último nó da lista, portanto, o acesso será realizado em tempo O(n). É claro, estamos considerando uma lista simples (sem nó cauda).

(E) É falsa. A justificativa é a mesma de C.

Portanto, a alternativa correta é a B.

POSCOMP 2010

As questões a seguir são do POSCOMP 2010.

Questão 25

Considere dois algoritmos $A_1$ E $A_2$, cujas funções de custo são, respectivamente, $T_1(n) = n^2 - n +$1 e $T_2(n) = 6n\log_2 n + 2n$. Para simplificar a análise, assuma que $n > 0$ é sempre uma potência de 2. Com relação ao enunciado, assinale a alternativa correta.

• (A) Como $T_1(n) = \Theta(n^2)$ e $T_2(n) = \Theta(n\log n)$, então $A_2$ é sempre mais eficiente que $A_1$.
• (B) O limite superior $T_1(n) = O(n^3)$ é correto e assintoticamente restrito.
• (C) O limite inferior $T_2(n) =\Omega(n^3)$ é correto e assintoticamente restrito.
• (D) $T_1$ e $T_2$ são assintoticamente equivalentes.
• (E) $A_1$ é mais eficiente que $A_2$, para n suficientemente pequeno.

Resolução

Vamos analisar cada alternativa:

(A) É falsa. Apesar das notações assintóticas estarem corretas, observe, por exemplo, que quando $n = 1$, $T_1(1) = 1$ e $T_2(2)=2$, logo, nesse caso, $A_1$ é mais eficiente que $A_2$.

(B) É falsa. O limite está correto, mas não é assintoticamente restrito, pois $T_1(n)$ não é $\Theta(n^3)$.

(C) É falsa. $T_2(n)$ não é $\Omega(n^3)$, pois a função cúbica é assintoticamente superior.

(D) É falsa, pois não há equivalência entre as duas funções.

(E) É verdadeira. Observe que para $n=1$ e para $n=2$, por exemplo, o algoritmo $A_1$ é mais eficiente.

Portanto, a alternativa correta é a E.

Questão 27

Considere o problema de ordenação onde os vetores a serem ordenados, de tamanho n > 0, possuem $\lfloor n/2 \rfloor$ valores iguais a um número real x e $\lceil n/2\rceil$ valores iguais a um outro número real y. Considere que os números reais x e y são conhecidos e fixos, porém estão distribuídos aleatoriamente no vetor a ser ordenado.

Neste caso, é correto afirmar:

• (A) Podemos ordenar estes vetores a um custo O(n).
• (B) No caso médio, o Quicksort será o algoritmo mais eficiente para este problema, com um custo $O(n\log n)$.
• (C) O algoritmo de ordenação por inserção sempre opera no melhor caso com um custo O(n).
• (D) O limite inferior para esta classe de problema é $\Omega(n^2)$.
• (E) O limite inferior para esta classe de problema é $\Omega(n\log n)$.

Resolução

Utilizando como base o algoritmo de partição do Quicksort, podemos construir um algoritmo O(n) para resolver o problema.

O menor valor entre x e y será o pivô. Todos os elementos iguais ao pivô devem ficar à esquerda. O algoritmo é apresentado a seguir (pseudocódigo)

1. sort(V[1...n], x, y)
2. |    pivô ← min(x, y)
3. |    i ← 0
4. |    para j ← 1 até n
5. |    |    se(V[j] = pivô)
6. |    |    |    i ← i + 1
7. |    |    |    trocar(V, i, j)
8. |    |    fim_se
9. |    fim_para
10.fim_sort

O algoritmo foi escrito utilizando como base o algoritmo de partição do Quicksort do livro do Cormen.

Portanto, a alternativa correta é a A.

Referências

CORMEN, T. H. et al. Algoritmos: teoria e prática. 3 ed. Rio de Janeiro: Elsevier, 2012.