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)={0,se n=1nT(n−1)+nse n>1
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) n2
- (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.

É 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:
T(n)=nT(n−1)+n=n[(n−1)T(n−2)+n−1]+n=n(n−1)T(n−2)+n(n−1)+n=n(n−1)[(n−2)T(n−3)+n−2]+n(n−1)+n=n(n−1)(n−2)T(n−3)+n(n−1)(n−2)+n(n−1)+n=n!(n−k)!T(n−k)+k∑i=1n!(n−i)!
A constante k é definida pelo caso base:
T(n−k)=T(1)n−k=1k=n−1
Logo,
T(n)=n!(n−(n−1))!T(n−(n−1))+n−1∑i=1n!(n−i)!=n!1!T(1)+n−1∑i=1n!(n−i)!=n−1∑i=1n!(n−i)!=n!n−1∑i=11(n−i)!
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!n−1∑i=11i!.
Você poderia perguntar "essa fórmula está correta?". Vamos testá-la com alguns valores: 2, 3, 4.
T(2)=2!×(1)=2T(3)=3!×(1+12)=9T(4)=4!×(1+12+16)=40
Agora, vamos calcular os mesmos valores, porém utilizando diretamente a relação de recorrência:
T(2)=2×T(1)+2=2×0+2=2T(3)=3×T(2)+3=3×2+3=9T(4)=4×T(3)+4=4×9+4=40
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→∞, portanto
T(n)=n!n−1∑i=11i!≈(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 n2, 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(n2).
- ( ) 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(n3).
- ( ) O limite O(n2) 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(n3) é 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⋅F(nb)+c⋅nk para F(n) assintoticamente não decrescente, a,b,k∈N, a≥1,b≥2,k≥0, e c∈R+. Nessas condições, de acordo com o Teorema Mestre,
- Se logalogb>k, então F(n) está em Θ(nloga/logb),
- Se logalogb=k, então F(n) está em Θ(nklogn)
- Se logalogb<k, então F(n) está em Θ(nk)
Considere os algoritmos A, B e C, que são descritos, respectivamente, pelas equações de recorrências:
FA(n)=8F(n4)+n
FB(n)=4F(n2)+n2
FC(n)=2F(n4)+n3
Dado que log22=1, log24=2 e log28=3, como pode-se comparar a ordem de complexidade Θ dos algoritmos A, B e C?
- (A) Θ(FA)>Θ(FB)>Θ(FC)
- (B) Θ(FA)<Θ(FB)<Θ(FC)
- (C) Θ(FA)>Θ(FB)<Θ(FC)
- (D) Θ(FA)<Θ(FB)>Θ(FC)
- (E) Θ(FA)=Θ(FB)=Θ(FC)
Resolução
Vamos calcular a complexidade de cada algoritmo. Para o algoritmo A, temos
a=8,b=4,k=1
log8log4=log28log24=32>1
Portanto, FA(n)=Θ(n3/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,b=2,k=2
log4log2=log24log22=21=2
Logo, FB(n)=Θ(n2logn).
Por fim, vamos calcular a complexidade de C:
a=2,b=4,k=3
log2log4=log22log24=12<3
Ou seja, FC(n)=Θ(n3).
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,
Θ(n3/2)<Θ(n2logn)<Θ(n3)
Θ(FA)<Θ(FB)<Θ(FC)
Logo, a opção certa é a B.
Nenhum comentário:
Postar um comentário