Questões do POSCOMP sobre Complexidade de Algoritmos #06

As questões desta postagem são das provas do POSCOMP dos anos 2010, 2014 e 2015 sobre Complexidade de Algoritmos.

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

POSCOMP 2010

A questão a seguir é da prova do ano 2010.

Questão 10

A relação de recorrência abaixo representa um processo de enumeração por recursão.

$$T(n)=\begin{cases}0,\quad\quad\quad\quad\quad\quad\text{se } n=1\\nT(n-1)+n\quad\text{se }n>1\end{cases}$$

Assinale a alternativa que corresponde a um limite superior para o valor da fórmula fechada de tal relação de recorrência.

• (A) T(1)
• (B) 0
• (C) n²
• (D) 1024
• (E) n!

Resolução

A relação de recorrência T(n) é bem parecida com a relação de recorrência do teorema de Laplace, que já foi analisada num artigo anterior.

Entretanto, o que realmente surpreendente é que o gabarito do POSCOMP está errado.

Questão 10 do POSCOMP 2010 (Clique aqui para ampliar)

É claro, antes de afirmar isso, eu analisei várias vezes a questão.

Para encontrar o limite superior de T(n), vamos resolver a equação de recorrência:

$$\begin{align*}T(n)&=nT(n-1)+n\\&=n\left[(n-1)T(n-2)+n-1\right]+n\\&=n(n-1)T(n-2)+n(n-1)+n\\&=n(n-1)\left[(n-2)T(n-3)+n-2\right]+n(n-1)+n\\&=n(n-1)(n-2)T(n-3)+n(n-1)(n-2)+n(n-1)+n\\&=\cfrac{n!}{(n-k)!}T(n-k)+\sum_{i=1}^k\cfrac{n!}{(n-i)!}\end{align*}$$

A constante $k$ é definida pelo caso base:

$$\begin{align*}T(n-k) = T(1)\\n-k=1\\k=n-1\end{align*}$$

Logo,

$$\begin{align*}T(n)&=\cfrac{n!}{(n-(n-1))!}T(n-(n-1))+\sum_{i=1}^{n-1}\cfrac{n!}{(n-i)!}\\&=\cfrac{n!}{1!}T(1)+\sum_{i=1}^{n-1}\cfrac{n!}{(n-i)!}\\&=\sum_{i=1}^{n-1}\cfrac{n!}{(n-i)!}\\&=n!\sum_{i=1}^{n-1}\cfrac{1}{(n-i)!}\end{align*}$$

Nesse último cálculo, eu utilizei o caso base: $T(1)=0$. O somatório pode ser invertido, isto é, podemos somar as parcelas na ordem inversa e, com isso, a série fica mais simples ainda:

$$T(n)=n!\sum_{i=1}^{n-1}\cfrac{1}{i!}.$$

Você poderia perguntar "essa fórmula está correta?". Vamos testá-la com alguns valores: 2, 3, 4.

$$\begin{align*}T(2)&=2!\times(1) = 2\\T(3)&=3!\times\left(1+\cfrac{1}{2}\right)=9\\T(4)&=4!\times\left(1+\cfrac{1}{2}+\cfrac{1}{6}\right)=40\end{align*}$$

Agora, vamos calcular os mesmos valores, porém utilizando diretamente a relação de recorrência:

$$\begin{align*}T(2)&=2\times T(1) + 2 =2\times 0 + 2 = 2\\T(3)&=3\times T(2)+3 = 3\times 2 + 3 = 9\\T(4)&=4\times T(3)+4 = 4\times 9 +4 = 40\end{align*}$$

Os valores são os mesmos! Se você quiser, pode continuar calculando T(5), T(6), T(7)... enfim, o somatório está certo.

Entretanto, ainda não fornecemos o limite superior para T(n). Na verdade, é bem "simples". A série que calculamos converge para a constante $e-1$ quando $n\rightarrow\infty$, portanto

$$T(n)=n!\sum_{i=1}^{n-1}\frac{1}{i!}\approx (e-1)n!$$

Logo, $T(n) = O(n!)$, isto é, o limite superior de $T(n)$ é $n!$. Se quiser mais detalhes sobre como resolver a série em questão acesse a postagem Complexidade Algorítmica do Teorema de Laplace no Cálculo de Determinantes, pois a solução da série é demonstrada na seção Primeira Análise: Custo Linear.

Conforme o gabarito, T(n) tem como limite superior a função $n^2$, que está errado. Portanto, a alternativa correta é a E (e não a C).

POSCOMP 2014

A questão a seguir é da prova do ano 2014.

Questão 25

Em relação ao limite assintótico de notação O, atribua V (verdadeiro) ou F (falso) às afirmativas a seguir.

• ( ) Em uma estrutura de laço duplamente aninhado, tem-se imediatamente um limite superior $O(n^2)$.
• ( ) Em uma estrutura de laço duplamente aninhado, o custo de cada iteração do laço interno é de limite superior $O(1)$.
• ( ) Em uma estrutura de laço triplamente aninhado, o custo de cada iteração do laço interno é de limite superior $O(n^3)$.
• ( ) O limite $O(n^2)$ para o tempo de execução do pior caso de execução aplica-se para qualquer entrada.
• ( ) $f(n)=O(g(n))$ é uma afirmação de que algum múltiplo constante de $g(n)$ é de limite assintótico inferior.

Assinale a alternativa que contém, de cima para baixo, a sequência correta.

• (A) V, V, F, V, F.
• (B) V, F, V, F, V.
• (C) F, V, V, F, F.
• (D) F, F, V, V, F.
• (E) F, F, F, V, V.

Resolução

A primeira afirmativa é verdadeira, se assumirmos, é claro, que cada iteração tenha complexidade constante.

A segunda afirmativa também é verdadeira, pois se cada iteração requer tempo constante, então o limite superior é $O(1)$.

A terceira afirmação é falsa, pois cada iteração do laço interno é $O(1)$. O que é $O(n^3)$ é o laço triplamente aninhado completo.

A quarta afirmativa é vaga, pois fala sobre o tempo de execução de algo que não é mencionado. Conforme o gabarito oficial a afirmação é verdadeira...

A quinta afirmativa é falsa, pois $f(n)=O(g(n))$ significa que $g(n)$ representa um limite superior para $f(n)$.

Observe que, mesmo com a ausência de informações na quarta afirmativa, é possível responder corretamente a questão apenas sabendo que as duas primeiras afirmativas são verdadeiras.

Conforme o gabarito oficial, a alternativa certa é a A.

POSCOMP 2015

A questão a seguir é da prova do ano 2015.

Questão 21

Muitas das recorrências que acontecem na análise de algoritmos de divisão e conquista têm a forma $F(n) = a\cdot F\left(\cfrac{n}{b}\right) + c\cdot n^k$ para $F(n)$ assintoticamente não decrescente, $a, b, k\in N$, $a\geq 1, b\geq 2, k\geq 0$, e $c\in\mathbb{R}^{+}$. Nessas condições, de acordo com o Teorema Mestre,

• Se $\cfrac{\log a}{\log b} > k$, então $F(n)$ está em $\Theta\left(n^{\log a/\log b}\right)$,
• Se $\cfrac{\log a}{\log b} = k$, então $F(n)$ está em $\Theta\left(n^{k}\log n\right)$
• Se $\cfrac{\log a}{\log b} < k$, então $F(n)$ está em $\Theta\left(n^{k}\right)$

Considere os algoritmos A, B e C, que são descritos, respectivamente, pelas equações de recorrências:

$$F_A(n)=8F\left(\cfrac{n}{4}\right)+n$$

$$F_B(n)=4F\left(\cfrac{n}{2}\right)+n^2$$

$$F_C(n)=2F\left(\cfrac{n}{4}\right)+n^3$$

Dado que $\log_2 2 = 1$, $\log_2 4 = 2$ e $\log_2 8 = 3$, como pode-se comparar a ordem de complexidade $\Theta$ dos algoritmos A, B e C?

• (A) $\Theta(F_A)>\Theta(F_B)>\Theta(F_C)$
• (B) $\Theta(F_A)<\Theta(F_B)<\Theta(F_C)$
• (C) $\Theta(F_A)>\Theta(F_B)<\Theta(F_C)$
• (D) $\Theta(F_A)<\Theta(F_B)>\Theta(F_C)$
• (E) $\Theta(F_A)=\Theta(F_B)=\Theta(F_C)$

Resolução

Vamos calcular a complexidade de cada algoritmo. Para o algoritmo A, temos

$$a=8, \quad b=4, \quad k=1$$

$$\frac{\log 8}{\log 4}=\frac{\log_2 8}{\log_2 4}=\frac{3}{2} > 1$$

Portanto, $F_A(n)=\Theta(n^{3/2})$. No último cálculo, foi utilizada a propriedade da mudança de base dos logaritmos. Utilizarei essa propriedade novamente nos próximos cálculos.

Para o algoritmo B, temos

$$a=4, \quad b=2, \quad k=2$$

$$\frac{\log 4}{\log 2}=\frac{\log_2 4}{\log_2 2}=\frac{2}{1} = 2$$

Logo, $F_B(n)=\Theta(n^2\log n)$.

Por fim, vamos calcular a complexidade de C:

$$a=2, \quad b=4, \quad k=3$$

$$\frac{\log 2}{\log 4}=\frac{\log_2 2}{\log_2 4}=\frac{1}{2} < 3$$

Ou seja, $F_C(n)=\Theta(n^3)$.

O algoritmo A tem a menor complexidade dos três. C tem a maior complexidade. Já o algoritmo B fica com complexidade entre A e C. Portanto,

$$\Theta(n^{3/2}) < \Theta(n^2\log n) < \Theta(n^3)$$

$$\Theta(F_A) < \Theta(F_B) < \Theta(F_C)$$

Logo, a opção certa é a B.