Em um grafo não direcionado representado por uma matriz de adjacência, qual é a complexidade em espaço…
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
Em um grafo não direcionado representado por uma matriz de adjacência, qual é a complexidade em espaço (variável de memória) em função de n vértices?
- A) O espaço é T(n²).
- B) O espaço é T(n).
- C) O espaço depende do número de arestas apenas.
- D) O espaço é T(n log n).
- E) O espaço é T(n³).
✅ Resposta correta: alternativa A
Resolução passo a passo
- Uma matriz de adjacência de um grafo com n vértices é uma tabela n por n, em que cada posição (i, j) guarda 1 ou 0 (ou o peso) indicando se existe aresta entre os vértices i e j. Passo 2: Como a tabela tem n linhas e n colunas, ela contém n x n = n^2 posições, independentemente de quantas arestas existem. Passo 3: Portanto o espaço ocupado é T(n^2), o que corresponde à alternativa A. Passo 4: A alternativa B está errada porque T(n) seria o espaço de uma estrutura com uma posição por vértice, como um vetor de graus, e não a matriz inteira. Passo 5: A alternativa C está errada porque a matriz sempre ocupa n^2 posições, mesmo que o grafo tenha poucas arestas; apenas a lista de adjacência depende de arestas, com espaço T(n + m). Passo 6: A alternativa D está errada porque n log n é típico de algoritmos de ordenação e não da estrutura de uma matriz. Passo 7: A alternativa E está errada porque n^3 não corresponde ao armazenamento da matriz, e sim, por exemplo, ao custo de multiplicar duas matrizes n por n de forma ingênua. Passo 8: O gabarito oficial A está correto, pois a análise independente leva à mesma resposta.
💡 Dica: Considere a definição de matriz de adjacência para grafos.
Alternativa por alternativa
A matriz de adjacência armazena uma entrada para cada par de vértices, totalizando n×n posições, independente do número de arestas.
O aluno assume que a memória cresce linearmente com o número de vértices, como em um vetor, esquecendo que a matriz guarda a relação entre cada par de vértices.
O aluno confunde a matriz de adjacência com a lista de adjacência, cujo espaço de fato depende do número de arestas, e aplica essa propriedade à matriz.
Por que engana: Confundir a complexidade em espaço de uma matriz de adjacência com a complexidade em espaço de outras representações de grafos, como listas de adjacência.
O aluno associa a complexidade de espaço a uma função de algoritmos de ordenação ou a estruturas hierárquicas, sem relacionar à forma de armazenar o grafo.
O aluno pensa que a matriz exige estrutura cúbica, talvez confundindo o espaço com o tempo de operações como a multiplicação de matrizes.
Raio-X da questão
complexidade em espaço
avaliacao
matriz de adjacência · complexidade de algoritmos
Revisar a representação de grafos e suas complexidades em espaço.
Confundir a complexidade em espaço de uma matriz de adjacência com a complexidade em espaço de outras representações de grafos, como listas de adjacência.
ciencia_tecnologia
pensamento_critico
abstrato
Questões parecidas com resolução
- Para um grafo não direcionado e esparso com N vértices e E arestas, qual representação em um programa consome menos…
- Considerando um grafo com n vértices e m arestas que representa conexões entre pontos de coleta de dado, qual…
- Para um grafo esparso com número muito maior de vértices do que de arestas, qual representação de arestas é mais…
- Numa rede de ônibus municipal modelada como grafo esparso, qual representação costuma usar menos memória: lista de…
- Para otimizar espaço em uma rede grande e esparsa, qual estrutura de dados é preferível: matriz de adjacência ou lista…
- Para modelar conexões entre usuários em uma rede social com milhões de usuários e grau médio pequeno, qual representação…
🔎 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