Questão 575633 de Tecnologia da Informação - FCC 2018

Questão

ID 575633

Disciplina: Tecnologia da Informação

Assuntos: Complexidade de Algoritmos (Big-O, P x NP)

Ano: 2018 Banca: FCC - Fundação Carlos Chagas Órgão: Câmara Legislativa do Distrito Federal

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) = n²

II. f(n) = nlog₂n

III. f(n) = 2ⁿ

IV. f(n) = 3log₂n

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

Alternativa A:
para entradas de tamanho n até 1.000 qualquer um dos softwares poderá ser utilizado sem comprometer o desempenho do sistema.
Alternativa B:
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.
Alternativa C:
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.
Alternativa D:
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.
Alternativa E:
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.

Estatísticas Cadernos

Questão 575633

Continue estudando na plataforma