POO + Complexidade

POO e Big-O juntos: medir o impacto real de escolhas de design. ArrayList vs HashMap medido com nanoTime. Grafo OO com classes. Conexão com APA e Teoria dos Grafos.

Big-OHashMapnanoTimeGrafolista de adjacênciamemoizationAPA

Big-O no contexto de objetos

Você está estudando Análise e Projeto de Algoritmos (APA) neste mesmo período. Hoje conectamos esse conhecimento com POO: escolhas de design OO têm impacto mensurável e demonstrável em complexidade.

🎓

conexão com APA e Teoria dos Grafos

APA: Big-O, análise assintótica, algoritmos de busca. Teoria dos Grafos (3º período): vértices, arestas, representações. Hoje: implementar grafos com classes Java e medir o custo de cada operação com System.nanoTime().

Operação	ArrayList	HashMap	TreeMap
Buscar por chave	O(n)	O(1)*	O(log n)
Inserir	O(1)*	O(1)*	O(log n)
Iteração ordenada	O(n log n) sort	não garante	O(n) natural

Medindo em Java com nanoTime

Antes de otimizar, meça. System.nanoTime() tem resolução em nanosegundos — ideal para comparar implementações.

Criar dados de teste — 10.000 pedidos em ArrayList e HashMap

Medir ArrayList.stream().filter(id) — Registrar tempo em nanosegundos

Medir HashMap.get(id) — Registrar tempo — diferença será dramática

Calcular speedup — HashMap / ArrayList = quantas vezes mais rápido

Cache com HashMap — Objeto que guarda resultados caros em Map — O(1) após primeira chamada

Grafo com classes Java

Teoria dos Grafos: você modelou no papel. Hoje modelamos em Java com classes. A escolha de representação (matriz de adjacência vs lista) impacta diretamente a complexidade.

⚡

OO + Complexidade juntos

Vertex com List vizinhos = lista de adjacência: O(V+E) espaço. Ou usar Map para descobrir vértice por nome em O(1) em vez de O(V). Design OO e complexidade andam juntos.

java
// Medindo diferença ArrayList vs HashMap
List<Pedido> lista = new ArrayList<>();
Map<String, Pedido> mapa = new HashMap<>();

for (int i = 0; i < 10_000; i++) {
    Pedido p = new Pedido("PED-"+i, "cliente"+i);
    lista.add(p);
    mapa.put(p.getCodigo(), p);
}

String busca = "PED-9999";

// ArrayList: O(n)
long t1 = System.nanoTime();
Pedido r1 = lista.stream().filter(p -> p.getCodigo().equals(busca))
                .findFirst().orElse(null);
long tempoLista = System.nanoTime() - t1;

// HashMap: O(1) médio
long t2 = System.nanoTime();
Pedido r2 = mapa.get(busca);
long tempoMapa = System.nanoTime() - t2;

System.out.printf("ArrayList: %,d ns%nHashMap:   %,d ns%nSpeedup: %.0fx%n",
    tempoLista, tempoMapa, (double)tempoLista/tempoMapa);

// Grafo OO com lista de adjacência
public class Vertice {
    private final String id;
    private final List<Vertice> vizinhos = new ArrayList<>();

    public Vertice(String id) { this.id = id; }
    public void conectar(Vertice v) { vizinhos.add(v); }
    public List<Vertice> getVizinhos() { return vizinhos; }
}

public class Grafo {
    private final Map<String, Vertice> vertices = new HashMap<>();

    public Vertice addVertice(String id) {
        return vertices.computeIfAbsent(id, Vertice::new);
    }
    public void addAresta(String de, String para) {
        addVertice(de).conectar(addVertice(para)); // O(1) get por nome
    }
}

☕

quiz · aula 15

Teste seus conhecimentos em Java

0/3 respondidas

QUESTÃO 01

Por que HashMap.get() é O(1) enquanto ArrayList.stream().filter() é O(n)?

QUESTÃO 02

No Grafo OO, por que usar Map em vez de List?

QUESTÃO 03

O que System.nanoTime() permite fazer que System.currentTimeMillis() não permite bem?

0/3

← aula anterior

Exceções no mundo real

aula 15 de 15 de 18

módulo 4

próxima aula →

Padrão Strategy + API