Questões do POSCOMP sobre Complexidade de Algoritmos #01

O intuito desta postagem é apresentar a solução de algumas questões do POSCOMP sobre Complexidade de Algoritmos. O POSCOMP (Exame Nacional para Ingresso na Pós-Graduação em Computação) "testa conhecimentos na área de Computação e tem como objetivo específico avaliar os conhecimentos de candidatos a Programas de Pós-Graduação em Computação oferecidos no Brasil" (SBC sobre o POSCOMP).

Para mais questões sobre o exame acesse a página POSCOMP.

POSCOMP 2002

Questão 29

Qual das seguintes afirmações sobre crescimento assintótico de funções não é verdadeira:

• (a) $2n^2+3n+1=O(n^2)$
• (b) Se $f(n) = O(g(n))$ então $g(n) = O(f(n))$
• (c) $\log n^2 = O(\log n)$
• (d) Se $f(n)=O(g(n))$ e $g(n)=O(h(n))$ então $f(n)=O(h(n))$
• (e) $2^{n+1}=O(2^n)$

Resolução

Conforme o gabarito, a alternativa (b) é a correta. Vamos analisar cada uma:

(a) A afirmação é verdadeira, pois qualquer polinômio de grau k é $O(n^k)$. Neste caso, k = 2, portanto $2n^2+3n+1=O(n^2)$.

(b) É falso. Quando afirmamos que $f(n)=O(g(n))$ significa que que $g(n)$ representa um limite superior para $f(n)$, portanto nem sempre temos $g(n)=O(f(n))$. Além disso, podemos também utilizar um contraexemplo. Suponha que $f(n)=n^2$ e $g(n)=n^3$. Dessa forma, teríamos $n^2 = O(n^3)$, que é verdade. Porém, $n^3\neq O(n^2)$, portanto a afirmação é falsa.

(c) $\log n^2=2\log n = O(\log n)$, portanto é verdade.

(d) É verdade. Essa é a propriedade transitiva da notação Big-O.

(e) $2^{n+1}=2\times 2^n = O(2^n)$, portanto é verdade.

Questão 31

Considere o algoritmo da busca sequencial de um elemento em um conjunto com n elementos. A expressão que representa o tempo médio de execução desse algoritmo para uma busca bem sucedida é:

• (a) $n^2$
• (b) $n(n+1)/2$
• (c) $\log_2 n$
• (d) $(n+1)/2$
• (e) $n\log n$

Resolução

O caso médio é a média (ou valor esperado) de todos os casos possíveis. Basicamente, multiplicamos a probabilidade de cada caso pelo custo e somamos os resultados. Como todos os casos são igualmente prováveis, então a probabilidade de cada caso é $1/n$, onde $n$ é o tamanho do vetor. O custo para encontrar um elemento é igual à posição que o mesmo ocupa, que é a quantidade de comparações necessárias para encontrá-lo. Isto é, se o elemento está na posição $i$, então o custo é $i$. Logo,

$$T(n)=\sum_{i=1}^n \frac{1}{n}\times i = \frac{1}{n} \sum_{i=1}^n i$$

$$T(n)= \frac{1}{n} \times \frac{n(n+1)}{2} = \frac{n+1}{2}$$

Portanto, a resposta correta é (d).

Questão 32

Quais dos algoritmos de ordenação abaixo possuem tempo no pior caso e tempo médio de execução proporcional a $O(n\log n)$.

• (a) Bubble sort e quicksort
• (b) Quicksort e merge sort
• (c) Merge sort e bubble sort
• (d) Heap sort e selection sort
• (e) Merge sort e heap sort

Resolução

Vamos analisar cada alternativa:

(a) Não é verdade, pois o Bubble sort tem pior caso e caso médio igual a $O(n^2)$ e o pior caso do Quicksort também é $O(n^2)$.

(b) É falso, pois, apesar do Merge sort ser $O(n\log n)$ no pior caso e no caso médio, o Quicksort é quadrático no pior caso.

(c) É falso, pois o Bubble sort é quadrático no caso médio e no pior caso.

(d) É falso, pois o Selection sort é quadrático.

(e) É verdade, pois o Merge sort e o Heap sort têm complexidade $O(n\log n)$ no pior caso e no caso médio.

Portanto, a alternativa correta é a (e).

POSCOMP 2003

Questão 37

Qual é o número mínimo de comparações necessário para encontrar o menor elemento de um conjunto qualquer não ordenado de n elementos?

• (a) 1
• (b) n - 1
• (c) n
• (d) n + 1
• (e) n log n

Resolução

A alternativa correta é a (b), porque se você considerar que o primeiro elemento do conjunto é o menor, então terá que fazer comparações com os outros n - 1 elementos restantes, fazendo substituições no valor (variável) caso algum valor menor seja encontrado.

Questão 39

Quais das seguintes igualdades são verdadeiras?

• I. $n^2=O(n^3)$
• II. $2*n+1=O(n^2)$
• III. $n^3=O(n^2)$
• IV. $3*n+5*n\log n = O(n)$
• V. $\log n + \sqrt{n}=O(n)$

• (a) somente I e II
• (b) somente II, III e IV
• (c) somente III, IV e V
• (d) somente I, II e V
• (e) somente I, III e IV

Resolução

Vamos analisar cada afirmação:

I) É verdadeira, pois $n^3$ é um limite superior para $n^2$.

II) É verdadeira, pois $n^2$ é assintoticamente maior que $2*n+1$.

III) É falsa, pois $n^2$ não é um limite superior para $n^3$. Na prática, $n^3$ é assintoticamente maior que $n^2$.

IV) É falsa, pois $n\log n$ é assintoticamente maior que $n$.

V) É verdadeira, pois $n$ é um limite superior para $\sqrt{n}$ e para $\log n$.

Portanto, a alternativa correta é a (d).

POSCOMP 2004

Questão 25

Considere as seguintes afirmativas sobre o algoritmo de pesquisa binária:

• I. a entrada deve estar ordenada
• II. uma pesquisa com sucesso é feita em tempo logarítmico na média
• III. uma pesquisa sem sucesso é feita em tempo logarítmico na média
• IV. o pior caso de qualquer busca é logarítmico

As afirmativas corretas são:

• (a) Somente I e II.
• (b) Somente I, II e III.
• (c) Somente II e III.
• (d) Somente III e IV.
• (e) Todas as afirmativas estão corretas.

Resolução

A afirmativa I é verdadeira, pois a pesquisa binária só funciona se o vetor estiver ordenado.

As afirmativas II, III e IV também são verdadeiras. O pior caso e o caso médio têm complexidade $O(\log n)$. Observe que as afirmativas III e IV são quase equivalentes, pois o pior caso é justamente a busca sem sucesso.

Questão 34

Um algoritmo é executado em 10 segundos para uma entrada de tamanho 50. Se o algoritmo é quadrático, quanto tempo em segundos ele gastará, aproximadamente, no mesmo computador, se a entrada tiver tamanho 100?

• (a) 10
• (b) 20
• (c) 40
• (d) 100
• (e) 500

Resolução

Como ele é quadrático, então podemos fazer a seguinte aproximação para o tempo de execução: $T(n) = cn^2$, onde $c$ é uma constante que determinaremos a seguir.

Sabe-se que $T(50) = 10$, logo

$$\begin{align*}c\times 50^2 = 10\\2500c=10\\c=\frac{10}{2500}=\frac{1}{250}\end{align*}.$$

Ou seja, $T(n)=\cfrac{1}{250}n^2$. Para $n = 100$, temos

$$\begin{align*}T(100) = \frac{1}{250}\times100^2 = \frac{10000}{250}=40\end{align*}.$$

Portanto, a alternativa correta é a (c).