← Courses
100%
📄 PDF
Análise de Algoritmos — Aula 6

Complexidade de Algoritmos
Associados a Estruturas de Dados

(Noções, Análises e Exemplos Práticos)
Pedro Ximenes
Universidade Católica de Pernambuco (UNICAP)
Análise de Algoritmos • Semestre Letivo 2026.1

Roteiro da Aula

Sumário geral dos tópicos abordados nesta sessão
Seção 0 & 1
Revisão & Introdução
Revisão da Aula 5, motivação e o impacto da ED no desempenho.
Seção 2 & 3
ArrayList vs LinkedList
Acesso direto $O(1)$, shifts $O(n)$, resize amortizado e encadeamento.
Seção 4 & 5
Pilha & Fila Circular
Políticas LIFO e FIFO com operações estritas em $O(1)$ sem deslocamentos.
Seção 6
Árvore Binária de Pesquisa
Busca e inserção em $O(h)$; árvores balanceadas $O(\log n)$ vs degeneradas $O(n)$.
Seção 7 & 8
Heap & Tabela Hash
Fila de prioridade em array e hashing com colisões em $O(1)$ médio.
Seções 9 a 13
Comparativo, Exercícios & Gabarito
Grande tabela comparativa, 6 exercícios resolvidos e 5 propostos.

Revisão — Aula 5

Consolidação dos tópicos de algoritmos iterativos
📌 Tópicos Abordados na Aula Anterior
  1. Análise completa do Selection Sort ($\Theta(n^2)$) e Bubble Sort ($O(n^2)$).
  2. Comparação rigorosa entre Melhor Caso, Pior Caso e Caso Médio.
  3. Complexidade com dois parâmetros: laços aninhados independentes com custo $O(n \cdot m)$.
  4. Padrão $O(\sqrt{n})$: verificação eficiente de primalidade e divisores.
  5. Técnica dos dois ponteiros: otimização de laços aninhados de $O(n^2)$ para $O(n)$ linear.

Revisão — Padrões de Complexidade

Classes assintóticas fundamentais dos algoritmos iterativos
Padrão de Controle Exemplo Típico Complexidade
Sem loop Sequência de instruções primitivas $O(1)$
1 loop simples para i de 0 ate n $O(n)$
Loop com divisão enquanto n > 1: n ← n/2 $O(\log n)$
Loop até $\sqrt{n}$ enquanto i*i ≤ n $O(\sqrt{n})$
2 loops aninhados para i + para j (dep. de i) $O(n^2)$
Série harmônica $\sum_{i=1}^{n} n/i$ $O(n \log n)$
Dois ponteiros Two Sum (ordenado), Palíndromo $O(n)$
❓ Pergunta Central desta Aula
A complexidade de um algoritmo depende apenas do código do algoritmo? Ou a estrutura de dados escolhida para armazenar as informações também determina o custo computacional?

A Escolha da Estrutura de Dados Importa

O impacto direto da organização da memória no desempenho
💡 Ideia Central
A eficiência de um algoritmo depende diretamente da estrutura de dados utilizada. A exata mesma operação conceitual pode ter complexidades completamente diferentes dependendo da ED escolhida!
🔍 Exemplo Motivador: Buscar um Elemento
Considere a operação de verificar se um determinado valor está presente:
  • Em um array não ordenado: $O(n)$ — busca linear obrigatória.
  • Em um array ordenado: $O(\log n)$ — busca binária com acesso por índice.
  • Em uma tabela hash: $O(1)$ — no caso médio por mapeamento direto.
  • Em uma árvore binária de pesquisa balanceada: $O(\log n)$.
🎯 Conclusão
A escolha da estrutura de dados certa pode transformar um algoritmo lento e impraticável em um algoritmo instantâneo!

Operações Fundamentais

As primitivas analisadas e o conceito inevitável de compromisso
⚙️ Operações que Analisaremos em Cada ED
  1. Acesso / Busca: Recuperar um elemento (por índice posicional ou por valor de chave).
  2. Inserção: Adicionar um novo elemento na estrutura.
  3. Remoção: Excluir um elemento existente.
⚖️ Trade-off (Compromisso Arquitetural)
Nenhuma estrutura de dados é "perfeita" para todas as operações simultaneamente. Cada estrutura estabelece um compromisso:
  • Array: Acesso instantâneo por índice ($O(1)$), mas inserção e remoção lentas ($O(n)$) devido ao deslocamento de elementos.
  • Lista Encadeada: Inserção e remoção rápidas nas pontas ($O(1)$), mas acesso por índice lento ($O(n)$).
  • Tabela Hash: Operações em $O(1)$ médio, mas sem ordem e com custo de memória extra.

Estruturas que Estudaremos

Catálogo estruturado da sessão
📋 Roteiro de Estruturas de Dados
  1. Array / ArrayList: Listas baseadas em arrays dinâmicos contíguos.
  2. LinkedList: Listas duplamente encadeadas baseadas em ponteiros.
  3. Pilha (Stack): Acesso restrito LIFO (Last In, First Out).
  4. Fila (Queue): Acesso restrito FIFO (First In, First Out) com anel circular.
  5. Árvore Binária de Pesquisa (BST): Estrutura hierárquica baseada em ordenação.
  6. Heap: Árvore quase-completa para filas de prioridade.
  7. Tabela Hash: Mapeamento chave-valor por endereçamento direto ou encadeamento.
🎯 Objetivo Metodológico
Para cada ED: compreender a disposição física em memória, deduzir a complexidade de cada operação fundamental, demonstrar visualmente o algoritmo e comparar os custos com as demais alternativas.

O Array — A Estrutura Mais Elementar

Armazenamento contíguo em memória e cálculo direto de endereço
📌 Definição
Um array é uma coleção de elementos do mesmo tipo armazenados em posições estritamente contíguas de memória física, acessíveis instantaneamente através de um índice inteiro.
⚡ Propriedade Fundamental: Acesso em Tempo Constante $O(1)$
O acesso por índice V[i] é executado em $O(1)$ sem percorrer o vetor, pois a CPU calcula diretamente o endereço de memória via aritmética de ponteiros: $$\text{endereço}(V[i]) = \text{endereço\_base} + i \times \text{tamanho\_do\_elemento}$$
⚠️ Consequência da Contiguidade
Como os elementos estão colados uns nos outros na memória, para abrir espaço para um novo elemento no início ou no meio é obrigatório empurrar (deslocar) todos os elementos seguintes!

Operações em Array Puro — Complexidades

Custo das operações primitivas sobre vetores estáticos
Operação Complexidade Razão Teórica
Acesso por índice V[i] $O(1)$ Cálculo direto de endereço (base + $i \times$ size)
Busca por valor (linear) $O(n)$ Varredura elemento a elemento no pior caso
Inserção no fim $O(1)$ Atribuição direta se houver espaço pré-alocado
Inserção na posição $i$ $O(n)$ Deslocamento (shift) de $n - i$ elementos à direita
Remoção da posição $i$ $O(n)$ Deslocamento (shift) de $n - 1 - i$ elementos à esquerda
🚫 Limitações do Array Puro
  • Tamanho estático fixo: Definido no momento da alocação. Se encher, não aceita novos dados.
  • Custo de deslocamento: Inserções e remoções arbitrárias são custosas ($O(n)$).
  • O desenvolvedor precisa controlar manualmente a variável de quantidade de elementos válidos.

ArrayList — Lista Dinâmica Baseada em Array

Encapsulamento de array puro com política de redimensionamento dinâmico
📦 O que é uma ArrayList?
Uma ArrayList encapsula internamente um array tradicional e expõe uma API rica de operações de lista, gerenciando automaticamente o redimensionamento dinâmico e o remanejamento dos elementos.
  • lista[]: O array contíguo que armazena fisicamente os elementos.
  • tamanho: Quantidade lógica atual de elementos inseridos.
  • capacidade: Tamanho físico alocado no vetor interno (ex: capacidade inicial de 4 ou 10).
🔄 O Mecanismo de Resize (Dobra de Capacidade)
Quando uma inserção ocorre e o array interno atinge a capacidade máxima (tamanho == capacidade):
  1. Aloca-se um novo array com o dobro da capacidade ($2 \times capacidade$).
  2. Copiam-se todos os $n$ elementos do array antigo para o novo array — custo de $O(n)$.
  3. O ponteiro interno passa a apontar para o novo vetor e o elemento é adicionado.

ArrayList — Inserção no Fim (add)

Análise de custo comum vs. resize e o conceito de custo amortizado
  1. algoritmo add(lista, tamanho, elemento)
  2.     se tamanho = capacidade(lista) entao
  3.         novaLista ← novo vetor[2 * capacidade(lista)]
  4.         para i de 0 ate tamanho-1 faca
  5.             novaLista[i] ← lista[i]
  6.         fim para
  7.         lista ← novaLista // resize: O(n)
  8.     fim se
  9.     lista[tamanho] ← elemento
  10.     tamanho ← tamanho + 1
  11. fim algoritmo
📊 Complexidade
  • Sem resize: $O(1)$ — o elemento é atribuído diretamente na próxima posição livre.
  • Com resize: $O(n)$ — quando a capacidade esgota, o array dobra de tamanho e copia os elementos.
  • Custo Amortizado: $O(1)$ — O resize caro de $O(n)$ é raro porque a capacidade do vetor dobra a cada expansão ($4 \to 8 \to 16 \dots$). A imensa maioria das inserções é imediata ($O(1)$). Diluindo o custo acumulado de todas as cópias pelo total de $n$ inserções realizadas, o custo médio por operação é constante: $\boxed{O(1)}$.
ArrayList pronta. Capacidade: 4, Elementos: 3.

ArrayList — Inserção em Posição Arbitrária

O custo inevitável de deslocamento (shift) de elementos
  1. algoritmo addEmPosicao(lista, tamanho, index, elem)
  2.     // Shift de elementos para a direita
  3.     para i de tamanho ate index+1 (dec) faca
  4.         lista[i] ← lista[i-1]
  5.     fim para
  6.     lista[index] ← elem
  7.     tamanho ← tamanho + 1
  8. fim algoritmo
⚠️ Análise do Pior Caso
Ao inserir no início (index = 0), todos os $n$ elementos atuais precisam ser deslocados uma posição para a direita: $$\boxed{\text{Pior Caso (index = 0): } O(n)}$$
📐 Esquema de Deslocamento

Inserindo elemento 5 no índice 2:

Antes: [9, 2, 1, 8, 24, _]

↓ Elementos nos índices 2, 3 e 4 movem-se 1 casa à direita

Depois: [9, 2, 5, 1, 8, 24]

ArrayList — Remoção

Deslocamento à esquerda para fechamento de lacuna na memória
  1. algoritmo remove(lista, tamanho, index)
  2.     elemento ← lista[index]
  3.     // Shift de elementos para a esquerda
  4.     para i de index ate tamanho-2 faca
  5.         lista[i] ← lista[i+1]
  6.     fim para
  7.     tamanho ← tamanho - 1
  8.     retorne elemento
  9. fim algoritmo
📊 Análise de Complexidade
  • Remover do início (index = 0): Desloca $n-1$ elementos uma casa para a esquerda ⇒ $\boxed{O(n)}$.
  • Remover do fim (index = tamanho - 1): Apenas decrementa o ponteiro tamanho--, sem deslocamentos ⇒ $\boxed{O(1)}$.
  • Remover do meio (index = k): Desloca $n - 1 - k$ elementos ⇒ $O(n)$.

ArrayList — Busca e Resumo das Complexidades

Consolidação do comportamento assintótico de listas dinâmicas
⚡ Busca por Índice: get(index)
Acesso direto à posição de memória: lista[index] $$\boxed{O(1)}$$
🔍 Busca por Valor: indexOf(elem) / contains(elem)
Varredura linear comparando elemento a elemento: $$\boxed{O(n)}$$
📋 Resumo das Complexidades — ArrayList
Operação Complexidade Observação
get(i) $O(1)$ Acesso direto
add(elem) no fim $O(1)$ amort. Resize eventual $O(n)$
add(i, elem) $O(n)$ pior caso Shift à direita
remove(i) $O(n)$ pior caso Shift à esquerda
indexOf(elem) $O(n)$ Busca linear

LinkedList — Estrutura

Nós dispersos na memória conectados por ponteiros de referência
🔗 Ideia do Encadeamento
Ao invés de armazenar elementos em posições contíguas de memória, cada elemento reside em um nó independente disperso no Heap. Cada nó armazena seu dado e duas referências (ponteiros): uma para o nó anterior (prev) e outra para o próximo nó (next).
head 8 11 22 43 tail
📌 Características Anatômicas
  • Cada nó contém: valor, referência next e referência prev.
  • A lista mantém referências diretas para o início (head) e o fim (tail).
  • Os elementos não são contíguos na memória física.
  • Consequência crucial: Não há cálculo de endereço direto para o $i$-ésimo elemento. É obrigatório percorrer os ponteiros nó a nó desde a cabeça.

LinkedList — Inserção

Eficiência imediata nas pontas vs. navegação sequencial no meio
⚡ addFirst(elem) e addLast(elem) — $O(1)$
  • addFirst: Cria o novo nó, aponta novo.next = head, atualiza head.prev = novo e redefine head = novo.
  • addLast: Cria o nó, aponta tail.next = novo e redefine tail = novo.
  • Apenas reconfiguração de ponteiros em tempo constante. Sem deslocamento nem resize!
⏳ add(index, elem) — $O(n)$
Para inserir em posição arbitrária:
  1. Percorrer $i$ nós a partir de head: $O(n)$.
  2. Manipular os 4 ponteiros vizinhos: $O(1)$.
  3. Custo total: $\boxed{O(n)}$.
✨ Vantagem sobre ArrayList
Inserções no início (addFirst) são sempre $O(1)$, sem necessidade de empurrar $n$ elementos nem redimensionar vetores!
LinkedList duplamente encadeada pronta.

LinkedList — Remoção

Desligamento de ponteiros nas extremidades vs. busca prévia no meio
⚡ removeFirst() e removeLast() — $O(1)$
  • removeFirst: Atualiza head = head.next e limpa a referência anterior. Custo: $O(1)$.
  • removeLast: Atualiza tail = tail.prev e limpa a referência seguinte. Custo: $O(1)$.
  • Operação puramente de manipulação de referências de topo e cauda.
⏳ remove(index) e remove(elem) — $O(n)$
Exige percorrer a lista desde a cabeça para localizar o nó correspondente:
  • Percorrer sequencialmente até o nó: $O(n)$.
  • Desligar e religar referências dos vizinhos: $O(1)$.
  • Total: $\boxed{O(n)}$.

LinkedList — Busca

A ausência de acesso posicional direto
⏳ get(index), indexOf(elem), contains(elem) — $O(n)$
Todas as buscas requerem iteração nó por nó:
  • get(index): É necessário caminhar $i$ saltos de ponteiro a partir de head ⇒ $\boxed{O(n)}$.
  • indexOf(elem): Percorre a lista comparando o valor nó a nó até encontrar ou atingir null ⇒ $\boxed{O(n)}$.
⚡ getFirst() e getLast() — $O(1)$
Basta retornar diretamente o valor armazenado nos ponteiros head.valor ou tail.valor. Custo: $\boxed{O(1)}$.

LinkedList — Resumo das Complexidades

Panorama completo das operações em listas encadeadas
Operação Complexidade Observação Arquitetural
addFirst / addLast $O(1)$ Manipulação direta de ponteiros em head/tail
add(i, elem) $O(n)$ Percorrer a cadeia de nós até a posição $i$
removeFirst / removeLast $O(1)$ Manipulação direta de ponteiros em head/tail
remove(i) $O(n)$ Percorrer até a posição do nó desejado
get(i) $O(n)$ Sem cálculo de endereço direto; travessia sequencial
getFirst / getLast $O(1)$ Acesso imediato às referências head e tail
📌 Conclusão Teórica
A LinkedList é imbatível nas extremidades (head e tail), mas é inadequada e ineficiente para operações que demandem acesso aleatório por índice no meio da coleção.

ArrayList vs LinkedList — Comparação

Confronto direto de desempenho e diretrizes de seleção
Operação ArrayList LinkedList
Acesso por índice (get(i)) $O(1)$ ✓ $O(n)$
Inserção no início (addFirst) $O(n)$ (shift obrigatório) $O(1)$ ✓
Inserção no fim (addLast) $O(1)$ amort. ✓ $O(1)$ ✓
Remoção do início (removeFirst) $O(n)$ (shift obrigatório) $O(1)$ ✓
Remoção do fim (removeLast) $O(1)$ ✓ $O(1)$ ✓
Busca por valor $O(n)$ $O(n)$
Uso de memória Contígua (alta localidade) Nós + ponteiros (overhead de referências)
💡 Quando Usar Cada Uma?
  • ArrayList: Escolha padrão para a esmagadora maioria dos casos; indispensável quando o acesso aleatório por índice for frequente e leituras superarem inserções arbitrárias.
  • LinkedList: Use prioritariamente quando você necessitar de inserções e remoções constantes nas pontas (início e fim) sem alocação contígua prévia.

Pilha — Last In, First Out (LIFO)

Acesso estrito à última posição inserida
📌 Definição
Uma pilha é uma estrutura de dados linear disciplinada onde toda adição (push) e toda remoção (pop) são efetuadas exclusivamente em uma única extremidade denominada topo. O último elemento a entrar é obrigatoriamente o primeiro a sair.
💻 Aplicações Práticas Essenciais
  • Operação Desfazer / Refazer (Ctrl+Z / Ctrl+Y).
  • Histórico de navegação (botão "Voltar" do navegador web).
  • Pilha de chamadas de execução (Call Stack de recursão).
  • Casamento e validação de parênteses/chaves em compiladores.
Pilha pronta. Topo aponta para o elemento mais recente.

Pilha — Pseudocódigo das Operações Primitivas

Manipulação elementar de ponteiro de topo em tempo constante
📥 push(pilha, topo, elem)
  1. algoritmo push(pilha, topo, elem)
  2.     se topo + 1 = capacidade entao
  3.         // erro: pilha cheia (overflow)
  4.     fim se
  5.     topo ← topo + 1
  6.     pilha[topo] ← elem
  7. fim algoritmo
📤 pop(pilha, topo)
  1. algoritmo pop(pilha, topo)
  2.     se topo = -1 entao
  3.         // erro: pilha vazia (underflow)
  4.     fim se
  5.     elem ← pilha[topo]
  6.     topo ← topo - 1
  7.     retorne elem
  8. fim algoritmo
⚡ Análise de Complexidade
Ambas as operações envolvem exclusivamente operações primitivas de incremento/decremento de um índice inteiro e atribuição em memória. Nenhum laço é executado: complexidade estritamente $\boxed{O(1)}$.

Pilha — Resumo das Complexidades

Por que todas as operações são estritamente O(1)?
📋 Tabela de Operações de Pilha
Operação Complexidade Justificativa Algorítmica
push(elem) $O(1)$ Atribuição direta em pilha[topo+1] e incremento
pop() $O(1)$ Leitura de pilha[topo] e decremento
peek() $O(1)$ Acesso direto ao elemento pilha[topo] sem remoção
isEmpty() $O(1)$ Comparação booleana simples: topo == -1
💡 Por que tudo é $O(1)$?
A disciplina LIFO restringe completamente o ponto de acesso ao topo. Não há necessidade de percorrer a estrutura, não há buscas intermediárias e nenhum elemento jamais é deslocado!

Fila — First In, First Out (FIFO)

Inserções no final e remoções no início
📌 Definição
Uma fila é uma estrutura de dados linear onde toda inserção (addLast / enqueue) é realizada no fim (tail) e toda remoção (removeFirst / dequeue) ocorre na outra ponta, o início (head). O primeiro elemento a entrar é obrigatoriamente o primeiro a sair.
🖨️ Aplicações Típicas
  • Spool de impressão (documentos impressos na ordem exata de chegada).
  • Filas de requisições web e filas de mensagens (RabbitMQ, Kafka, SQS).
  • Busca em Largura em Grafos e Árvores (BFS - Breadth-First Search).
  • Escalonamento de processos por fatias de tempo (Round-Robin em SO).

Fila — Implementação e Complexidade

Eliminando o custo de shift com aritmética modular em buffer circular
⚠️ O Problema da Fila Linear com Shift
Se implementarmos a fila em um array simples e toda remoção do início exigir deslocar os elementos restantes para a esquerda (shiftLeft), a remoção custará $O(n)$!
✨ A Solução Elegante: Fila Circular
Ao invés de deslocar os dados fisicamente, deslocamos apenas os ponteiros head e tail utilizando aritmética modular com o operador resto de divisão (%):
  • Ao enfileirar: $\text{tail} \leftarrow (\text{tail} + 1) \pmod{\text{capacidade}}$
  • Ao desenfileirar: $\text{head} \leftarrow (\text{head} + 1) \pmod{\text{capacidade}}$
Quando um ponteiro atinge o final do array físico, ele "dá a volta" para o índice 0!
⚡ Complexidades na Fila Circular
Ambas as operações básicas tornam-se instantâneas: $$\boxed{\texttt{enqueue}: O(1) \quad \text{e} \quad \texttt{dequeue}: O(1)}$$

Fila — Exemplo de Funcionamento Circular

A volta no vetor físico garantindo tempo constante O(1)
🔄 Traço do Funcionamento
Considere um vetor de capacidade 4 com ponteiros Head (H) e Tail (T):
  1. addLast(a), addLast(b), addLast(c):
    $[\underset{H}{a},\;b,\;\underset{T}{c},\;\_]$
  2. removeFirst() → a:
    $[\_,\;\underset{H}{b},\;\underset{T}{c},\;\_]$
  3. addLast(d), addLast(e):
    O tail dá a volta: $(3+1) \pmod 4 = 0$!
    $[\underset{T}{e},\;\underset{H}{b},\;c,\;d]$
Fila Circular pronta. Observe H (head) e T (tail).

BST — Definição

A propriedade fundamental da Árvore Binária de Pesquisa
🌳 Propriedade da BST (Binary Search Tree)
Uma Árvore Binária de Pesquisa é uma árvore binária onde, para todo nó $X$:
  • Todos os valores na subárvore esquerda de $X$ são estritamente menores que o valor de $X$.
  • Todos os valores na subárvore direita de $X$ são estritamente maiores que o valor de $X$.
🌿 Exemplo Canônico da Aula
Na árvore com raiz 41:
  • À esquerda temos 20, cujos filhos são 11 ($< 20$) e 29 ($> 20$). Todos $< 41$.
  • À direita temos 65, cujos filhos são 50 ($< 65$) e 91 ($> 65$). Todos $> 41$.

BST — Conceitos Importantes

Terminologia e o papel decisivo da altura h
📖 Terminologia Estrutural
  • Raiz: O nó superior da árvore, que não possui pai (nó 41).
  • Folhas: Nós sem filhos (ex: 11, 29, 50, 91).
  • Altura $h$: O comprimento do maior caminho entre a raiz e uma folha.
🎯 Ponto Central da Análise de Complexidade
As operações fundamentais na BST (busca, inserção e remoção) dependem estritamente da altura $h$ da árvore:
  • Quanto menor a altura $h$, mais rápida a execução.
  • Para $n$ nós, a altura pode variar drasticamente: desde $h \approx \log_2 n$ (árvore perfeitamente balanceada) até $h = n - 1$ (árvore completamente degenerada em lista linear)!

BST — Busca

Decisão binária a cada nó: esquerda ou direita
  1. algoritmo buscaBST(raiz, valor)
  2.     no ← raiz
  3.     enquanto no != nulo faca
  4.         se valor = no.valor entao
  5.             retorne no
  6.         senao se valor < no.valor entao
  7.             no ← no.esquerda
  8.         senao
  9.             no ← no.direita
  10.         fim se
  11.     fim enquanto
  12.     retorne nulo // nao encontrado
  13. fim algoritmo
💡 Ideia do Algoritmo
Compara o valor buscado com a chave do nó atual:
  • Se for igual: elemento localizado com sucesso.
  • Se for menor: descartamos toda a subárvore direita e descemos para a esquerda.
  • Se for maior: descartamos toda a subárvore esquerda e descemos para a direita.
⚡ Custo da Busca
Em cada iteração, descemos exatamente um nível na árvore: $$\boxed{\text{Busca em BST: } O(h)}$$

BST — Exemplo de Busca Interativa

Rastreamento passo a passo da busca pelo valor 29 na árvore da aula
🔍 Traço da Busca por 29
  1. Compara 29 com 41 (raiz): $29 < 41$ ⇒ desce para a esquerda.
  2. Compara 29 com 20: $29 > 20$ ⇒ desce para a direita.
  3. Compara 29 com 29: $29 == 29$ ⇒ Encontrou!

Total de comparações: 3 (proporcional à altura percorrida $h$).

🎮 Controles do Simulador
Teste buscar 29 ou qualquer outro valor na árvore ao lado!
BST pronta. Clique em "Buscar 29" para ver o percurso.

BST — Inserção

Localizando a folha vazia para acoplamento do novo nó
🌱 Ideia da Inserção
A inserção segue a exata mesma lógica da busca: desce comparando as chaves até encontrar uma referência nula onde o novo elemento deve se encaixar como uma nova folha.
  1. algoritmo inserirBST(raiz, valor)
  2.     se raiz = nulo entao raiz ← novo No(valor); retorne; fim se
  3.     no ← raiz
  4.     enquanto no != nulo faca
  5.         se valor < no.valor entao
  6.             se no.esquerda = nulo entao no.esquerda ← novo No(valor); retorne; fim se
  7.             no ← no.esquerda
  8.         senao
  9.             se no.direita = nulo entao no.direita ← novo No(valor); retorne; fim se
  10.             no ← no.direita
  11.         fim se
  12.     fim enquanto
  13. fim algoritmo

BST — Complexidade de Inserção

Trabalho constante por nível visitado até a folha
📊 Análise
A inserção percorre um único caminho direto da raiz até a posição de inserção da folha, realizando apenas $O(1)$ operações de comparação por nó visitado. $$\boxed{\text{Inserção em BST: } O(h)}$$
🔍 Exemplo da Aula: Inserir o Valor 45
Na árvore canônica com raiz 41:
  1. $45 > 41$ ⇒ desce para a direita (nó 65).
  2. $45 < 65$ ⇒ desce para a esquerda (nó 50).
  3. $45 < 50$ ⇒ desce para a esquerda (encontra null) ⇒ insere 45 aqui!
Custo total: exatamente 3 comparações $= O(h)$.

BST — Balanceada vs. Degenerada

O abismo de desempenho entre O(log n) e O(n)
🌿 Árvore Balanceada (Melhor Caso)
  • As chaves dividem o espaço de busca pela metade a cada nível.
  • Para $n = 7$ nós, altura $h = 2$.
  • Altura teórica: $\boxed{h = O(\log n)}$.
  • Busca, inserção e remoção em tempo logarítmico!
⚠️ Árvore Degenerada (Pior Caso)
  • Ocorre quando chaves são inseridas em ordem já crescente ou decrescente (ex: 1, 2, 3, 4, 5, 6, 7).
  • A árvore degenera em uma lista encadeada simples!
  • Altura: $\boxed{h = n - 1 = O(n)}$.
  • Todas as operações degradam para tempo linear $O(n)$!

BST — Resumo de Complexidades

Comparativo assintótico entre o caso ótimo e o caso degenerado
Operação Melhor Caso (Balanceada, $h = O(\log n)$) Pior Caso (Degenerada, $h = O(n)$)
Busca $O(\log n)$ $O(n)$
Inserção $O(\log n)$ $O(n)$
Remoção $O(\log n)$ $O(n)$
Mínimo / Máximo $O(\log n)$ $O(n)$
💡 Conclusão Teórica e Árvores Auto-Balanceáveis
A eficiência de uma BST depende intrinsecamente de mantê-la balanceada. Estruturas como Árvores AVL e Árvores Rubro-Negras (Red-Black Trees) realizam rotações automáticas para garantir matematicamente que $h \le 2 \log_2 n$, assegurando $O(\log n)$ mesmo no pior caso de inserção ordenada!

Heap — O que é?

A estrutura ideal para implementação de filas de prioridade
Motivação: Fila de Prioridade
Queremos uma estrutura que permita:
  • Inserir elementos com prioridade.
  • Extrair o elemento de maior (ou menor) prioridade rapidamente.
Alternativas com estruturas lineares
Estratégia Inserção Extração do máx.
Lista ordenada $O(n)$ $O(1)$
Lista não ordenada $O(1)$ $O(n)$
Heap $O(\log n)$ $O(\log n)$
Heap é o meio-termo ideal!
Ambas as operações são $O(\log n)$, e a consulta ao máximo é $O(1)$.

Heap — Propriedades

As duas leis estruturais do Heap Máximo
Definição: Heap Máximo
Uma árvore binária que satisfaz duas propriedades:
  1. Propriedade do Heap: O valor de cada nó é maior ou igual ao de seus filhos. O maior está sempre na raiz.
  2. Completude: A árvore é completa ou quase-completa da esquerda para a direita. Isso garante $h = O(\log n)$.
88 87 73 47 54 6 0

Heap — Representação em Array

Como dispensar ponteiros e navegar por índices matemáticos
Como representar o Heap em um array?
Percurso em largura: $heap = [88, 87, 73, 47, 54, 6, 0]$
Índice: [0] [1] [2] [3] [4] [5] [6]
Valor: 88 87 73 47 54 6 0
Fórmulas de Navegação
Para um nó no índice $i$:
  • Filho à esquerda: $2i + 1$
  • Filho à direita: $2(i + 1)$
  • Pai: $\lfloor(i-1)/2\rfloor$
Por que funciona?
A propriedade de completude garante que não há ``buracos'' no array. Os nós são dispostos nível a nível, da esquerda para a direita.

Heap — Inserção

Inserção na próxima posição livre e subida (sift-up)
Algoritmo
  1. Adicionar o novo elemento na próxima posição livre (fim do array).
  2. Comparar com o pai: se for maior, trocar.
  3. Repetir até satisfazer a propriedade ou chegar à raiz.
Exemplo: Inserir 100 no heap $[88, 87, 73, 47, 54]$
  1. Colocar 100 na posição 5: $[88, 87, 73, 47, 54, \mathbf{100}]$
  2. $100 > \text{pai}(5) = 73$? Sim $\Rightarrow$ troca: $[88, 87, \mathbf{100}, 47, 54, 73]$
  3. $100 > \text{pai}(2) = 88$? Sim $\Rightarrow$ troca: $[\mathbf{100}, 87, 88, 47, 54, 73]$
  4. 100 é raiz $\Rightarrow$ parar.
$$\boxed{\text{Inserção no Heap: } O(\log n)}$$
Por quê $O(\log n)$?
No pior caso, o elemento sobe da folha até a raiz. O caminho tem tamanho $h = O(\log n)$ (árvore completa).
Heap inicial: [88, 87, 73, 47, 54]. Clique em "Próximo Passo" para inserir 100.

Heap — Remoção (Extract Max) e Heapify

Troca da raiz com a última folha e descida restaurando o heap
Algoritmo de Remoção
  1. Trocar a raiz (máximo) com a última folha.
  2. Decrementar o tamanho do heap.
  3. Aplicar heapify na raiz para restaurar a propriedade.
Heapify
Compara o nó com seus filhos esquerdo e direito. O maior dos três assume a posição do nó. Repetir descendo na árvore.
Exemplo: Remover max de $[100, 87, 88, 47, 54, 73]$
  1. Trocar 100 com 73: $[\mathbf{73}, 87, 88, 47, 54, 100]$. Remover 100 (tail--).
  2. Heapify(0): $\max(73, 87, 88) = 88 \Rightarrow$ troca: $[88, 87, \mathbf{73}, 47, 54]$.
  3. 73 é folha $\Rightarrow$ parar.
$$\boxed{\text{Remoção no Heap: } O(\log n)}$$
Heap inicial: [100, 87, 88, 47, 54, 73]. Clique em "Próximo Passo" para remover 100.

Heap — Resumo de Complexidades

Construção bottom-up e eficiência assintótica global
Operação Complexidade
Inserção (add) $O(\log n)$
Remoção do máximo (extractMax) $O(\log n)$
Consulta do máximo (peek) $O(1)$
Build Heap (a partir de array) $O(n)$
Build Heap é $O(n)$?
Sim! Embora cada heapify individual seja $O(\log n)$, a soma total é $O(n)$ porque a maioria dos nós está próxima das folhas.

Tabela Hash — Motivação

O sonho de realizar operações em tempo constante O(1)
💭 O Sonho: $O(1)$ para Tudo
E se pudéssemos associar cada elemento diretamente a um índice no array sem precisar realizar buscas lineares ou comparações sucessivas?
⚡ Tabela de Acesso Direto (Chaves Inteiras Pequenas)
Se as chaves forem inteiros pequenos (ex: matrículas de 0 a 1999), podemos usar a própria chave como índice no vetor: $$\texttt{tabela}[\text{chave}] = \text{valor} \quad \Longrightarrow \quad O(1)$$
🚫 O Grande Obstáculo Prático
Quando as chaves são grandes (ex: CPF com 11 dígitos ⇒ seriam necessárias $10^{11}$ posições de memória, inviabilizando qualquer computador) ou quando as chaves são strings alfanuméricas (nomes, e-mails, URLs), o acesso direto torna-se completamente impraticável.

Tabela Hash — Função Hash

Mapeando universos gigantescos de chaves para um espaço compacto
📐 O Papel da Função Hash
Uma função hash $h(k)$ mapeia chaves de qualquer tamanho para índices inteiros válidos dentro de uma tabela de tamanho compacto $m$: $$hash(chave) \longrightarrow \text{índice} \in [0, m-1]$$ Exemplo pelo método da divisão: $hash(k) = k \pmod m$, onde $m$ é tipicamente um número primo.
💎 Propriedades de uma Boa Função Hash
  1. Determinística: Para a mesma chave de entrada, deve retornar obrigatoriamente o mesmo índice sempre.
  2. Eficiente: O cálculo matemático do índice deve executar estritamente em tempo constante $O(1)$.
  3. Uniforme: Distribui as chaves com igual probabilidade por todos os slots da tabela, minimizando agrupamentos.

Tabela Hash — Funcionamento

Mapeamento modular de chaves reais para posições de array
🔢 Exemplo de Mapeamento com $m = 10$
Seja a função $hash(k) = k \pmod{10}$:
  • Chave 807365841: $807365841 \pmod{10} = \mathbf{1}$ ⇒ Armazena no índice 1 ("Jesse").
  • Chave 665422653: $665422653 \pmod{10} = \mathbf{3}$ ⇒ Armazena no índice 3 ("Walter").
  • Chave 736217017: $736217017 \pmod{10} = \mathbf{7}$ ⇒ Armazena no índice 7 ("Saul").
  • Chave 111382749: $111382749 \pmod{10} = \mathbf{9}$ ⇒ Armazena no índice 9 ("Mike").
❓ O que acontece se duas chaves diferentes gerarem o mesmo índice?
Pelo Princípio da Casa dos Pombos, se tivermos mais chaves possíveis que posições $m$, colisões são matematicamente inevitáveis!

Tabela Hash — Colisões e Encadeamento

Tratamento de colisões através de listas encadeadas (Chaining)
💥 O que é uma Colisão?
Ocorre quando duas chaves diferentes produzem exatamente o mesmo índice na função hash: $$hash(chave_1) = hash(chave_2), \quad \text{sendo } chave_1 \neq chave_2$$
🔗 Resolução por Encadeamento (Separate Chaining)
Cada posição da tabela armazena uma lista encadeada com todos os elementos que colidiram naquele bucket:
  • Inserção: Calcular hash, adicionar à lista ⇒ $\boxed{O(1)}$.
  • Busca: Calcular hash, percorrer a lista ⇒ $\boxed{O(\alpha)}$, onde $\alpha = n/m$ é o fator de carga (detalhado no próximo slide).
Tabela Hash com m=7. Teste colisões com o Preset do Ex. 4.

Tabela Hash — Fator de Carga e Resize

O que é, como calcular e controle de densidade para manter O(1)
📊 O que é o Fator de Carga ($\alpha$)?
O fator de carga ($\alpha$) mede a taxa média de ocupação de cada posição da tabela: $$\alpha = \frac{n}{m}$$ onde:
  • $n$ = número total de elementos armazenados.
  • $m$ = tamanho da tabela (número de slots / posições do array).
Como calcular (Exemplo prático):
Se uma tabela possui $m = 7$ posições e inserimos $n = 5$ chaves: $$\alpha = \frac{5}{7} \approx 0{,}71$$ No encadeamento, $\alpha$ representa exatamente o comprimento médio de cada lista.
💡 Impacto no Desempenho
  • Se $\alpha$ for muito alto ⇒ muitas colisões, listas longas ⇒ degradação da busca para $O(n)$.
  • A biblioteca padrão do Java (HashMap) adota $\alpha = 0{,}75$ como limite padrão para disparar o resize.
🔄 Resize e Rehash
Quando $\alpha$ atinge o limite (ex: $0{,}75$):
  1. Criar nova tabela maior (tipicamente o dobro: $2m$).
  2. Recalcular o hash de cada elemento com a nova função/tamanho (rehash).
  3. Reinserir todos na nova tabela ⇒ Custo $\boxed{O(n)}$, mas amortizado (ocorre raramente).

Tabela Hash — Endereçamento Aberto

Sondagem de posições livres dentro do próprio vetor
📌 Ideia do Endereçamento Aberto
Todos os elementos residem diretamente no array da tabela, sem listas encadeadas externas. Se a posição $h(k)$ estiver ocupada, procura-se a próxima posição livre através de uma sequência de sondagem (probing).
🔍 Sondagem Linear (Linear Probing)
$$hash(chave, i) = (hash(chave) + i) \pmod m, \quad i = 0, 1, 2, \dots$$ Avança circularmente de 1 em 1 até encontrar um slot vago.
⚖️ Trade-off entre as Estratégias de Colisão
  • Encadeamento: Usa memória extra (listas), mas o fator de carga pode ser $\alpha > 1$.
  • Endereçamento Aberto: Sem memória extra (tudo no array), mas o fator de carga deve ser estritamente $\alpha < 1$.

Tabela Hash — Complexidades

O contraste entre o caso médio O(1) e a degradação no pior caso O(n)
Operação Caso Médio (Distribuição Uniforme) Pior Caso (Todas as chaves colidem)
Inserção (put) $O(1)$ $O(n)$
Busca (get) $O(1)$ $O(n)$
Remoção (remove) $O(1)$ $O(n)$
⚠️ Quando ocorre o Pior Caso?
Todas as chaves colidem (mesmo hash) ⇒ todos os elementos em uma única lista encadeada ⇒ busca linear $O(n)$!
✅ Na Prática do Mundo Real
Com uma boa função hash e fator de carga controlado ($\alpha \le 0{,}75$), o caso médio $O(1)$ predomina. O resize/rehash é $O(n)$, mas amortizado.

Grande Tabela Comparativa Geral

Todas as estruturas de dados fundamentais lado a lado
Estrutura de Dados Acesso Busca Inserção Remoção
Array / ArrayList $O(1)$ $O(n)$ $O(n)$ ($O(1)$ amort. no fim) $O(n)$ ($O(1)$ no fim)
LinkedList $O(n)$ $O(n)$ $O(1)$ nas pontas / $O(n)$ meio $O(1)$ nas pontas / $O(n)$ meio
Pilha (Stack) $O(1)$ (topo) --- $O(1)$ (push) $O(1)$ (pop)
Fila (Queue) $O(1)$ (head) --- $O(1)$ (enqueue) $O(1)$ (dequeue)
BST (balanceada) --- $O(\log n)$ $O(\log n)$ $O(\log n)$
BST (degenerada) --- $O(n)$ $O(n)$ $O(n)$
Heap $O(1)$ (máximo) --- $O(\log n)$ $O(\log n)$
Tabela Hash --- $O(1)$ médio / $O(n)$ pior $O(1)$ médio / $O(n)$ pior $O(1)$ médio / $O(n)$ pior

Quando Usar Cada Estrutura?

Guia prático de engenharia de software e curvas comparativas
💡 Guia Prático de Decisão
  • Acesso frequente por índice numérico? → ArrayList.
  • Inserções/remoções constantes nas pontas? → LinkedList ou Deque.
  • Política estrita LIFO (desfazer/voltar)? → Pilha.
  • Ordem estrita FIFO (processamento por chegada)? → Fila.
  • Consultas por intervalo ordenado? → BST balanceada.
  • Extrair rapidamente o máximo/mínimo? → Heap.
  • Busca instantânea por chave sem necessidade de ordem? → Tabela Hash.
Qual operação comparar?
16
Comparativo para BUSCAR um valor entre $n = 16$ itens:
• Tabela Hash: 1 cálculo de hash e acesso direto ao bucket ($O(1)$).
• BST Balanceada: 4 comparações descendo pelos nós ($O(\log n)$).
• Array e LinkedList: até 16 comparações varrendo item por item ($O(n)$).

Exercício Resolvido 1 — Inserções em ArrayList

Contagem exata de operações primitivas e custo amortizado
📝 Enunciado
Uma ArrayList inicialmente vazia com capacidade inicial 4 recebe as seguintes operações consecutivas: add(a), add(b), add(c), add(d), add(e). Quantas operações primitivas (atribuições) são realizadas no total? Qual a complexidade amortizada?
✅ Resolução Passo a Passo
  • add(a): 1 atribuição direta → Total acumulado: 1
  • add(b): 1 atribuição direta → Total acumulado: 2
  • add(c): 1 atribuição direta → Total acumulado: 3
  • add(d): 1 atribuição direta → Total acumulado: 4 (capacidade 4 esgotada!)
  • add(e): Resize Obrigatório!
    • Aloca novo array com o dobro da capacidade: $2 \times 4 = 8$.
    • Copia os 4 elementos do array anterior: 4 atribuições.
    • Insere o novo elemento "e": 1 atribuição.
    • Subtotal do resize: $4 + 1 = 5$ atribuições.

Custo Total: $1 + 1 + 1 + 1 + 5 = \mathbf{9\text{ atribuições}}$ para 5 inserções.

Custo Médio Amortizado: $\frac{9}{5} = 1.8\text{ atribuições/inserção} \Longrightarrow \boxed{O(1)\text{ amortizado}}$.

Exercício Resolvido 2 — Inserções no Início (Parte 1)

Comparando o custo total de n inserções no início: ArrayList
📝 Enunciado
Considere a execução de $n$ inserções consecutivas no início de uma lista (posição de índice 0). Compare analiticamente o custo total usando: (a) ArrayList e (b) LinkedList.
⚙️ Solução (a) — ArrayList
Cada inserção no índice 0 exige o deslocamento (shift) para a direita de todos os elementos que já estão presentes na lista:
  • 1ª inserção: lista tem 0 elementos → 0 shifts.
  • 2ª inserção: lista tem 1 elemento → 1 shift.
  • 3ª inserção: lista tem 2 elementos → 2 shifts.
  • $\dots$
  • $n$-ésima inserção: lista tem $n-1$ elementos → $n-1$ shifts.
$$\text{Total de Shifts} = 0 + 1 + 2 + \dots + (n-1) = \sum_{i=0}^{n-1} i = \frac{n(n-1)}{2} \in \mathbf{\Theta(n^2)}$$

Exercício Resolvido 2 — Inserções no Início (Parte 2)

Comparando o custo total com LinkedList
✅ Solução (b) — LinkedList
Cada inserção no início em uma lista encadeada (addFirst) manipula exclusivamente as referências do nó e o ponteiro head em tempo constante $O(1)$: $$\text{Total} = n \times O(1) = \mathbf{O(n)}$$
📊 Comparativo Conclusivo
$$\boxed{\text{ArrayList: } \Theta(n^2) \quad \text{versus} \quad \text{LinkedList: } O(n)}$$
🎯 Lição Arquitetural
Para algoritmos que realizam inserções volumosas na cabeça da coleção, a LinkedList é assintoticamente infinitamente superior à ArrayList!

Exercício Resolvido 3 — Busca em BST

Construção de árvore e rastreamento de busca
📝 Enunciado
Os elementos $[15, 10, 20, 8, 12, 17, 25]$ são inseridos nesta exata ordem em uma BST inicialmente vazia. Determine a estrutura resultante e analise a complexidade de buscar o elemento 12.
🌳 Passo 1: Construção da Árvore
  • 15 é a raiz.
  • 10 vai à esquerda de 15; 20 vai à direita de 15.
  • 8 vai à esquerda de 10; 12 vai à direita de 10.
  • 17 vai à esquerda de 20; 25 vai à direita de 20.

A árvore é perfeitamente balanceada com altura $h = 2$.

🔍 Passo 2: Buscar 12
  1. $12 < 15$ ⇒ desce para a esquerda (nó 10).
  2. $12 > 10$ ⇒ desce para a direita (nó 12).
  3. $12 == 12$ ⇒ Encontrado!

Total: exatamente 3 comparações. Custo $O(h) = O(\log 7) \approx 2.8$ operações!

Exercício Resolvido 4 — Tabela Hash com Colisões (Parte 1)

Inserção e cálculo modular de índices
📝 Enunciado
Uma tabela hash de tamanho $m = 7$ utiliza a função $hash(k) = k \pmod 7$ com resolução de colisões por encadeamento. Insira as chaves $[14, 21, 28, 35, 10]$ e analise o custo de buscar o elemento 35.
🔢 Passo 1: Cálculo dos Hashes
  • $hash(14) = 14 \pmod 7 = \mathbf{0}$
  • $hash(21) = 21 \pmod 7 = \mathbf{0}$ → Colisão com 14 no bucket 0!
  • $hash(28) = 28 \pmod 7 = \mathbf{0}$ → Colisão com 14 e 21 no bucket 0!
  • $hash(35) = 35 \pmod 7 = \mathbf{0}$ → Colisão com 14, 21 e 28 no bucket 0!
  • $hash(10) = 10 \pmod 7 = \mathbf{3}$ → Inserido sem colisão no bucket 3.

Exercício Resolvido 4 — Tabela Hash com Colisões (Parte 2)

Estado dos buckets e custo da busca
📦 Passo 2: Estado dos Buckets na Tabela
  • Posição [0]: Lista encadeada com 4 elementos: $[14 \longrightarrow 21 \longrightarrow 28 \longrightarrow 35]$
  • Posição [3]: Lista com 1 elemento: $[10]$
  • Demais posições [1, 2, 4, 5, 6]: Vazias (null).
🔍 Passo 3: Custo de Buscar 35
$hash(35) = 35 \pmod 7 = 0$. Acessa o bucket 0 e percorre a lista comparando chaves:
Compara com 14 → 21 → 28 → 35. Total: 4 comparações!
⚠️ Diagnóstico Teórico
Como todos os múltiplos de 7 foram mapeados para o mesmo slot, a busca degradou para o pior caso linear $O(n)$. Escolher uma função hash que não divida perfeitamente os dados de entrada é fundamental!

Exercício Resolvido 5 — Análise de Algoritmo com ED

O perigo do antipadrão de acesso aleatório em laço
📝 Enunciado
Analise a complexidade do algoritmo abaixo, considerando que a variável lista seja: (a) uma ArrayList e (b) uma LinkedList.
  1. algoritmo processaLista(lista, n)
  2.     para i de 0 ate n-1 faca
  3.         elemento ← lista.get(i) // acesso por indice
  4.         // processa elemento em tempo O(1)
  5.     fim para
  6. fim algoritmo
⚡ Solução (a) — ArrayList
Na ArrayList, lista.get(i) é acesso direto em tempo constante $O(1)$:
$$\text{Total} = \sum_{i=0}^{n-1} O(1) = n \times O(1) = \mathbf{O(n)}$$

Exercício Resolvido 5 — Continuação

O desastre quadrático ao usar get(i) em LinkedList
🚫 Solução (b) — LinkedList
Na LinkedList, cada chamada a lista.get(i) precisa percorrer $i$ nós desde a cabeça:
$$\text{Total} = \sum_{i=0}^{n-1} i = 0 + 1 + 2 + \dots + (n-1) = \frac{n(n-1)}{2} \in \mathbf{\Theta(n^2)}$$
📊 Comparação de Desempenho
$$\boxed{\text{ArrayList: } O(n) \quad \text{versus} \quad \text{LinkedList: } \Theta(n^2)}$$
🎯 Lição de Engenharia de Software
Chamar get(i) dentro de um laço iterando sobre uma LinkedList é um dos antipadrões mais clássicos e destruidores de performance da programação! Para percorrer uma LinkedList em $O(n)$, deve-se obrigatoriamente usar um Iterator / foreach, que avança de nó em nó sem reiniciar da cabeça!

Exercício Resolvido 6 — Qual ED Escolher?

Seleção orientada pelos requisitos operacionais do sistema
📝 Enunciado
Você precisa implementar um sistema de controle com as seguintes operações frequentes: (1) Inserir novos elementos; (2) Verificar se um elemento existe; (3) Remover elementos por valor. A ordem dos elementos não importa. Qual ED escolher?
Estrutura Candidata Inserção Busca Remoção por Valor
ArrayList $O(1)$ amort. $O(n)$ $O(n)$
LinkedList $O(1)$ $O(n)$ $O(n)$
BST Balanceada $O(\log n)$ $O(\log n)$ $O(\log n)$
Tabela Hash $O(1)$ médio $O(1)$ médio $O(1)$ médio
✅ Veredito
$$\boxed{\text{Melhor Escolha: \textbf{Tabela Hash}}}$$ Como a ordem entre os elementos é irrelevante para o problema, a Tabela Hash oferece desempenho imbatível de $O(1)$ médio para todas as operações exigidas!

Exercício Proposto 1

ArrayList — Custo de n remoções consecutivas do início
📝 Enunciado
Dada uma ArrayList contendo inicialmente $n$ elementos, qual é o custo assintótico total de remover todos os elementos a partir do início (posição de índice 0), um por um, até esvaziar a lista?
💡 Dica
A cada remoção realizada no índice 0, todos os elementos que restam na lista sofrem uma operação de shift para a esquerda.
Solução Rápida: Na 1ª remoção desloca-se $n-1$; na 2ª $n-2$; $\dots$; até 0. Total: $\sum_{i=1}^{n-1} i = \frac{n(n-1)}{2} \in \mathbf{\Theta(n^2)}$.

Exercício Proposto 2

BST — O pior caso de inserção ordenada
📝 Enunciado
Os elementos $[1, 2, 3, 4, 5, 6, 7]$ são inseridos nesta exata ordem em uma BST inicialmente vazia.
  1. Desenhe ou descreva a árvore resultante.
  2. Qual é a altura $h$ da árvore?
  3. Qual é a complexidade de buscar o elemento 7?
💡 Dica
Como cada novo elemento é estritamente maior que o nó anterior, ele é sistematicamente inserido à direita.
Solução Rápida: A árvore torna-se estritamente degenerada (uma cadeia para a direita). Altura $h = 6 = n - 1$. Buscar o elemento 7 percorre todos os 7 nós, com custo $\mathbf{O(n)}$.

Exercício Proposto 3

Heap Máximo — Sequência de inserções e contagem de trocas
📝 Enunciado
Insira os elementos $[10, 20, 15, 30, 25]$ nesta ordem em um Heap Máximo inicialmente vazio.
  1. Mostre o estado do array do heap após cada uma das 5 inserções.
  2. Quantas trocas (swaps) foram realizadas no total?
💡 Dica
Após colocar o elemento no fim do array, aplique o procedimento de subida comparando com o pai no índice $\lfloor(i-1)/2\rfloor$.
Solução Rápida: 10 → [10] (0 trocas); 20 → [20, 10] (1 troca); 15 → [20, 10, 15] (0 trocas); 30 → [30, 20, 15, 10] (2 trocas); 25 → [30, 25, 15, 10, 20] (1 troca). Total: 4 trocas.

Exercício Proposto 4

Tabela Hash com primo e o fenômeno de colisão total
📝 Enunciado
Uma tabela hash de tamanho $m = 11$ utiliza $hash(k) = k \pmod{11}$ com resolução por encadeamento. Insira as chaves $[22, 33, 44, 55, 66, 77, 88]$.
  1. Em quais posições da tabela cada chave é alocada?
  2. Há colisões? Quantas?
  3. Qual é o fator de carga final $\alpha$?
💡 Dica
Observe o que todas essas chaves têm em comum matematicamente em relação ao número 11.
Solução Rápida: Como todos os números são múltiplos de 11, $k \pmod{11} = 0$ para todos. Todas as 7 chaves caem no bucket 0 (6 colisões). Fator de carga $\alpha = 7/11 \approx 0.64$.

Exercício Proposto 5

Seleção de EDs para cenários reais de engenharia de software
📝 Enunciado
Para cada cenário abaixo, indique a melhor estrutura de dados e justifique com a operação dominante:
  1. Um editor de texto implementando Ctrl+Z (desfazer) e Ctrl+Y (refazer).
  2. Um servidor de impressão processando ordens de impressão na ordem exata de chegada.
  3. Um jogo online exibindo em tempo real o ranking dos 10 melhores jogadores do servidor.
  4. A tabela de símbolos de um compilador verificando se uma variável já foi declarada.
  5. Um banco de dados executando consultas por intervalo (ex: "alunos com nota entre 7 e 9").
Solução Rápida: 1. Duas Pilhas (LIFO); 2. Fila (FIFO); 3. Min-Heap de tamanho 10; 4. Tabela Hash ($O(1)$); 5. BST balanceada ($O(\log n + k)$).

Gabarito — Exercício Proposto 1

ArrayList — Custo de n remoções do início
📌 Enunciado
Dada uma ArrayList com $n$ elementos, remover todos do início (índice 0), um por um.
✅ Demonstração Analítica
A cada remoção realizada na posição 0, todos os elementos restantes na lista precisam ser deslocados uma casa para a esquerda (shift à esquerda):
  • 1ª remoção: restam $n-1$ elementos → $n-1$ shifts.
  • 2ª remoção: restam $n-2$ elementos → $n-2$ shifts.
  • $\dots$
  • $(n-1)$-ésima remoção: resta 1 elemento → 1 shift.
  • $n$-ésima remoção: lista vazia → 0 shifts.
$$\text{Total de Deslocamentos} = (n-1) + (n-2) + \dots + 1 + 0 = \sum_{k=1}^{n-1} k = \frac{n(n-1)}{2}$$ $$\boxed{\Theta(n^2)}$$

Gabarito — Exercício Proposto 2

BST — Pior caso de inserção ordenada
📌 Enunciado
Inserir $[1, 2, 3, 4, 5, 6, 7]$ nesta ordem em uma BST inicialmente vazia.
✅ Resolução Completa

(a) Estrutura da árvore: Como cada valor inserido é estritamente maior que a raiz e que todos os nós anteriores, cada elemento é acoplado como filho direito do elemento anterior: $$1 \longrightarrow 2 \longrightarrow 3 \longrightarrow 4 \longrightarrow 5 \longrightarrow 6 \longrightarrow 7$$ A árvore degenera completamente em uma lista encadeada simples inclinada à direita!

(b) Altura da árvore: $\mathbf{h = 6 = n - 1}$.

(c) Complexidade de buscar o 7: É obrigatório percorrer todos os 7 nós da raiz até a folha 7. Custo de 7 comparações ⇒ $\boxed{O(n)}$.

Gabarito — Exercício Proposto 3

Heap Máximo — Inserção de [10, 20, 15, 30, 25]
📌 Enunciado
Mostrar o estado do array e contar as trocas nas inserções sucessivas.
✅ Rastreamento das Inserções
  1. Inserir 10: [10] → 0 trocas.
  2. Inserir 20: [10, 20] → $20 > \text{pai}(10)$ ⇒ troca ⇒ [20, 10] → 1 troca.
  3. Inserir 15: [20, 10, 15] → $15 < \text{pai}(20)$ ⇒ 0 trocas.
  4. Inserir 30: [20, 10, 15, 30] → $30 > \text{pai}(10)$ ⇒ [20, 30, 15, 10] → $30 > \text{pai}(20)$ ⇒ [30, 20, 15, 10] → 2 trocas.
  5. Inserir 25: [30, 20, 15, 10, 25] → $25 > \text{pai}(20)$ ⇒ [30, 25, 15, 10, 20] → 1 troca.

Heap Final: [30, 25, 15, 10, 20]  |  Total de Trocas: $\boxed{4\text{ trocas}}$.

Gabarito — Exercício Proposto 4

Tabela Hash com m = 11 e chaves múltiplas
📌 Enunciado
Inserir $[22, 33, 44, 55, 66, 77, 88]$ em tabela $m=11$ com $hash(k) = k \pmod{11}$.
✅ Resolução Completa

(a) Posições alocadas:

  • $22 \pmod{11} = 0, \quad 33 \pmod{11} = 0, \quad 44 \pmod{11} = 0, \quad 55 \pmod{11} = 0$
  • $66 \pmod{11} = 0, \quad 77 \pmod{11} = 0, \quad 88 \pmod{11} = 0$

Todas as 7 chaves são mapeadas para o bucket [0]!

(b) Colisões: Como a primeira chave ocupa o slot e as 6 seguintes colidem no mesmo local, ocorreram exatamente 6 colisões.

(c) Fator de carga: $\alpha = \frac{n}{m} = \frac{7}{11} \approx \mathbf{0.64}$.

💡 Lição
Mesmo com $\alpha < 1$ e usando um tamanho primo ($11$), se as chaves compartilharem um fator comum com o módulo da função hash, ocorrerá colisão em massa!

Gabarito — Exercício Proposto 5

Respostas e justificativas operacionais para os cenários reais
✅ Soluções Justificadas
  1. Ctrl+Z / Ctrl+Y: Duas Pilhas (Stack) — A primeira empilha as ações executadas para desfazer (LIFO); a segunda guarda as ações desfeitas para refazer.
  2. Spooler de Impressão: Fila (Queue) — A ordem FIFO assegura que o primeiro documento enviado seja o primeiro impresso.
  3. Ranking Top-10: Min-Heap de tamanho 10 — A raiz armazena a menor pontuação do top-10 em $O(1)$. Qualquer nova pontuação é comparada com a raiz em $O(1)$ e atualizada em $O(\log 10) = O(1)$.
  4. Tabela de Símbolos do Compilador: Tabela Hash — Busca e inserção de identificadores em tempo médio constante $O(1)$.
  5. Consultas por Intervalo no Banco de Dados: BST Balanceada (ou B-Tree) — Os dados ordenados permitem encontrar o início do intervalo em $O(\log n)$ e percorrer em-ordem em $O(k)$ elementos.

Resumo da Aula 6

Síntese dos principais aprendizados conceituais
🎓 O que Aprendemos Nesta Aula
  1. A escolha da estrutura de dados altera radicalmente a classe assintótica dos algoritmos.
  2. ArrayList: Acesso direto $O(1)$, mas inserção e remoção no meio/início sofrem shifts $O(n)$. Resize tem custo amortizado $O(1)$.
  3. LinkedList: Inserção e remoção $O(1)$ nas pontas (head/tail), mas acesso posicional por índice é lento ($O(n)$).
  4. Pilha e Fila: Políticas de acesso restritas (LIFO e FIFO) que garantem operações fundamentais em estrito $O(1)$ sem shifts.
  5. BST: Eficiência atrelada à altura: $O(\log n)$ quando balanceada e degradação para $O(n)$ quando degenerada.
  6. Heap: Fila de prioridade balanceada com inserção e extração em $O(\log n)$ e consulta de topo em $O(1)$.
  7. Tabela Hash: Mapeamento direto com $O(1)$ médio; sensível a colisões e fator de carga $\alpha$.

Tabela Resumo Final

Quadro sinóptico de complexidades para memorização
Estrutura Acesso Busca Inserção Remoção
ArrayList $O(1)$ $O(n)$ $O(1)$ amort. fim / $O(n)$ meio $O(1)$ fim / $O(n)$ meio
LinkedList $O(n)$ $O(n)$ $O(1)$ pontas / $O(n)$ meio $O(1)$ pontas / $O(n)$ meio
Pilha (Stack) $O(1)$ topo --- $O(1)$ $O(1)$
Fila (Queue) $O(1)$ head --- $O(1)$ $O(1)$
BST (bal.) --- $O(\log n)$ $O(\log n)$ $O(\log n)$
Heap $O(1)$ max --- $O(\log n)$ $O(\log n)$
Tabela Hash --- $O(1)$ méd. $O(1)$ méd. $O(1)$ méd.
💡 Mensagem Principal
Não existe estrutura de dados universalmente "perfeita". A boa engenharia de software exige a identificação precisa das operações dominantes do problema para escolher a estrutura com o melhor trade-off de desempenho.

Próxima Aula

Transição para algoritmos recursivos e equações de recorrência
🚀 Aula 7 — Análise de Algoritmos Recursivos
  • Relações de recorrência e complexidade temporal de funções recursivas.
  • Método da Substituição (indução matemática).
  • Método da Árvore de Recursão (custo por nível e custo total).
  • Teorema Mestre: Análise de algoritmos de Divisão e Conquista.
  • Exemplos canônicos: Fatorial, Fibonacci, Busca Binária, MergeSort e QuickSort.

Dúvidas?

Utilize os controles superiores e simuladores para revisar os conceitos.

Referências Bibliográficas

Bibliografia fundamental recomendada
📚 Leituras Recomendadas
  • T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein.
    Algoritmos: Teoria e Prática. 3ª ed, Elsevier, 2012. Capítulos 6 (Heapsort), 10 (Estruturas de Dados Elementares), 11 (Tabelas Hash) e 12 (Árvores Binárias de Busca).
  • J. A. B. Monteiro.
    Notas de Aula — Estruturas de Dados. Disponível em: joaoarthurbm.github.io/eda.
  • R. Sedgewick, K. Wayne.
    Algorithms. 4th ed, Addison-Wesley, 2011.
  • J. Kleinberg, É. Tardos.
    Algorithm Design. Pearson, 2005.