Pular para o conteúdo principal

Questão de Algoritmos e Estrutura de Dados — Algoritmos — CESGRANRIO 2024

Algoritmos e Estrutura de DadosAlgoritmos
Código
cg020773
Banca
CESGRANRIO
Órgão
BNDES
Ano
2024
Nível
Superior
Cargo
Analista - Análise de Sistemas - Desenvolvimento (Manhã)
Considere os seguintes algoritmos, todos com complexidade assintótica O(n):Algoritmo 1: executa uma iteração simples sobre uma lista de tamanho n.Algoritmo 2: executa duas iterações simples sobre uma lista de tamanho n, uma após a outra.Algoritmo 3: executa uma iteração simples sobre uma lista de tamanho n, mas a iteração interna realiza uma operação constante que leva t_C tempo.Algoritmo 4: executa uma iteração sobre uma lista de tamanho n e, dentro dessa iteração, realiza uma operação constante k vezes, em que o tempo total das operações é k * t_D e(k * t_D > t_C).Algoritmo 5: executa uma iteração simples sobre uma lista de tamanho n, mas a iteração interna realiza uma operação com complexidade O(1).Qual dos algoritmos é menos eficiente em termos de tempo de execução, embora todos tenham a mesma complexidade assintótica O(n)?
  1. AAlgoritmo 1
  2. BAlgoritmo 2
  3. CAlgoritmo 3
  4. DAlgoritmo 4
  5. EAlgoritmo 5
Revelar gabarito e comentário

GabaritoD — Algoritmo 4

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: Eficiência Prática vs. Assintótica

Gabarito: letra D. O Algoritmo 4 é o menos eficiente em termos de tempo de execução real, pois, embora todos sejam O(n), ele possui o maior fator constante por iteração: realiza k operações constantes por elemento, com k * t_D > t_C, onde t_C é o tempo da operação do Algoritmo 3.

A questão testa a diferença entre complexidade assintótica e desempenho concreto: dois algoritmos O(n) podem ter tempos de execução muito diferentes devido aos fatores constantes.

Alternativa A — ❌ Incorreta

Algoritmo 1 executa uma única iteração simples. É o mais eficiente, com menor fator constante.

Alternativa B — ❌ Incorreta

Algoritmo 2 executa duas iterações inteiras, totalizando 2n operações. Embora tenha fator constante 2, ainda é menor que o fator k * t_D do Algoritmo 4 (pois k pode ser grande e t_D significativo).

Alternativa C — ❌ Incorreta

Algoritmo 3 executa uma iteração com operação constante t_C por elemento. Como k * t_D > t_C, o Algoritmo 4 é menos eficiente.

Alternativa D — ✅ Correta ⟵ GABARITO

Algoritmo 4 realiza, para cada um dos n elementos, k operações constantes (cada uma com tempo t_D). O total é n * k * t_D, e o enunciado garante que k * t_D > t_C. Portanto, é o que tem maior tempo de execução entre os cinco.

Alternativa E — ❌ Incorreta

Algoritmo 5 executa uma iteração com uma operação O(1) por elemento, equivalente ao Algoritmo 1. Eficiência similar a Algoritmo 1, sendo mais rápido que Algoritmo 4.

NÃO CAIA NESSA!

A banca explora a confusão entre complexidade assintótica e eficiência prática. O aluno pode pensar que "duas iterações" (algoritmo 2) é pior, mas o enunciado especifica que o algoritmo 4 tem fator k * t_D maior que t_C, tornando-o o menos eficiente.

Gabarito: letra D

Link permanente: /questoes/cg020773