Pular para o conteúdo principal

Questão de Algoritmos e Estrutura de Dados — Algoritmos — FCC 2018

Algoritmos e Estrutura de DadosAlgoritmos
Código
fc042263
Banca
FCC
Órgão
Câmara Legislativa do Distrito Federal
Ano
2018
Cargo
Analista de Sistemas - Área 1
Considere, por hipótese, que uma Analista de Sistemas da Câmara Legislativa está participando de um processo de avaliaçãode quatro softwares concorrentes para suporte a algumas atividades da Câmara. A Analista solicitou que cada empresafornecesse 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₂nIII. f(n) = 2nIV. f(n) = 3log₂nAo fazer a análise dos algoritmos, a Analista conclui corretamente que
  1. Apara entradas de tamanho n até 1.000 qualquer um dos softwares poderá ser utilizado sem comprometer o desempenho do sistema.
  2. Bhá 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. Cpara 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 log₂n.
  4. Dpara 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. Eambos 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.
Revelar gabarito e comentário

GabaritoB — 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.

Comentário gerado por IA. É um apoio ao estudo, ancorado em fontes, mas pode conter imprecisões — confira sempre na fonte oficial (lei, súmula, edital e gabarito da banca). Encontrou um erro? Use “Reportar”.

Análise de complexidade de algoritmos

Gabarito: letra B. A função (f(n)=n^2) (I) domina assintoticamente as demais ((n \log n), (2n) e (3 \log n)) e, por ser a de maior crescimento, é a que mais compromete o desempenho para entradas grandes – portanto, não deve ser escolhida. As demais alternativas contêm erros conceituais sobre o comportamento das funções.

A questão testa o conhecimento sobre a ordem de crescimento das funções de complexidade. Em notação assintótica, da mais lenta para a mais rápida (para (n) grande):

Função

Classe de complexidade

Exemplo de crescimento (n=10^6)

(3 \log_2 n)

(O(\log n))

≈ 3 × 20 = 60 operações

(2n)

(O(n))

2 × 10^6 operações

(n \log_2 n)

(O(n \log n))

10^6 × 20 ≈ 2 × 10^7 operações

(n^2)

(O(n^2))

10^12 operações (inviável)

O software com complexidade quadrática domina os demais (cresce mais rápido) e, para entradas grandes, torna o sistema lento.

Complexidade assintótica
  • 1Mais eficiente (crescimento lento)
    • 3 log₂ n (O(log n))
    • 2n (O(n))
    • n log₂ n (O(n log n))
  • 2Menos eficiente (crescimento rápido)
    • n² (O(n²)) — domina os demais
      • Não deve ser escolhido
LEVEL · soulevel.com.br

Alternativa A — ❌ Incorreta

Afirma que qualquer software serve para (n) até 1.000. A função (n^2) com (n=1000) gera (10^6) operações, o que pode já comprometer o desempenho dependendo do contexto – e a análise assintótica não se baseia em um limiar fixo.

Alternativa B — ✅ Correta ⟵ GABARITO

Há dominação assintótica de um software (o de complexidade (n^2)) sobre os demais, e este não deve ser escolhido por comprometer o desempenho. Exatamente o que a alternativa descreve.

Alternativa C — ❌ Incorreta

Afirma que o logaritmo diminui com o aumento de (n). Na verdade, (\log_2 n) cresce (lentamente) à medida que (n) aumenta. O software IV ((3 \log_2 n)) é o mais eficiente, mas não por essa razão errada.

Alternativa D — ❌ Incorreta

Diz que todos os softwares ficam inviáveis para (n \geq 10^6). As funções logarítmica e linear ainda são perfeitamente viáveis (poucas operações), apenas a quadrática se torna proibitiva.

Alternativa E — ❌ Incorreta

Afirma que ambos os softwares com complexidade logarítmica (na verdade, só o IV é puramente logarítmico; o II é (n \log n)) dominam assintoticamente os outros – o oposto é verdade: a quadrática domina todos. Além disso, não há dois algoritmos puramente logarítmicos na lista.

NÃO CAIA NESSA!

A banca explora a confusão entre crescimento e decrescimento do logaritmo (alternativa C) e inverte a relação de dominação (alternativa E). Lembre-se: (\log n) cresce, e a ordem de dominância é (n^2 \gg n \log n \gg n \gg \log n).

Gabarito: letra B.

Link permanente: /questoes/fc042263