Qual é a complexidade temporal, em notação O, de um algoritmo que percorre todos os elementos de uma matriz de…
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
Qual é a complexidade temporal, em notação O, de um algoritmo que percorre todos os elementos de uma matriz de dimensão N×M exatamente uma vez?
- A) O(N+M)
- B) O(N×M)
- C) O(N*M^2)
- D) O(log(N×M))
- E) O(N^2)
✅ Resposta correta: alternativa B
Resolução passo a passo
- Entenda o que a questão pede. Um algoritmo percorre todos os elementos de uma matriz N×M exatamente uma vez, ou seja, ele visita cada célula uma única vez, sem repetições. Passo 2: Conte quantas operações são necessárias. A matriz tem N×M elementos no total, e se cada elemento exige uma quantidade constante de trabalho (ler, comparar, somar), o número total de operações é proporcional a N×M. Passo 3: Expresse isso em notação O. Como o custo cresce linearmente com o número de células, a complexidade é O(N×M). Passo 4: Verifique as alternativas. A alternativa B, O(N×M), é a correta, pois descreve exatamente o crescimento proporcional ao número total de elementos. A alternativa A, O(N+M), está errada porque soma as dimensões em vez de multiplicá-las; isso só descreveria um percurso só por linhas e colunas, não por todas as células. A alternativa C, O(N*M^2), está errada porque há um termo M^2 que não existe em um percurso simples com uma visita por elemento. A alternativa D, O(log(N×M)), está errada porque logaritmo indica redução pela metade a cada passo, como na busca binária, o que não ocorre ao percorrer todos os elementos. A alternativa E, O(N^2), está errada porque supõe que N seja a única dimensão relevante e eleva ao quadrado sem motivo, já que o M não aparece. Passo 5: Conclusão. Como o algoritmo visita cada um dos N×M elementos exatamente uma vez com custo constante, a resposta correta é a B, concordando com o gabarito oficial.
💡 Dica: Considere a quantidade total de elementos na matriz.
Alternativa por alternativa
O aluno soma as dimensões da matriz, imaginando que basta percorrer uma linha e uma coluna, em vez de todas as células. Confunde o percurso de uma linha com a visita a todos os elementos.
Por que engana: Confundir a complexidade de percorrer uma matriz com a de operações em listas unidimensionais, subestimando o número total de elementos.
O algoritmo visita cada um dos N×M elementos uma única vez; assim o tempo cresce proporcionalmente ao número total de elementos.
O aluno acredita que o M aparece elevado ao quadrado, talvez por confundir com algoritmos de dupla varredura aninhada sobre as colunas. Não percebe que cada elemento é visitado apenas uma vez.
O aluno associa qualquer algoritmo que trabalha com matrizes a logaritmo, lembrando de buscas binárias ou árvores. Não nota que percorrer todos os elementos não divide o problema pela metade a cada passo.
O aluno considera que a complexidade de matrizes é sempre quadrática, aplicando N^2 por intuição, sem olhar para as dimensões N e M da questão. Ignora o M e aplica um padrão de matriz quadrada a uma matriz genérica.
Raio-X da questão
complexidade temporal
avaliacao
notação O · matrizes em algoritmos
Revisar conceitos de complexidade de algoritmos e notação O.
Confundir a complexidade de percorrer uma matriz com a de operações em listas unidimensionais, subestimando o número total de elementos.
ciencia_tecnologia
pensamento_critico
abstrato
Questões parecidas com resolução
- Qual é a complexidade temporal, em notação O, do algoritmo clássico que multiplica duas matrizes quadradas n×n usando…
- 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…
- Considere um algoritmo que para cada um dos N elementos de um vetor executa, no pior caso, uma busca linear sobre M…
- 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…
- Qual é a complexidade temporal para acessar diretamente um elemento matriz[i][j] em um algoritmo que usa índices válidos…
- Considere um algoritmo com duas estruturas de repetição aninhadas, cada uma iterando de 1 até n. Qual é a complexidade…
🔎 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