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 é…
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
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 complexidade temporal assintótica desse algoritmo em função de n?
- A) A complexidade é cúbica, O(n³).
- B) A complexidade é linear, O(n).
- C) O(n²)
- D) A complexidade é logarítmica, O(log n).
- E) A complexidade é constante, O(1).
✅ Resposta correta: alternativa C
Resolução passo a passo
- Analise a estrutura do pseudocódigo. Há dois laços aninhados, um de i de 1 até n e outro de j de 1 até n, portanto o corpo do laço interno é executado n vezes para cada valor de i.
- Conte as execuções do bloco mais interno. Como i percorre n valores e, para cada um, j percorre n valores, o comando 'if A[i] == A[j]' é executado n x n = n^2 vezes.
- Verifique o custo do corpo do laço. A comparação entre A[i] e A[j] e, no caso verdadeiro, o incremento de count são operações de tempo constante, ou seja, cada uma custa O(1).
- Some os custos. O total é n^2 vezes O(1), que resulta em O(n^2), independentemente de quantas comparações sejam verdadeiras, pois o pior caso e o caso geral executam o mesmo número de iterações.
- Compare com as alternativas. A alternativa C, O(n^2), está correta. A alternativa A esta errada porque não há um terceiro laço aninhado que justifique n^3. A alternativa B esta errada porque um único laço daria O(n), mas aqui há dois laços aninhados. A alternativa D esta errada porque a complexidade logarítmica exigiria divisão do problema a cada passo, o que não ocorre. A alternativa E esta errada porque o custo cresce com n e não é constante.
💡 Dica: Analise a estrutura de repetição e a condição do if.
Alternativa por alternativa
O aluno pode ter contado um terceiro nível de repetição ou supôs que cada comparação dentro de dois laços gera outro laço, somando um fator n a mais.
Por que engana: Confundir a complexidade quadrática com a linear, acreditando que a comparação de elementos em um loop aninhado é O(n).
O aluno viu a variável n e associou o algoritmo a uma única varredura do vetor, ignorando que o laço interno também percorre n elementos a cada iteração do externo.
Existem dois laços aninhados que percorrem até n iterações cada; operações internas são O(1), resultando em tempo proporcional a n×n.
O aluno associou o algoritmo a buscas binárias ou a divisões sucessivas do problema, confundindo laços aninhados com estratégias de divisão e conquista.
O aluno pensou que, como a operação dentro do laço é simples, o algoritmo teria custo constante, esquecendo que essa operação é repetida n^2 vezes.
Raio-X da questão
complexidade temporal
avaliacao
análise de algoritmos · notação assintótica
Revisar conceitos de complexidade de algoritmos e notação assintótica.
Confundir a complexidade quadrática com a linear, acreditando que a comparação de elementos em um loop aninhado é O(n).
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 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…
- Se uma matriz n × n contém registros e um algoritmo compara cada par distinto de elementos para detectar duplicidade de…
- 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…
- 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…
🔎 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