POSCOMP 2019: Questão 21 Resolvida (Complexidade de algoritmos)

Questão

Considere os seguintes algoritmos recursivos que resolvem o mesmo problema em uma entrada de tamanho $n$:

• Algoritmo 1: Divide o problema em 3 partes de tamanho $n/4$ cada e gasta um tempo adicional $O(1)$ por chamada.
• Algoritmo 2: Divide o problema em 3 partes de tamanho $n/2$ cada e gasta um tempo adicional $O(n^2)$ por chamada.
• Algoritmo 3: Divide o problema em 3 partes de tamanho $n/3$ cada e gasta um tempo adicional de $O(n)$ por chamada.

A complexidade dos algoritmos 1, 2 e 3 é, respectivamente:

• (A) $\Theta\left(n^{\log_4 3}\right), \Theta\left(n^2\right), \Theta\left(n\log n\right)$
• (B) $\Theta\left(\cfrac{n}{4}\right), \Theta\left(\cfrac{n}{2}\right), \Theta\left(\cfrac{n}{3}\right)$
• (C) $\Theta(1), \Theta\left(n^2\right), \Theta(n)$
• (D) $\Theta\left(n^4\right), \Theta\left(n^2\right), \Theta\left(n^3\right)$
• (E) $\Theta\left(n^{\log_4 3}\right), \Theta\left(n^{\log_2 3}\right), \Theta\left(n^{\log_3 3}\right)$

Resolução

Esta questão será resolvida por etapas.

Complexidade do primeiro algoritmo

Seja $T_1(n)$ o tempo de execução do primeiro algoritmo para uma entrada de tamanho $n$. A chamada recursiva $T_1(n)$ terá como custo $3T_1(n/4)$, o que significa que o problema foi dividido em 3 partes de tamanho $n/4$, além do custo $O(1)$ da chamada.

A equação de recorrência para esse caso será

$$T_1(n)=3T_1(n/4)+O(1).$$

A recorrência anterior pode ser resolvida por meio do teorema mestre ou pelo método de Akra-Bazzi. Utilizaremos o primeiro.

$$a=3,b=4,f(n)=1$$

Essa recorrência se enquadra no primeiro caso do teorema mestre, considerando, dentre inúmeras possibilidades, $\epsilon=\log_4 3$

$$\begin{align*}f(n)&=O\left(n^{\log_b a -\epsilon}\right)\\&=O\left(n^{\log_4 3 -\epsilon}\right)\\&=O\left(n^{\log_4 3 -\log_4 3}\right)\\&=O\left(n^{0}\right)\\&=O (1)\end{align*}$$

Ou seja, $T_1=\Theta\left(\log_b a \right)= \Theta\left(\log_4 3 \right)$.

Complexidade do segundo algoritmo

Para o segundo algoritmo, denota-se o tempo de execução como $T_2(n)$. Nesse caso, o problema é dividido em 3 partes de tamanho $n/2$ e o custo é de $3T_2(n/2)$ mais o custo adicional de $O(n^2)$.

A equação de recorrência, portanto, é

$$T_2(n)= 3T_2(n/2)+O(n^2)$$

Conforme o teorema mestre, para essa recorrência $a=3$, $b=2$ e $f(n)=n^2$, o que faz com que $T_2(n)$ se enquadre no terceiro caso do teorema mestre, que será demonstrado a seguir.

Escolhendo convenientemente $\epsilon = 2-\log_2 3\approx 0{,}41$, obtém-se

$$\begin{align*}f(n)&=\Omega\left(n^{\log_b a + \epsilon}\right)\\& =\Omega\left(n^{\log_2 3 + (2-\log_2 3)}\right)\\& =\Omega\left(n^{\log_2 3 + 2-\log_2 3}\right)\\&=\Omega\left(n^2\right)\end{align*}$$

Como $f(n)=n^2=\Omega\left(n^2\right)$ é verdadeiro, então o limite assintótico anterior está correto.

Porém, ainda é necessário provar a condição de regularidade $af(n/b)\leq cf(n)$ para algum $c<1$ e $n$ suficientemente grande.

$$\begin{gather}af(n/b)\leq cf(n)\\3f(n/2)\leq cf(n)\\3(n/2)^2\leq cn^2\\3n^2/4 \leq cn^2\\3/4 \leq c\end{gather}$$

A desigualdade anterior é satisfeita para qualquer $c\geq 3/4$, consequentemente todo $c$ tal que $3/4\leq c<1$ satisfaz a condição de regularidade.

Isso demonstra que a recorrência $T_2(n)$ satisfaz o terceiro caso do teorema mestre e que, portanto,

$$T_2(n)=\Theta(f(n))=\Theta(n^2).$$

Complexidade do terceiro algoritmo

O tempo de execução do terceiro algoritmo será denotada por $T_3(n)$. Nesse algoritmo, o problema é dividido em 3 partes de tamanho $n/3$ cujo o custo é de $3T(n/3)$. O custo adicional por chamada é $O(n)$.

A partir dessas informações, chega-se na seguinte equação de recorrência

$$T_3(n)=3T_3(n/3)+O(n).$$

A recorrência em questão se enquadra no segundo caso do teorema mestre, onde $a=3$, $b=3$ e $f(n)=n$.

A demonstração exige seja provado que $f(n)=\Theta\left(n^{\log_b a}\right)$, que é verdade, uma vez que $\log_b a=\log_3 3=1$ e, portanto, $f(n)=\Theta\left(n\right)$.

Ou seja, $T_3(n)=\Theta\left(n^{\log_b a}\log n\right)= \Theta\left(n\log n\right)$.

Conclusão

Finalmente, concluímos que o primeiro algoritmo tem complexidade $T_1=\Theta\left(\log_4 3 \right)$, o segundo tem complexidade $T_2(n)= \Theta(n^2)$ e o terceiro tem complexidade $T_3(n)= \Theta\left(n\log n\right)$.

Portanto, a alternativa correta é a A.

Mais questões

Se você deseja mais questões resolvidas do POSCOMP 2019, acesse a tag Questões do POSCOMP 2019.

Agora, se você procura questões, gabaritos e caderno de questões de outras edições, então acesse a página POSCOMP.

Resolverei as questões conforme o tempo permitir e de acordo com os meus conhecimentos. Como eu não sei resolver todas as questões, recomendo que você consulte também o gabarito oficial do exame.