Questão de Algoritmos e Estrutura de Dados — Algoritmos — FGV 2021
Algoritmos e Estrutura de Dados›Algoritmos
Código
fg045700
Banca
FGV
Órgão
TJ-RO
Ano
2021
Nível
Superior
Cargo
Analista Judiciário - Analista de Sistema - Desenvolvimento de Sistema
João precisa codificar uma função f(A), onde A é um array unidimensional de números inteiros, que deve retornar o maior valor armazenado em A.A complexidade de um algoritmo eficiente para a função f, para um array com n (n ≥ 1) elementos, deveria ser:
AO(1)
BO(log n)
CO(n)
DO(n log n)
EO(n²)
Revelar gabarito e comentário▾
GabaritoC — O(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: Busca do Máximo
Gabarito: letra C (O(n)). Para encontrar o maior valor em um array não ordenado, é necessário percorrer todos os elementos ao menos uma vez, resultando em complexidade linear O(n). Nenhum algoritmo pode fazer melhor que isso porque cada elemento precisa ser examinado.
A banca testa o conhecimento de complexidade para uma operação básica. O algoritmo mais eficiente para a função f(A) (maior valor de um array) é simples: percorrer o array, comparar e atualizar o máximo. Isso exige n comparações, portanto O(n). Vamos analisar cada alternativa:
1Percorrer todos os n elementos
2Comparar e atualizar o máximo
3Complexidade: O(n)
LEVEL · soulevel.com.br
Alternativa A — ❌ Incorreta
O(1) seria constante, independente do tamanho do array. Isso só seria possível se o maior valor já estivesse pré-calculado ou o array estivesse ordenado e acessássemos o último elemento, mas não há garantia.
Alternativa B — ❌ Incorreta
O(log n) é típico de algoritmos de busca binária, que exigem o array ordenado. O enunciado não afirma que o array está ordenado, portanto não é aplicável.
Alternativa C — ✅ Correta ⟵ GABARITO
O(n) é a complexidade da solução ótima: percorrer todos os n elementos uma única vez.
Alternativa D — ❌ Incorreta
O(n log n) é característico de algoritmos de ordenação eficientes (como Merge Sort ou Quick Sort). Ordenar para depois pegar o máximo seria ineficiente, pois o problema pede apenas o máximo, não a ordenação.
Alternativa E — ❌ Incorreta
O(n²) é típico de algoritmos como Bubble Sort (pior caso) ou força bruta comparando todos os pares. É muito pior que o necessário.
PEGA ESSA DICA!
Em análise de complexidade, sempre identifique o número de operações fundamentais (geralmente comparações ou acessos). Para encontrar o máximo em um array não ordenado, o mínimo teórico é n-1 comparações, portanto O(n). Se o array estivesse ordenado, seria O(1) (acessar o último elemento), mas isso não é informado.