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
- 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…
- Considere um algoritmo com duas estruturas de repetição aninhadas, cada uma iterando de 1 até n. Qual é a complexidade…
- Considere o algoritmo: contador := 0; para i de 1 até n passo 2 faça contador := contador + 1; fim para. Em termos de n…
- Se uma matriz n × n contém registros e um algoritmo compara cada par distinto de elementos para detectar duplicidade de…
- Considere o pseudocódigo: for i from 1 to n: for j from 1 to n: if A[i] == A[j] then count ? count + 1. Qual é a…
- Considere o pseudocódigo: total := 0; para i de 1 até n faça para j de 1 até i faça total := total + 1; fim para; fim…
🔎 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