Qual é a complexidade temporal, em notação O, do algoritmo clássico que multiplica duas matrizes quadradas n×n…
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, do algoritmo clássico que multiplica duas matrizes quadradas n×n usando três loops aninhados (operações de soma e produto)?
- A) O(n^4), pois cada loop adiciona complexidade.
- B) O(n^3)
- C) O(n), já que é uma operação simples de multiplicação.
- D) O(log n), pois as matrizes são divididas a cada iteração.
- E) O(n^2), pois apenas duas dimensões são multiplicadas.
✅ Resposta correta: alternativa B
Resolução passo a passo
- Identifique a estrutura do algoritmo. A multiplicação clássica de duas matrizes n×n usa três loops aninhados: um para a linha i da primeira matriz, um para a coluna j da segunda e um para o índice k que percorre a soma do produto escalar entre a linha e a coluna.
- Conte as operações executadas no loop mais interno. Para cada par (i, j), o loop k executa n somas e n produtos, ou seja, cerca de 2n operações elementares.
- Multiplique pelas repetições dos loops externos. Há n valores para i e n valores para j, totalizando n^2 pares. Logo o número total de operações é n^2 × n = n^3 (multiplicado por uma constante 2, que é desprezada na notação O).
- Conclua. A complexidade temporal é O(n^3), alternativa B, que coincide com o gabarito oficial.
- Analise as alternativas erradas. A alternativa A (n^4) superestima, pois não há um quarto loop aninhado. A alternativa C (O(n)) confunde a operação individual de multiplicação com o número total de operações do algoritmo. A alternativa D (O(log n)) corresponde a algoritmos de divisão e conquista, que não são o método clássico. A alternativa E (O(n^2)) conta apenas os pares (i, j) e ignora o loop de soma interno.
💡 Dica: Considere a definição de complexidade temporal em algoritmos.
Alternativa por alternativa
O aluno acredita que cada loop aninhado multiplica a complexidade por um fator extra, somando expoentes de forma indevida, e conclui que três loops produzem n^4.
Por que engana: Confundir a complexidade de multiplicação de matrizes com operações mais simples, como soma ou multiplicação de números individuais.
O método clássico executa, para cada uma das n^2 posições do produto, uma soma sobre n multiplicações, resultando em crescimento proporcional a n·n·n = n^3.
O aluno confunde o custo de uma única operação aritmética com o custo total do algoritmo, ignorando que os loops repetem essas operações n^3 vezes.
O aluno associa qualquer divisão do problema a logaritmo, aplicando a ideia de algoritmos de divisão e conquista (como busca binária) a um método que não divide as matrizes.
O aluno considera apenas as dimensões das matrizes (duas) e ignora o loop de soma interno, que percorre o índice k e acrescenta mais um fator n.
Raio-X da questão
complexidade temporal
avaliacao
notação O · algoritmos de multiplicação
Revisar a notação O e a multiplicação de matrizes.
Confundir a complexidade de multiplicação de matrizes com operações mais simples, como soma ou multiplicação de números individuais.
ciencia_tecnologia
pensamento_critico
abstrato
Questões parecidas com resolução
- 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…
- 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…
- 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…
🔎 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