FC ConcursosFC Concursos

Questão FC373202

Considere, por hipótese, que uma Analista de Sistemas da Câmara Legislativa está participando de um processo de avaliação de quatro softwares concorrentes para suporte a algumas at

Algoritmos e Lógica de Programação

FCC · 2018

Considere, por hipótese, que uma Analista de Sistemas da Câmara Legislativa está participando de um processo de avaliação de quatro softwares concorrentes para suporte a algumas atividades da Câmara. A Analista solicitou que cada empresa fornecesse a função de complexidade do principal algoritmo do software. As funções de complexidade estão listadas abaixo.


I. f(n) = n2
II. f(n) = nlog2n
III. f(n) = 2n
IV. f(n) = 3log2n


Ao fazer a análise dos algoritmos, a Analista conclui corretamente que

  1. para entradas de tamanho n até 1.000 qualquer um dos softwares poderá ser utilizado sem comprometer o desempenho do sistema.
  2. há uma relação de dominação assintótica de um dos softwares sobre os demais e este software que domina assintoticamente os outros não deve ser escolhido, pois pode comprometer o desempenho do sistema.
  3. para entradas de tamanho n acima de 1.000 o software IV é o mais indicado para ser escolhido, pois quanto maior o valor de n, menor o valor do log2n.
  4. para entradas de tamanho n igual ou acima de 1.000.000 qualquer um dos softwares ficará inviável, pois o desempenho do sistema ficará comprometido.
  5. ambos os softwares com funções de complexidade logarítmicas possuem algoritmos ótimos e dominam assintoticamente todos os outros, por isso são as melhores escolhas.
Mostrar resposta e comentário

Gabarito

B

Comentário do professor

A opção ressalta a existência de uma dominação assintótica: a função \(2^n\) cresce muito mais rápido que funções polinomiais, logarítmicas ou quasi-lineares. Em termos formais, existe \(n_0\) tal que, para todo \(n>n_0\), \(2^n\) é maior que \(n^2\), \(n\log_2 n\) e \(3\log_2 n\).

Isso significa que um algoritmo com custo \(2^n\) terá tempo de execução que explode quando o tamanho da entrada aumenta, comprometendo a escalabilidade do sistema.

Mesmo que para entradas pequenas o software pareça aceitável, a análise assintótica prioriza o comportamento para \(n\) grande. Por isso, o software cujo algoritmo tem complexidade \(2^n\) não deve ser escolhido, pois pode tornar o sistema inviável à medida que a carga cresce.

Conteúdo do catálogo FC Concursos · Atualizado em

Continue aprendendo