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).
Nenhum comentário:
Postar um comentário