Qual é a complexidade temporal para acessar diretamente um elemento matriz[i][j] em um algoritmo que usa…
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 para acessar diretamente um elemento matriz[i][j] em um algoritmo que usa índices válidos para a matriz?
- A) O(n^2) pois é necessário percorrer toda matriz para acessar um elemento.
- B) Tempo constante: O(1).
- C) O(log n) devido à busca binária necessária para encontrar o elemento.
- D) O(n) porque cada elemento deve ser verificado sequencialmente.
- E) A complexidade é O(n^3) por conta das múltiplas dimensões da matriz.
✅ Resposta correta: alternativa B
Resolução passo a passo
- Em uma matriz armazenada em memória contígua (ou acessada por um vetor de vetores), o endereço de matriz[i][j] é calculado diretamente a partir do índice da linha, do índice da coluna e do endereço base, com uma quantidade fixa de operações aritméticas e de acesso à memória.
- Como o número de operações não depende do tamanho n da matriz, o acesso direto a um elemento tem complexidade temporal constante, O(1).
- Por isso a alternativa B está correta e coincide com o gabarito oficial.
- A alternativa A está errada, pois acessar um elemento não exige percorrer a matriz inteira; isso só ocorre em operações como busca ou impressão de todos os elementos.
- A alternativa C está errada, pois a busca binária não é necessária para acessar uma posição cujos índices já são conhecidos, e ela exigiria dados ordenados.
- A alternativa D está errada, pois a verificação sequencial de todos os elementos só seria necessária se estivéssemos procurando um valor, não acessando uma posição específica.
- A alternativa E está errada, pois as múltiplas dimensões de uma matriz bidimensional são acessadas com dois índices diretos, sem gerar complexidade cúbica.
💡 Dica: Considere a definição de complexidade temporal em algoritmos.
Alternativa por alternativa
O aluno acredita que, para acessar uma posição específica, é preciso percorrer toda a matriz, confundindo acesso direto com busca.
Por que engana: Confundir a complexidade de acesso direto com a necessidade de percorrer a matriz inteira, levando a uma resposta incorreta.
Acesso por índice refere-se diretamente ao endereço do elemento na memória e não depende do tamanho da matriz.
O aluno associa qualquer localização de elemento à busca binária, sem perceber que a busca binária só se aplica a dados ordenados e que aqui os índices já são conhecidos.
O aluno confunde acessar uma posição conhecida com procurar um valor, imaginando que cada elemento precisa ser verificado em sequência.
O aluno supõe que cada dimensão adicional multiplica o custo de forma cúbica, quando na verdade cada índice é usado diretamente em um cálculo de endereço de custo fixo.
Raio-X da questão
complexidade temporal
avaliacao
acesso a elementos de matriz · complexidade de algoritmos
Revisar conceitos de complexidade de algoritmos e acesso a matrizes.
Confundir a complexidade de acesso direto com a necessidade de percorrer a matriz inteira, levando a uma resposta incorreta.
ciencia_tecnologia
tomada_decisao
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 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…
- Em um algoritmo que armazena uma matriz de registros 'tab' em um vetor linear em row-major com n colunas, qual fórmula…
- Em uma matriz, como podemos acessar o elemento localizado na primeira linha e segunda coluna?
- Assinale a alternativa que representa uma maneira de acessar um elemento de uma matriz em programação.
- Em um algoritmo que percorre uma matriz de registros 'matrizDados' usando variáveis índice i e j para acessar elementos…
🔎 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