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
- Projete um algoritmo em pseudocódigo que receba uma lista de nomes (strings) como dado de entrada e devolva uma lista de…
- Um algoritmo compara cada par distinto de n elementos (dois laços aninhados com i<j). Em função de n, quantas…
- Considere um algoritmo que para cada um dos N elementos de um vetor executa, no pior caso, uma busca linear sobre M…
- Um algoritmo percorre uma lista de n elementos com dois loops aninhados: para i de 1 a n: para j de 1 a n: executar…
- Para um algoritmo que percorre um vetor dados de tamanho N verificando cada elemento até achar um alvo, qual a…
- Na aula de Computação, Pedro precisa organizar uma lista quase ordenada de nomes em pseudocódigo. Qual algoritmo…
🔎 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