Um algoritmo compara cada par distinto de n elementos (dois laços aninhados com i<j). Em função de n, quantas…
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
Um algoritmo compara cada par distinto de n elementos (dois laços aninhados com i<j). Em função de n, quantas comparações esse algoritmo realiza?
- A) n^2 comparações, pois cada elemento é comparado com todos.
- B) n(n + 1) comparações, considerando laços aninhados.
- C) n! comparações, já que todos os elementos precisam ser comparados.
- D) 2n comparações, já que são dois laços aninhados.
- E) n(n - 1) / 2 comparações
✅ Resposta correta: alternativa E
Resolução passo a passo
- O enunciado diz que o algoritmo compara cada par distinto de n elementos usando dois laços aninhados com i<j. Isso significa que a comparação ocorre apenas quando i é menor que j, ou seja, cada par (i, j) aparece uma única vez.
- Contando os pares distintos: para i = 1, j varia de 2 a n, o que dá n-1 comparações; para i = 2, há n-2; e assim por diante, até i = n-1, com 1 comparação. A soma é (n-1) + (n-2) + ... + 1 = n(n-1)/2.
- Assim, o número de comparações é n(n - 1) / 2, que corresponde à alternativa E. Resolvi isso por conta própria e o resultado confirma o gabarito oficial.
- Por que as outras estão erradas: A) n^2 contaria também pares repetidos e pares de um elemento com ele mesmo, o que não ocorre com i<j; B) n(n+1) é ainda maior e não corresponde à restrição i<j; C) n! cresce muito mais rápido que o número de pares; D) 2n é linear e não representa a quantidade de pares distintos.
💡 Dica: Considere a fórmula para combinações de n elementos.
Alternativa por alternativa
Acredita que cada elemento é comparado com todos os outros, incluindo a si mesmo e os pares repetidos, ignorando a condição i<j que elimina repetições.
Por que engana: Confundir o número de comparações com a soma total de elementos, levando a uma contagem errada das comparações realizadas.
Acha que os laços aninhados com j começando em i+1 ou n somam uma unidade extra, multiplicando n por (n+1) sem considerar a restrição de pares distintos.
Confunde comparar pares com considerar todas as permutações dos elementos, usando fatorial como se cada ordem fosse uma comparação diferente.
Associa o número de laços ao número de comparações, achando que dois laços geram um total linear proporcional a 2n, sem analisar quantas combinações de pares são formadas.
Cada par distinto de n elementos corresponde à combinação C(n,2) = n(n-1)/2, que conta todas as comparações com i<j.
Raio-X da questão
comparações em algoritmos
avaliacao
laços aninhados em algoritmos · combinatória básica
Revisar a análise de complexidade de algoritmos.
Confundir o número de comparações com a soma total de elementos, levando a uma contagem errada das comparações realizadas.
ciencia_tecnologia
pensamento_critico
abstrato
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