Questão de Algoritmos e Estrutura de Dados — Algoritmos — IDECAN 2023
Algoritmos e Estrutura de Dados›Algoritmos
Código
qq944800
Banca
IDECAN
Órgão
SEFAZ-RR
Ano
2023
Nível
Superior
Cargo
Implementador de Software
A complexidade de algoritmos considera o tempo de execução que um código usa para solucionar um problema. Selecione a alternativa que mostra a notação da menor complexidade entre as seguintes: Ordem quadrática; Ordem cúbica; Ordem logarítmica; Ordem linear; Ordem exponencial
AO(n²)
BO(n³)
CO(n)
DO(cn)
EO(log n)
Revelar gabarito e comentário▾
GabaritoE — O(log n)
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 – Notação Big O
Gabarito: letra E. A menor complexidade entre as listadas é a logarítmica, representada por O(log n). As demais opções (quadrática O(n²), cúbica O(n³), linear O(n) e exponencial O(cⁿ)) crescem mais rapidamente que a logarítmica, sendo, portanto, maiores.
A questão testa a ordenação das principais ordens de crescimento assintótico, um conceito fundamental em análise de algoritmos. A ordem crescente de complexidade (da menor para a maior) é:
Notação
Nome
Exemplo de algoritmo
O(1)
Constante
Acesso a array por índice
O(log n)
Logarítmica
Busca binária
O(n)
Linear
Busca sequencial
O(n log n)
Linearítmica
Merge Sort
O(n²)
Quadrática
Bubble Sort
O(n³)
Cúbica
Multiplicação de matrizes ingênua
O(2ⁿ)
Exponencial
Torres de Hanói
1O(1) — Constante
2O(log n) — Logarítmica
3O(n) — Linear
4O(n log n) — Linearítmica
5O(n²) — Quadrática
6O(n³) — Cúbica
7O(2ⁿ) — Exponencial
LEVEL · soulevel.com.br
Alternativa A — ❌ Incorreta
O(n²) representa a ordem quadrática. Embora seja uma complexidade comum, é maior que O(log n).
Alternativa B — ❌ Incorreta
O(n³) representa a ordem cúbica. Cresce ainda mais rápido que a quadrática, portanto não é a menor.
Alternativa C — ❌ Incorreta
O(n) representa a ordem linear. Embora seja menor que as polinomiais de grau superior, ainda é maior que a logarítmica para entradas grandes.
Alternativa D — ❌ Incorreta
O(cⁿ) (com c > 1) representa a ordem exponencial. É a maior entre as listadas, muito superior a O(log n).
Alternativa E — ✅ Correta ⟵ GABARITO
O(log n) representa a ordem logarítmica. É a menor complexidade dentre as opções, crescendo muito lentamente à medida que a entrada aumenta. Por exemplo, para n = 1.000.000, log₂(n) ≈ 20, enquanto n = 1.000.000.