Depois de aprender a pensar em sequência, decisão e repetição, vem o degrau que separa quem copia solução de quem cria solução: escolher como organizar os dados e conhecer os algoritmos clássicos. A ideia central é simples e vale ouro. A mesma tarefa, com a estrutura errada, custa um milhão de passos; com a estrutura certa, custa um. Este guia mostra as estruturas fundamentais, o custo real de cada operação em notação Big O e como decidir qual usar, sem matemática pesada e com código Python que roda. Para aprender tudo na prática, com jogos, desenhos, laboratório e certificado, use o Curso de Lógica de Programação Intermediário, gratuito e parte da Trilha Lógica.
Resposta rápida
- Estrutura de dados é o formato em que você guarda muitos valores: lista, dicionário, conjunto, pilha, fila, árvore, heap e grafo.
- Big O descreve como o custo cresce com o tamanho da entrada: O(1) constante, O(log n) logarítmico, O(n) linear, O(n log n), O(n²) quadrático e O(2^n) exponencial.
- Buscar por posição é O(1), mas buscar por valor em lista não ordenada é O(n); no dicionário, buscar por chave é O(1) em média.
- Escolher a estrutura certa muda a complexidade do problema: a regra de ouro é casar a operação mais frequente com a estrutura que a faz barata.
O que são estruturas de dados e por que a escolha muda tudo
No começo da programação você lida com poucos valores por vez: uma nota, dois preços, um nome. O mundo real vem em montes: a turma inteira, o extrato do mês, o tabuleiro completo. Guardar isso em variáveis soltas não escala, então usamos estruturas de dados, que são recipientes organizados para muitos dados de uma vez. O ponto que separa o programador iniciante do intermediário não é conhecer todas elas, é sentir qual pede menos esforço para o problema. Precisa buscar rápido por um identificador? Um dicionário resolve em O(1). Precisa manter tudo em ordem e processar por chegada? Uma fila. Precisa do maior valor a cada passo? Um heap. A estrutura errada não trava o programa, mas o deixa lento e cheio de gambiarra. A certa faz o código curto e o desempenho previsível.
Big O: como o tempo cresce com o tamanho da entrada
Dois programas podem dar o mesmo resultado e mesmo assim serem muito diferentes: um responde na hora, o outro trava com dados grandes. Para comparar sem depender da máquina, contamos passos em vez de segundos e perguntamos como esse número cresce quando a entrada aumenta. Esse é o papel do Big O. Ele ignora constantes e detalhes pequenos e foca no formato do crescimento, que é o que domina quando os dados ficam grandes. A tabela abaixo mostra as classes que aparecem quase sempre, com o teste mental de dobrar a entrada e um exemplo concreto de cada uma.
| Notação | Nome | Se a entrada dobra, o trabalho... | Exemplo típico |
|---|---|---|---|
| O(1) | constante | não muda | ler lista[i], acessar dict[chave] |
| O(log n) | logarítmico | soma um passo | busca binária, altura de árvore balanceada |
| O(n) | linear | dobra | busca linear, percorrer a lista uma vez |
| O(n log n) | linearítmico | pouco mais que dobra | merge sort, quick sort médio, sorted() |
| O(n²) | quadrático | quadruplica | dois laços aninhados, bubble sort |
| O(2^n) | exponencial | eleva ao quadrado (explode) | força bruta de subconjuntos, fibonacci recursivo ingênuo |
A leitura prática é esta: O(1) e O(log n) são ótimos e aguentam qualquer volume; O(n) e O(n log n) são o território normal de código bem escrito; O(n²) já pesa em listas grandes e O(2^n) só funciona em entradas minúsculas. Quando você melhora um trecho de O(n) para O(1) trocando uma lista por um dicionário, não ganha 10% de desempenho: ganha uma ordem de grandeza que aparece justamente quando o sistema cresce.
As estruturas fundamentais e o custo de cada operação
Cada estrutura é boa em algumas operações e ruim em outras, e o segredo é conhecer esse perfil. A tabela reúne as complexidades típicas de acesso, busca, inserção e remoção das estruturas que você mais vai usar. Onde a célula traz um asterisco ou um símbolo, a nota da última coluna explica a condição.
| Estrutura | Acesso por posição | Busca por valor | Inserção | Remoção | Observação |
|---|---|---|---|---|---|
| Array / lista (Python list) | O(1) | O(n) | O(1)* fim, O(n) meio | O(n) | *amortizado ao inserir no fim |
| Lista ligada | O(n) | O(n) | O(1) | O(1) | O(1) só se você já tem o nó em mãos |
| Pilha (stack) | O(1) topo | O(n) | O(1) | O(1) | LIFO: último a entrar sai primeiro |
| Fila (deque) | O(1) pontas | O(n) | O(1) | O(1) | FIFO: primeiro a entrar sai primeiro |
| Tabela hash / dicionário | O(1)† por chave | O(1)† chave, O(n) valor | O(1)† | O(1)† | †médio; O(n) no pior caso (colisões) |
| Conjunto (set) | - | O(1)† pertence | O(1)† | O(1)† | itens únicos, sem repetição |
| Árvore de busca balanceada | O(log n) | O(log n) | O(log n) | O(log n) | mantém ordem; O(n) se desbalanceia |
| Heap (fila de prioridade) | O(1) ver topo | O(n) | O(log n) | O(log n) topo | menor ou maior sempre no topo |
Array x lista ligada: o trade-off entre acesso e inserção
Array e lista ligada guardam sequências, mas por dentro são opostos. O array reserva um bloco contíguo de memória, então calcular onde está o item de posição 5 é conta direta: acesso por índice em O(1). O preço é a inserção no meio, que empurra todos os elementos seguintes uma casa para o lado, custando O(n). A lista ligada guarda cada item em um nó que aponta para o próximo, espalhados pela memória. Inserir ou remover é só religar dois ponteiros, O(1), desde que você já esteja no ponto certo. A conta vira: para chegar ao ponto certo, ela percorre desde o começo, O(n). Ou seja, um é rápido para ler por posição e caro para remexer no meio; o outro é o inverso. Na maioria dos códigos do dia a dia a lista dinâmica (o list do Python, o array do JavaScript) vence, porque acesso por índice e inserção no fim cobrem quase tudo. Você aprende a lista ligada por dentro para entender o custo, mas raramente a implementa à mão.
Tabela hash: por que o dicionário busca em O(1) (e quando degrada)
O dicionário é a estrutura que mais muda a vida de quem programa, porque transforma busca de O(n) em O(1). O truque é a função hash: ela pega a chave (um nome, um CPF, um id) e calcula um número que aponta para o endereço onde o valor mora. Guardar e buscar viram ir direto ao local, sem varredura. Por isso "achar o telefone da Ana" custa o mesmo com dez contatos ou com dez milhões. O detalhe honesto é o pior caso: se muitas chaves geram o mesmo endereço (colisão), a estrutura precisa percorrer uma pequena lista interna para desempatar, e no limite isso vira O(n). Implementações sérias, como a do Python, redimensionam a tabela e distribuem bem as chaves, então na prática você trata dicionário e conjunto como O(1) médio. O conjunto (set) é a mesma máquina sem os valores: serve para responder "esse item já apareceu?" em O(1) e para remover duplicados de uma coleção.
Pilha (LIFO) e fila (FIFO): dois padrões que aparecem sempre
Pilha e fila guardam itens em sequência, mas mudam quem sai primeiro. A pilha é LIFO: o último a entrar é o primeiro a sair, como uma pilha de pratos onde você tira o de cima. Ela aparece no desfazer e refazer de editores, na navegação de voltar do navegador e na própria máquina, que empilha as chamadas de funções e desempilha ao retornar. A fila é FIFO: o primeiro a entrar é o primeiro a sair, como a fila do caixa. Ela aparece em tarefas processadas por ordem de chegada, filas de impressão e no percurso em largura de um grafo. As duas fazem inserir e remover em O(1), e é justamente essa garantia de custo fixo nas pontas que as torna úteis. Em Python, a pilha é o próprio list (append e pop no fim), e a fila é o deque do módulo collections, que remove da frente em O(1), coisa que o list não faz bem.
Árvores: por que a busca fica O(log n)
A árvore organiza dados em uma hierarquia de nós, cada um com filhos. A mais usada para busca é a árvore binária de busca: em todo nó, os menores ficam à esquerda e os maiores à direita. Procurar um valor vira uma sequência de comparações em que cada passo descarta metade do que sobrou, e cortar pela metade repetidamente é exatamente o que produz O(log n). Uma árvore balanceada com um milhão de itens tem cerca de vinte níveis, então você acha qualquer valor em vinte comparações. O senão é o balanceamento: se os dados entram já ordenados e ninguém reequilibra, a árvore cresce toda para um lado, vira uma lista disfarçada e a busca degrada para O(n). Para garantir o O(log n) existem árvores que se ajustam sozinhas, como AVL e rubro-negra. Árvores também estão por trás de índices de banco de dados e de estruturas ordenadas que precisam de inserção e busca rápidas ao mesmo tempo.
Busca linear x busca binária
Achar um item é a operação mais comum da computação, e há duas estratégias base. A busca linear confere item por item e funciona em qualquer coleção, ordenada ou não, ao custo de O(n). A busca binária é bem mais rápida, mas cobra um preço de entrada: os dados precisam estar ordenados. Ela olha o item do meio, compara com o alvo e descarta a metade onde ele não pode estar, repetindo até achar, em O(log n). É a mesma tática de adivinhar um número de 1 a 100 chutando sempre o meio: você acerta em no máximo sete tentativas. Veja as duas em Python.
def busca_linear(lista, alvo):
# O(n): confere item por item, serve para lista sem ordem
for i, valor in enumerate(lista):
if valor == alvo:
return i
return -1
def busca_binaria(ordenada, alvo):
# O(log n): exige a lista JA ORDENADA
inicio, fim = 0, len(ordenada) - 1
while inicio <= fim:
meio = (inicio + fim) // 2
if ordenada[meio] == alvo:
return meio
if ordenada[meio] < alvo:
inicio = meio + 1 # descarta a metade de baixo
else:
fim = meio - 1 # descarta a metade de cima
return -1A lição prática: se você vai buscar muitas vezes na mesma coleção, ordenar uma vez (O(n log n)) e depois usar busca binária compensa. Se vai buscar por chave e não por ordem, nem ordene: jogue os dados em um dicionário e busque em O(1).
Algoritmos de ordenação: quais existem e quando usar
Ordenar é reorganizar uma coleção segundo um critério, e é pré-requisito para busca binária e mil relatórios. Os algoritmos didáticos (bubble, insertion, selection) são O(n²): fáceis de entender, lentos com dados grandes. Os de produção (merge, quick e o Timsort do Python) são O(n log n). Um fato importante e provado: nenhum algoritmo de ordenação baseado em comparação consegue ser melhor que O(n log n) no melhor caso possível, esse é o piso teórico. A tabela compara os principais.
| Algoritmo | Melhor | Médio | Pior | Espaço | Quando usar |
|---|---|---|---|---|---|
| Bubble sort | O(n) | O(n²) | O(n²) | O(1) | só para aprender o conceito |
| Insertion sort | O(n) | O(n²) | O(n²) | O(1) | listas pequenas ou quase ordenadas |
| Selection sort | O(n²) | O(n²) | O(n²) | O(1) | quando trocar itens custa muito caro |
| Merge sort | O(n log n) | O(n log n) | O(n log n) | O(n) | desempenho garantido e ordenação estável |
| Quick sort | O(n log n) | O(n log n) | O(n²) | O(log n) | rápido na prática, ordena no lugar |
| Timsort (sort do Python) | O(n) | O(n log n) | O(n log n) | O(n) | o padrão: use sorted() e list.sort() |
A conclusão para o dia a dia é curta: não escreva seu próprio sort em produção. O sorted() e o list.sort() do Python usam Timsort, que detecta trechos já ordenados e ganha desempenho em dados reais. Você implementa merge e quick à mão para entender a divisão e conquista, não para usar no lugar da biblioteca.
Recursão x iteração
Recursão é uma função que resolve um problema chamando a si mesma em uma versão menor, até chegar a um caso base que para a cadeia. Iteração resolve o mesmo com laços. Os dois têm o mesmo poder: todo algoritmo recursivo pode virar laço e vice-versa. A recursão brilha em problemas que se dividem naturalmente, como percorrer árvores, merge sort e backtracking, deixando o código curto e parecido com a definição do problema. O laço costuma gastar menos memória, porque não empilha uma chamada por nível, e não corre risco de estourar a pilha em profundidades grandes. O exemplo clássico do fatorial mostra os dois lados.
def fatorial_recursivo(n):
if n <= 1: # caso base que para a recursao
return 1
return n * fatorial_recursivo(n - 1)
def fatorial_iterativo(n):
resultado = 1
for k in range(2, n + 1):
resultado *= k
return resultado
# fatorial_recursivo(5) == fatorial_iterativo(5) == 120Escolha pela clareza: se a solução recursiva fica óbvia e a profundidade é controlada, use recursão. Se a profundidade pode ser enorme (percorrer uma lista de milhões), prefira o laço para não estourar a pilha de chamadas.
Complexidade de tempo x complexidade de espaço
Big O mede duas coisas diferentes com a mesma notação. Complexidade de tempo conta os passos executados; complexidade de espaço conta a memória extra usada além dos dados de entrada. As duas às vezes competem. O merge sort é O(n log n) no tempo, mas gasta O(n) de espaço, porque copia os dados em listas auxiliares. O quick sort ordena quase sem memória extra, apenas O(log n) da pilha de recursão. A memoização, que guarda resultados já calculados para não repetir trabalho, é o exemplo mais direto do troca: ela derruba o tempo (transforma exponencial em linear) gastando espaço para armazenar as respostas. Em ambientes com memória apertada, um algoritmo um pouco mais lento porém enxuto pode ser a escolha certa. Sempre olhe as duas dimensões antes de decidir.
Como escolher a estrutura certa para o problema
A decisão fica simples quando você parte da operação mais frequente e escolhe a estrutura que a torna barata. Precisa buscar rápido por uma chave única? Use dicionário, busca em O(1). Precisa saber se um item já apareceu ou remover duplicados? Use conjunto. Precisa manter ordem de chegada e processar do começo? Use fila. Precisa do último item primeiro (desfazer, voltar)? Use pilha. Precisa sempre do menor ou maior a cada passo? Use heap. Precisa dos dados ordenados com inserção e busca rápidas? Use árvore balanceada. Precisa só de uma sequência acessada por posição? A lista basta. O erro mais caro é forçar a lista em tudo por ser a mais familiar. Vale também escolher pelo que não muda: uma tupla (imutável) comunica que aquele conjunto de valores não deve ser alterado, e o interpretador aproveita isso.
Estruturas de dados em Python: list, dict, set, tuple e collections
O Python já traz as estruturas centrais prontas, e conhecer o custo de cada uma evita surpresa. O list é a lista dinâmica (acesso O(1), append no fim O(1) amortizado, insert no meio O(n), item in list é O(n)). O dict é a tabela hash (get, set e del em O(1) médio). O set é o conjunto (pertence, adicionar e remover em O(1) médio). A tuple é a sequência imutável, boa para dados fixos. O módulo collections completa o kit com o deque (fila com pontas em O(1), o jeito certo de fazer fila, já que list.insert(0, x) é O(n)), o Counter (contagem de itens) e o defaultdict (chave nova já nasce com um valor padrão).
numeros = [10, 20, 30] # list: ordem e acesso por indice
numeros.append(40) # O(1) amortizado no fim
agenda = {"ana": "1234"} # dict: busca por chave em O(1) medio
agenda["bruno"] = "5678"
vistos = {1, 2, 3} # set: itens unicos, "in" em O(1) medio
print(2 in vistos) # True
ponto = (10, 20) # tuple: imutavel, comunica dado fixo
from collections import deque, Counter, defaultdict
fila = deque() # fila eficiente: popleft em O(1)
fila.append("a")
fila.popleft()
contagem = Counter("banana") # Counter({'a': 3, 'n': 2, 'b': 1})
grupos = defaultdict(list) # chave nova ja nasce com []
grupos["frutas"].append("uva")Para praticar sem instalar nada, o guia de como aprender Python do zero aponta o caminho, e a guia de listas em Python aprofunda a estrutura que você mais vai usar. Quem quiser ver estas estruturas em dados reais pode brincar com a ferramenta de formatar JSON, que exibe listas e dicionários aninhados na tela.
Erros comuns de quem sai do básico
O primeiro é usar sempre a lista, mesmo quando o dicionário resolveria: procurar um contato em uma lista de milhares varre tudo (O(n)), enquanto o dicionário acha na hora (O(1)). O segundo é aninhar laços sobre dados grandes sem perceber que o custo vira O(n²): dobrar os dados quadruplica o trabalho. O terceiro é rodar busca linear em dados que já dariam para ordenar e usar busca binária, ou pior, ordenar a coleção inteira a cada consulta em vez de uma vez só. O quarto é confundir acesso por posição (O(1)) com busca por valor (O(n)) e achar que a lista busca rápido. E o quinto é confiar na entrada do usuário sem validar, a maior fonte de erros e brechas de segurança. Conhecer esses tropeços de antemão é meia batalha ganha.
Limitações deste guia
As complexidades aqui são o comportamento assintótico típico de cada estrutura e algoritmo: descrevem como o custo cresce, não o tempo exato em segundos, que depende da máquina, da linguagem e da implementação. Casos médios (como O(1) do dicionário) são estatísticos e têm pior caso pior; casos amortizados (append no fim da lista) valem na média de muitas operações, não em toda operação isolada. Este é um guia de fundamentos: estruturas mais especializadas (tries, tabelas de espalhamento com sondagem, árvores B, grafos ponderados) e a análise formal de algoritmos ficam para o estudo avançado. Para aprender com prática guiada, jogos e um laboratório de algoritmos, o curso intermediário de lógica cobre este conteúdo passo a passo.
Fontes oficiais
Para conferir as complexidades e aprofundar, use material de referência reconhecido, não blogs de terceiros:
- Python Wiki: TimeComplexity - tabela oficial de complexidade das operações de list, dict, set e deque na implementação CPython.
- Documentação do Python: módulo collections - deque, Counter, defaultdict e OrderedDict, com o comportamento de cada um.
- MIT OpenCourseWare: 6.006 Introduction to Algorithms - curso aberto do MIT sobre estruturas de dados, busca, ordenação e análise de complexidade.
Conclusão
Estruturas de dados e algoritmos são o passo que transforma quem escreve pequenos programas em quem resolve problemas de verdade, em qualquer linguagem. O resumo cabe em uma frase: conheça o custo de cada estrutura, escolha a que torna barata a operação que você faz mais, e deixe a biblioteca ordenar por você. Depois deste guia, avance para as estruturas de dados avançadas (pilha, fila, árvore, grafo e hash por dentro), firme a base com o guia de como aprender programação do zero e entenda o conceito raiz na guia sobre o que é um algoritmo. Quem estuda Python pode aprofundar com programação orientada a objetos e decorators em Python. Para praticar com dados reais, use a calculadora de Base64, o conversor de binário, decimal e hexadecimal e a calculadora de hash (MD5, SHA). Veja também como o portal audita seus números na página como validamos os cálculos e conheça as demais ferramentas da categoria Tecnologia. Para aprender tudo com método, comece pelo Curso de Lógica de Programação Intermediário e veja todos os cursos gratuitos do ValorFinal.