Módulo 02 Estruturas Sequenciais

Matrizes e Organização Bidimensional

Uma matriz organiza elementos em linhas e colunas, criando uma visão bidimensional muito útil para tabelas, imagens, mapas, tabuleiros e problemas matemáticos. Entretanto, a memória do computador continua sendo essencialmente linear. Nesta aula, vamos entender como uma matriz bidimensional é transformada em uma sequência de endereços, como acessar m[i][j] em O(1) e como os diferentes percursos alteram a forma como os dados são visitados.

Objetivo 01Entender linhas e colunas
Objetivo 02Visualizar a memória linear
Objetivo 03Analisar percursos e custos
01

Do vetor para duas dimensões

O Que é uma Matriz?

Uma matriz é uma estrutura sequencial que organiza elementos em linhas e colunas. Cada elemento é identificado por um par de índices, normalmente escrito como matriz[linha][coluna].

Duas Dimensões

O índice deixa de ser apenas i e passa a ser um par: linha e coluna.

Ordem definida

Cada posição possui uma localização lógica precisa dentro da grade.

Acesso O(1)

Conhecendo linha e coluna, podemos calcular diretamente a posição linear.

Memória linear

A grade é uma abstração; por baixo, os elementos precisam ser representados na memória.

Modelo mental: uma matriz 3×4 possui 3 linhas, 4 colunas e portanto 3 × 4 = 12 elementos.
O primeiro índice representa a linha

Em m[2][3], o valor 2 identifica a linha e o valor 3 identifica a coluna. Se os índices começam em zero, estamos falando da terceira linha e da quarta coluna.

Matriz é um vetor de vetores?

Conceitualmente, essa é uma forma útil de pensar. Entretanto, a representação física depende da estrutura utilizada. Um array bidimensional tradicional em C++ é armazenado de maneira contígua por linhas. Já um std::vector<std::vector<int>> é formado por vetores internos independentes e não garante um único bloco contíguo para toda a matriz.

Onde matrizes aparecem?

Imagens digitais, tabuleiros de jogos, mapas, matrizes de adjacência de grafos, tabelas numéricas, transformações geométricas, programação dinâmica e inúmeros algoritmos científicos utilizam estruturas matriciais.

02

Da coordenada para o endereço

Como Acessar matriz[i][j] Diretamente?

Para encontrar uma célula, precisamos transformar duas coordenadas em uma posição linear. Em armazenamento por linhas (row-major), primeiro vêm todas as colunas da linha 0, depois as da linha 1, depois as da linha 2 e assim por diante.

Para uma matriz com C colunas:

índice linear = linha × C + coluna
endereço = base + índice_linear × tamanho_do_elemento
Laboratório de endereçamento matricial
Clique em uma célula para calcular sua posição linear e endereço.
03

A grade é uma abstração

Linearização da Matriz

A matriz é visualizada como uma grade, mas em uma representação contígua cada linha é colocada imediatamente após a anterior. Esse processo pode ser entendido como uma linearização da matriz.

Visão bidimensional — 3 × 4

10111213 20212223 30313233

Memória linear — row-major

10111213 20212223 30313233
Em C e C++, arrays multidimensionais tradicionais utilizam row-major order: os elementos de uma mesma linha aparecem consecutivamente na memória.
Row-major

Primeiro armazenamos todas as colunas da linha 0, depois todas as colunas da linha 1 e assim por diante. C e C++ seguem esse padrão para arrays multidimensionais tradicionais.

Column-major

Outra possibilidade é armazenar primeiro todos os elementos da coluna 0, depois da coluna 1 e assim por diante. Algumas linguagens e bibliotecas científicas utilizam essa estratégia. A fórmula de endereçamento muda conforme o layout.

04

Dois laços, diferentes ordens

Percorrendo uma Matriz

Uma matriz normalmente é percorrida com dois laços: um controla as linhas e outro controla as colunas. Se a matriz possui L linhas e C colunas, visitar todos os elementos exige L × C acessos.

Simulador de percurso

Compare a ordem em que as células são visitadas. Para uma matriz row-major, percorrer por linhas segue naturalmente a ordem física dos elementos na memória.

Células visitadas 0
Posição atual —
Escolha um tipo de percurso para iniciar.
Percurso completo é O(L × C)

Se todas as células precisam ser visitadas, o algoritmo executa uma operação para cada uma das L × C posições. Em uma matriz quadrada n × n, isso é frequentemente escrito como O(n²).

Por linhas e por colunas têm o mesmo Big O

Ambos percorrem a mesma quantidade de elementos e portanto possuem a mesma ordem assintótica. Entretanto, em uma matriz contígua row-major, percorrer por linhas costuma apresentar melhor localidade de memória e pode aproveitar melhor o cache.

Buscar valor em uma matriz não ordenada

Sem uma propriedade adicional de ordenação ou uma estrutura auxiliar, no pior caso precisamos testar todas as L × C células.

05

Resumo de custo

Complexidade das Operações

Operação Complexidade Explicação
Acessar m[i][j] O(1) A posição linear é calculada diretamente.
Alterar m[i][j] O(1) Mesmo princípio do acesso direto.
Percorrer toda matriz O(L × C) Todas as células são visitadas uma vez.
Buscar em matriz não ordenada O(L × C) No pior caso, é necessário verificar todas as posições.
Inicializar todos os elementos O(L × C) Cada posição precisa receber um valor.
Espaço ocupado O(L × C) Existem L × C elementos armazenados.
Para uma matriz quadrada n × n, L e C valem n. Assim, percorrer todos os elementos exige n × n = n² operações, ou seja, O(n²).
06

Aplicação prática

Matrizes em C++17

Em C++, podemos representar matrizes usando arrays bidimensionais, std::array, std::vector<std::vector<int>> ou até um único std::vector linearizado. Cada abordagem possui implicações diferentes de tamanho, flexibilidade e contiguidade.

Array bidimensional tradicional 
#include <array>

std::array<std::array<int, 4>, 3> matriz{{
    {{1, 2, 3, 4}},
    {{5, 6, 7, 8}},
    {{9, 10, 11, 12}}
}};

int valor = matriz[1][2]; // 7
Percorrendo por linhas 
for (const auto& linha : matriz) {
    for (int valor : linha) {
        std::cout << valor << ' ';
    }
    std::cout << '\n';
}
Matriz linear com std::vector 
int linhas = 4;
int colunas = 5;
int linha = 2;
int coluna = 3;

int indice_linear = linha * colunas + coluna; // 13
Matriz linearizada em um único vector 
#include <vector>

int linhas = 4;
int colunas = 5;
std::vector<int> dados(linhas * colunas);

auto indice = [colunas](int linha, int coluna) {
    return linha * colunas + coluna;
};

dados[indice(2, 3)] = 99;
Quando usar uma lista de listas?

É uma representação simples e conveniente quando as dimensões são conhecidas somente em tempo de execução. Cada linha é um vetor independente, o que também permite estruturas irregulares em que linhas possuem comprimentos diferentes.

Por que usar um único vector linearizado?

Um único vetor mantém todos os elementos em um bloco contíguo e permite controlar explicitamente a transformação linha × colunas + coluna. Isso pode ser útil quando contiguidade e localidade de memória são importantes.

07

Modelo mental

O Que Você Precisa Guardar

Dimensões L linhas × C colunas.
Acesso m[i][j] continua O(1).
Memória A grade precisa ser representada linearmente.
Percurso Visitar tudo custa O(L × C).
Resumo: a matriz adiciona uma segunda dimensão lógica ao vetor. O segredo para entendê-la é perceber que linha e coluna são transformadas em uma única posição linear, mantendo o acesso direto.