Questão de Algoritmos e Estrutura de Dados — Algoritmos — FUMARC 2018
Algoritmos e Estrutura de Dados›Algoritmos
Código
qq343163
Banca
FUMARC
Órgão
Câmara de Carmo do Cajuru - MG
Ano
2018
Nível
Superior
Cargo
Analista de Sistemas e Suporte
Função de complexidade de algoritmos, cujo tempo de execução ocorre tipicamente em algoritmos que resolvem um problema quebrando-o em problemas menores, resolvendo cada um deles independentemente e, depois, ajuntando as soluções:
Af(n) = O ( log n ).
Bf(n) = O ( n ).
Cf(n) = O ( n log n ).
Df(n) = O ( n²).
Revelar gabarito e comentário▾
GabaritoC — f(n) = O ( n 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: Divisão e Conquista
Gabarito: letra C. A descrição do enunciado — "quebrar o problema em problemas menores, resolver cada um independentemente e depois ajuntar as soluções" — é a definição clássica do paradigma divisão e conquista. Algoritmos como Merge Sort, Quick Sort (caso médio) e Binary Search seguem essa estratégia, e sua complexidade de tempo típica é O(n log n).
Divisão e conquista: Estratégia (Quebrar em subproblemas menores, Resolver cada independentemente, Combinar as soluções); Complexidade típica (O(n log n)); Exemplos (Merge Sort, Quick Sort (caso médio), Heap Sort)
Análise das alternativas
Alternativa A — ❌ Incorreta
f(n) = O(log n). Essa complexidade aparece em algoritmos que reduzem o problema pela metade a cada passo sem processar todos os elementos, como a busca binária. Porém, não envolve "ajuntar soluções" de múltiplos subproblemas — apenas descarta metade dos dados.
Alternativa B — ❌ Incorreta
f(n) = O(n). Corresponde a algoritmos que percorrem todos os elementos uma única vez (ex.: busca linear, soma de elementos). Não há quebra recursiva em subproblemas.
Alternativa C — ✅ Correta ⟵ GABARITO
f(n) = O(n log n). É a complexidade típica dos algoritmos de divisão e conquista em que o problema é dividido em duas metades (ou mais) e cada metade é resolvida recursivamente, com a combinação das soluções custando O(n). A recorrência T(n) = 2T(n/2) + O(n) resolve para O(n log n). Exemplos: Merge Sort, Quick Sort (caso médio), Heap Sort.
Alternativa D — ❌ Incorreta
f(n) = O(n²). Aparece em algoritmos com laços aninhados que percorrem todos os pares (ex.: Bubble Sort, Selection Sort). Não é característico da abordagem descrita.
PEGA ESSA DICA!
Na hora da prova, associe "dividir para conquistar" com O(n log n), e lembre que a notação O é a cota superior (pior caso, a menos que especificado médio). Para algoritmos de ordenação por comparação, O(n log n) é o limite inferior no pior caso.