Se uma matriz n × n contém registros e um algoritmo compara cada par distinto de elementos para detectar…
Publicado por Alexandre Lombardi dos Santos, fundador do GeraProva
Criar soluções de problemas para os quais seja adequado o uso de registros e matrizes unidimensionais para descrever suas informações e automatizá-las usando uma linguagem de programação.
Fonte: Base Nacional Comum Curricular (MEC).Questão
Se uma matriz n × n contém registros e um algoritmo compara cada par distinto de elementos para detectar duplicidade de um campo 'id', qual é a complexidade temporal em função de n?
- A) Complexidade temporal é O(2^n) por conta de um algoritmo exponencial necessário.
- B) O(n^4), pois são n^2 elementos e a comparação par a par leva ~ (n^2)^2 operações.
- C) Complexidade é O(n) pois cada elemento é verificado uma vez.
- D) A complexidade é O(n^2) porque compara apenas elementos adjacentes.
- E) É O(n^3) considerando que três elementos são necessários para a comparação.
✅ Resposta correta: alternativa B
Resolução passo a passo
- A matriz n x n tem n^2 registros no total, então o número de elementos é N = n^2. Passo 2: Um algoritmo que compara cada par distinto de elementos faz uma comparação para cada combinação de dois elementos diferentes, ou seja, N(N-1)/2 comparações. Passo 3: Substituindo N por n^2, temos (n^2)(n^2-1)/2, que é aproximadamente n^4/2. Passo 4: Em notação O, constantes como 1/2 são descartadas e o termo dominante é n^4, logo a complexidade é O(n^4). Passo 5: A alternativa B está correta e coincide com o gabarito oficial. Por que as outras estão erradas: A usa crescimento exponencial, que não surge em comparações de pares; C supõe que cada elemento é verificado uma única vez, mas cada um precisa ser comparado com os demais; D considera só elementos adjacentes, o que não corresponde a comparar todos os pares distintos; E associa o custo a triplas de elementos, o que não é o que o enunciado descreve.
💡 Dica: Considere a definição de complexidade temporal para algoritmos de comparação.
Alternativa por alternativa
Confunde comparação de pares com a exploração de todos os subconjuntos dos elementos, que cresce exponencialmente. Pensa que o algoritmo precisa testar combinações de qualquer tamanho.
Número de elementos = n^2; comparações entre todos os pares é proporcional ao quadrado desse total, resultando em n^4.
Acredita que basta percorrer a lista uma única vez para detectar duplicidade. Ignora que cada elemento precisa ser comparado com todos os outros para descobrir repetições.
Lê 'cada par distinto' como 'pares de elementos vizinhos', como em uma verificação após ordenação. Além disso, considera apenas n^2 comparações sem levar em conta que há N elementos, cada um comparado com os demais.
Por que engana: Confundir a quantidade de comparações necessárias, levando a uma estimativa errada da complexidade temporal.
Associa o número de comparações ao número de elementos envolvidos em cada comparação, supondo que três elementos definem o custo. Não percebe que a comparação é feita entre dois elementos, e o total depende do número de pares.
Raio-X da questão
complexidade temporal
avaliacao
complexidade de algoritmos · análise de algoritmos
Revisar conceitos de complexidade de algoritmos e análise de desempenho.
Confundir a quantidade de comparações necessárias, levando a uma estimativa errada da complexidade temporal.
ciencia_tecnologia
pensamento_critico
abstrato
Questões parecidas com resolução
- 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…
- Um algoritmo aninhado percorre uma matriz M de tamanho n×n com dois loops: para i de 1 até n e para j de 1 até n. Se a…
- Um algoritmo compara cada par distinto de n elementos (dois laços aninhados com i<j). Em função de n, quantas…
- Qual é a complexidade temporal, em notação O, de um algoritmo que percorre todos os elementos de uma matriz de dimensã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…
Todas as questões de Programação - Programação usando registros e matrizes
🔎 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