Questão de Algoritmos e Estrutura de Dados — Algoritmos — FUMARC 2018
Algoritmos e Estrutura de Dados›Algoritmos
Código
qq342646
Banca
FUMARC
Órgão
COPASA
Ano
2018
Nível
Superior
Cargo
Agente de Saneamento - Desenvolvedor Sistemas Informação
Analise as afirmativas a seguir sobre complexidade de algoritmos:I. Algoritmos de complexidade O(n log n) resolvem um problema quebrando-o em problemas menores, resolvendo cada um deles independentemente e depois ajuntando as soluções.II. Algoritmos de complexidade O(1) são chamados de complexidade linear, onde um pequeno trabalho é realizado sobre cada elemento de entrada.III. Algoritmos de complexidade O(n) são chamados de complexidade constante, onde o tempo de execução cresce na mesma proporção do crescimento da estrutura de dados.Estão CORRETAS as afirmativas:
AI, apenas.
BI e II, apenas.
CII e III, apenas.
DI, II e III.
Revelar gabarito e comentário▾
GabaritoA — I, apenas.
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”.
Complexidade de Algoritmos
Gabarito: letra A. Apenas a afirmativa I está correta: algoritmos O(n log n) frequentemente usam a estratégia de divisão e conquista (quebrar em subproblemas, resolver independentemente e combinar). A afirmativa II inverte os conceitos: O(1) é complexidade constante, não linear. A afirmativa III também inverte: O(n) é complexidade linear, não constante. Portanto, apenas I é verdadeira.
NÃO CAIA NESSA!
A banca troca os nomes das classes de complexidade: O(1) (constante) é apontado como linear, e O(n) (linear) como constante. Fique atento à definição de cada notação.
Afirmativa
Complexidade citada
Nome correto da classe
Descrição correta?
Justificativa
I
O(n log n)
Linearítmica / Divisão e conquista
✅ Sim
Quebra em subproblemas, resolve independentemente e combina (ex.: Mergesort)
II
O(1)
Constante
❌ Não
O(1) é constante, não linear; não processa cada elemento
III
O(n)
Linear
❌ Não
O(n) é linear, não constante; tempo cresce proporcionalmente à entrada
Complexidade de algoritmos: O(1) — constante (Tempo não depende da entrada); O(n) — linear (Tempo proporcional à entrada); O(n log n) — log-linear (Divisão e conquista, Quebra, resolve, combina)
Item I — ✅ Correto
A afirmativa descreve corretamente o paradigma divisão e conquista, que geralmente resulta em complexidade O(n log n), como nos algoritmos Mergesort e Heapsort. A quebra em problemas menores, solução independente e combinação é a essência desse paradigma.
Item II — ❌ Incorreto
Algoritmos de complexidade O(1) são chamados de complexidade constante, e não linear. Neles, o tempo de execução não depende do tamanho da entrada. Já a complexidade linear é O(n), onde cada elemento de entrada recebe um processamento.
Item III — ❌ Incorreto
Algoritmos de complexidade O(n) são chamados de complexidade linear, e não constante. Neles, o tempo de execução cresce proporcionalmente ao tamanho da entrada (relação 1:1). Complexidade constante é O(1), onde o tempo não varia com a entrada.