Questões do POSCOMP sobre Complexidade de Algoritmos #06

Por
|  

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

POSCOMP 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(n1)+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.

Questão 10 do POSCOMP 2010
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:

T(n)=nT(n1)+n=n[(n1)T(n2)+n1]+n=n(n1)T(n2)+n(n1)+n=n(n1)[(n2)T(n3)+n2]+n(n1)+n=n(n1)(n2)T(n3)+n(n1)(n2)+n(n1)+n=n!(nk)!T(nk)+ki=1n!(ni)!

A constante k é definida pelo caso base:

T(nk)=T(1)nk=1k=n1

Logo,

T(n)=n!(n(n1))!T(n(n1))+n1i=1n!(ni)!=n!1!T(1)+n1i=1n!(ni)!=n1i=1n!(ni)!=n!n1i=11(ni)!

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!n1i=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 e1 quando n, portanto

T(n)=n!n1i=11i!(e1)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)=aF(nb)+cnk para F(n) assintoticamente não decrescente, a,b,kN, a1,b2,k0, e cR+. 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.

Sugestões de livros para estudantes de computação na Amazon (patrocinado): Lista de Livros

Obrigado pela leitura! Se você puder, considere apoiar financeiramente o Blog Cyberini, Chave Pix: cyberpix9@gmail.com

Doar com PayPal

Siga o blog

Redes sociais: Facebook, Twitter, YouTube, Pinterest, Instagram, Telegram

Importante: utilize o bom senso na hora de comentar. Acesse a política de privacidade para maiores informações sobre comentários.

Nenhum comentário:

Postar um comentário

Este site usa cookies para fornecer serviços, analisar o tráfego e exibir publicidade personalizada, conforme a nossa política de privacidade. Seus dados, como IP e user agent, são compartilhados com nossos parceiros (como o Google). Saiba Mais

RecusarAceitar