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 sistema portátil registra a corrente gerada em um eletrodo de trabalho durante um pulso de 4 segundos. Para comparar…
- Em um protótipo computacional que monitora a salinidade de um tanque, dois eletrodos ficam imersos na água e são usados…
- Em uma lavanderia, uma pessoa instala dois eletrodos próximos ao piso, ligados a uma entrada digital de um controlador…
- Em uma demonstração de interface cérebro-computador, eletrodos colocados sobre o couro cabeludo captam sinais elétricos…
- Em um protótipo de interface computacional controlada por sinais musculares, cada canal utiliza um eletrodo para captar…
- Em uma prótese controlada por sinais musculares, eletrodos na pele captam a atividade elétrica e a enviam ao sistema…
🔎 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