Num algoritmo de ordenação que usa dois índices em laços aninhados para percorrer um vetor de N nomes, como a…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Identificar o comportamento dos algoritmos no que diz respeito ao consumo de recursos como tempo de execução, espaço de memória e energia, entre outros.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Num algoritmo de ordenação que usa dois índices em laços aninhados para percorrer um vetor de N nomes, como a variável N influencia a complexidade temporal?
- A) O algoritmo se torna mais eficiente com aumento de N.
- B) A complexidade temporal cresce aproximadamente como o quadrado de N, ou seja O(N^2).
- C) A complexidade é linear, O(N), devido ao uso de dois índices.
- D) A complexidade não é afetada pela quantidade de nomes no vetor.
- E) Se N for pequeno, a complexidade se torna O(1).
✅ Resposta correta: alternativa B
Resolução passo a passo
- Um algoritmo de ordenação com dois laços aninhados percorre o vetor de N nomes: o laço externo executa cerca de N vezes e, para cada uma dessas vezes, o laço interno percorre até cerca de N elementos.
- Assim, o número total de comparações e trocas é aproximadamente N vezes N, isto é, N^2 (com constantes e termos menores que são desprezados na notação assintótica).
- Portanto, a complexidade temporal cresce aproximadamente com o quadrado de N, sendo representada por O(N^2). Essa é a alternativa B, que coincide com o gabarito oficial.
- A alternativa A está errada, pois o algoritmo não fica mais eficiente quando N aumenta; ao contrário, o tempo de execução cresce com N.
- A alternativa C está errada, pois dois laços aninhados não geram complexidade linear; o uso de dois índices aninhados multiplica o trabalho, resultando em quadrático.
- A alternativa D está errada, pois o número de nomes é justamente o fator que determina quantas operações são feitas.
- A alternativa E está errada, pois O(1) significa tempo constante, o que não se aplica a laços aninhados sobre o vetor, mesmo que N seja pequeno; para N pequeno o tempo é apenas menor, não constante.
💡 Dica: Considere a relação entre N e a quantidade de comparações feitas.
Alternativa por alternativa
O aluno acredita que, por haver mais dados, o algoritmo ganha eficiência, confundindo o tamanho da entrada com a melhoria de desempenho.
Laços aninhados realizam cerca de N×N iterações (mais precisamente N(N-1)/2 comparações em muitas ordenações simples), resultando em comportamento quadrático à medida que N aumenta.
O aluno associa a presença de dois índices a uma complexidade linear, sem perceber que os laços estão aninhados e se multiplicam em vez de somar.
Por que engana: Confundir a complexidade quadrática com a linear, acreditando que o uso de dois índices não afeta a complexidade temporal.
O aluno supõe que o número de elementos não altera o trabalho do algoritmo, talvez por não relacionar o número de iterações ao tamanho do vetor.
O aluno confunde algoritmo de tempo constante com redução do tempo para valores pequenos de N, achando que a complexidade passa a ser O(1) quando a entrada é pequena.
Raio-X da questão
complexidade temporal
avaliacao
complexidade de algoritmos · laços aninhados
Revisar conceitos de algoritmos e complexidade de tempo.
Confundir a complexidade quadrática com a linear, acreditando que o uso de dois índices não afeta a complexidade temporal.
ciencia_tecnologia
pensamento_critico
cientifico
Questões parecidas com resolução
- Em um projeto de monitoramento de rios, uma boia computacional organiza leituras de sensores antes de enviá-las por…
- Uma biblioteca escolar recebeu caixas de livros doados para uma feira de troca. Para registrar os exemplares, a equipe…
- Um centro cultural público oferece inscrições on-line para atividades com critérios variados. Na oficina de teatro…
- Uma escola está testando dois protótipos de aplicativo para que estudantes consultem mudanças de sala, horários e…
- Uma secretaria municipal de educação está digitalizando pedidos de transporte escolar e de atendimento em contraturno…
- — O cartaz não pode sair duas vezes, pois a feira começa em uma hora — alertou a coordenadora do centro cultural. No…
🔎 Procurar outra questão
Procure no banco do GeraProva pelo tema ou por um trecho do enunciado. Cada questão já vem com resolução comentada e a análise de cada alternativa.
Professor: monte a prova com questões como esta, com gabarito e folha de respostas, em 30 segundos. Ver planos · Blog