O que é um algoritmo?
Um algoritmo é um conjunto de instruções que realizam uma tarefa. Pode ser uma receita de bolo, um manual de montagem ou, no nosso caso, um procedimento que um computador segue para resolver um problema.
A diferença entre um algoritmo bom e um ruim pode ser a diferença entre resolver algo em 30 operações ou em 1 bilhão. É exatamente sobre isso que vamos falar.
Pesquisa Binária
Imagine que você está procurando um nome em uma lista telefônica com 128 nomes ordenados alfabeticamente. A abordagem mais ingênua seria olhar nome por nome, do início ao fim. No pior caso, você faria 128 verificações.
A pesquisa binária funciona de forma muito mais inteligente: você abre no meio da lista, verifica se o nome que busca vem antes ou depois, e descarta metade dos itens de uma só vez. Depois repete o processo na metade restante.
Com 128 nomes, o máximo de etapas é 7 (porque log2 128 = 7). Se a lista tiver 256 nomes, são apenas 8 etapas. Dobramos a entrada e adicionamos apenas uma única etapa a mais.
Requisito fundamental
A pesquisa binária só funciona com listas ordenadas. Se a lista não estiver em ordem, você precisa ordená-la primeiro ou usar outro método de busca.
Implementação em Python
def pesquisa_binaria(lista, alvo):
baixo = 0
alto = len(lista) - 1
while baixo <= alto:
meio = (baixo + alto) // 2
chute = lista[meio]
if chute == alvo:
return meio
if chute > alvo:
alto = meio - 1
else:
baixo = meio + 1
return None # não encontrado
# Exemplo de uso
minha_lista = [1, 3, 5, 7, 9, 11, 13, 15]
print(pesquisa_binaria(minha_lista, 7)) # 3 (índice do elemento)
print(pesquisa_binaria(minha_lista, 10)) # NoneA cada iteração, o espaço de busca é dividido pela metade. Isso resulta em uma complexidade de O(log n).
Logaritmos
Se exponenciação é multiplicar uma base por ela mesma várias vezes, o logaritmo é a operação inversa: ele responde “quantas vezes preciso multiplicar a base para chegar nesse número?”.
- log10 100 = 2 — preciso multiplicar 10 por ele mesmo 2 vezes para chegar em 100 (10 x 10 = 100)
- log2 128 = 7 — preciso multiplicar 2 por ele mesmo 7 vezes para chegar em 128
- log2 256 = 8 — um a mais que 128, porque dobramos o número
Na ciência da computação, quando falamos de O(log n), geralmente estamos nos referindo a log na base 2. É por isso que a pesquisa binária é tão eficiente: cada etapa elimina metade do problema.
Notação Big O
A notação Big O descreve o quanto um algoritmo escala conforme o tamanho da entrada cresce. Ela não mede o tempo em segundos, mas sim o número de operações no pior caso.
Comparação prática
Considere uma lista com 1 bilhão de elementos (10^9):
| Algoritmo | Operações |
|---|---|
| Busca simples O(n) | 1.000.000.000 |
| Busca binária O(log n) | ~30 |
A diferença é absurda. Enquanto a busca simples precisa verificar cada elemento, a busca binária resolve o problema em cerca de 30 passos.
Complexidades mais comuns
| Notação | Nome | Exemplo |
|---|---|---|
| O(1) | Constante | Acessar um elemento de array por índice |
| O(log n) | Logarítmica | Pesquisa binária |
| O(n) | Linear | Busca simples (percorrer toda a lista) |
| O(n log n) | Linearítmica | Quicksort, Merge sort |
| O(n^2) | Quadrática | Selection sort, loops aninhados |
| O(n!) | Fatorial | Caixeiro-viajante (força bruta) |
O que significa na prática?
Para ter uma noção concreta, veja quantas operações cada complexidade exige para diferentes tamanhos de entrada:
| n | O(1) | O(log n) | O(n) | O(n log n) | O(n^2) | O(n!) |
|---|---|---|---|---|---|---|
| 10 | 1 | ~3 | 10 | ~33 | 100 | 3.628.800 |
| 100 | 1 | ~7 | 100 | ~664 | 10.000 | impossível |
| 1.000 | 1 | ~10 | 1.000 | ~9.966 | 1.000.000 | impossível |
A complexidade O(n!) é especialmente assustadora: para n = 20, estamos falando de aproximadamente 2,4 quintilhões de operações. É por isso que problemas como o do caixeiro-viajante não têm solução exata eficiente para entradas grandes.
Arrays vs Listas Encadeadas
Antes de falar de Quicksort, vale entender duas estruturas de dados fundamentais.
Arrays
- Armazenam elementos em posições sequenciais na memória
- Leitura por índice é instantânea: O(1)
- Inserção é problemática: se não houver espaço contíguo disponível, todos os elementos precisam ser movidos — O(n)
- Tamanho geralmente fixo (ou precisa realocar)
Listas encadeadas
- Cada elemento guarda uma referência (ponteiro) para o próximo
- Os itens podem estar espalhados pela memória
- Inserção é rápida: basta atualizar os ponteiros — O(1)
- Leitura por posição exige percorrer a lista desde o início — O(n)
Resumo comparativo
| Operação | Array | Lista encadeada |
|---|---|---|
| Leitura | O(1) | O(n) |
| Inserção | O(n) | O(1) |
| Deleção | O(n) | O(1) |
Quando usar cada um?
- Arrays: quando você precisa acessar elementos por índice com frequência (ex.: tabela de preços, ranking)
- Listas encadeadas: quando inserções e remoções são frequentes e a leitura sequencial é aceitável (ex.: fila de tarefas, playlist)
Na prática, a maioria das linguagens modernas oferece estruturas híbridas (como ArrayList em Java ou list em Python) que combinam o melhor dos dois mundos.
Quicksort
O Quicksort é um dos algoritmos de ordenação mais usados na prática. Ele utiliza a técnica Dividir para Conquistar (Divide and Conquer), que consiste em:
- Definir um caso base (geralmente um array vazio ou com um único elemento, que já está ordenado)
- Reduzir o problema até chegar ao caso base
Dividir para Conquistar
A técnica DC (Divide and Conquer) é uma estratégia geral para resolver problemas:
- Divida o problema em subproblemas menores
- Conquiste cada subproblema recursivamente
- Combine os resultados
A pesquisa binária também usa essa lógica: divide o espaço de busca ao meio a cada etapa. O Quicksort aplica o mesmo princípio para ordenação.
Como funciona
- Escolha um elemento como pivô (pivot)
- Particione o array em dois sub-arrays: elementos menores que o pivô e elementos maiores que o pivô
- Aplique o Quicksort recursivamente em cada sub-array
- Combine os resultados
Implementação em Python
def quicksort(lista):
if len(lista) < 2:
return lista # caso base: lista vazia ou com 1 elemento
pivo = lista[0]
menores = [i for i in lista[1:] if i <= pivo]
maiores = [i for i in lista[1:] if i > pivo]
return quicksort(menores) + [pivo] + quicksort(maiores)
# Exemplo de uso
print(quicksort([10, 5, 2, 3])) # [2, 3, 5, 10]
print(quicksort([33, 15, 10, 7])) # [7, 10, 15, 33]Escolha do pivô
A escolha do pivô impacta diretamente a performance:
- Pivô fixo (primeiro elemento): simples, mas perigoso. Se o array já estiver ordenado, o Quicksort degenera para O(n^2)
- Pivô aleatório: estratégia recomendada. Ao escolher aleatoriamente, a probabilidade de cair no pior caso é muito baixa
- Mediana de três: escolhe a mediana entre o primeiro, o meio e o último elemento. Boa heurística
Complexidade
| Caso | Complexidade | Quando acontece |
|---|---|---|
| Melhor caso | O(n log n) | Pivô divide o array ao meio |
| Caso médio | O(n log n) | Pivô aleatório, divisões razoáveis |
| Pior caso | O(n^2) | Pivô é sempre o menor ou maior elemento |
Na prática, o caso médio é o mais comum, e o Quicksort tende a ser mais rápido que outros algoritmos O(n log n) como o Merge Sort, por ter constantes menores e melhor uso de cache.
Conclusão
Esses conceitos formam a base para entender a eficiência de qualquer software:
- Pesquisa binária transforma buscas de bilhões de operações em dezenas
- Big O nos dá uma linguagem comum para comparar algoritmos
- Arrays e listas encadeadas têm trade-offs claros que impactam a performance
- Quicksort mostra como a técnica Dividir para Conquistar resolve problemas de ordenação de forma elegante
Entender algoritmos não é apenas exercício acadêmico. É o que separa um sistema que aguenta escala de um que trava com mil usuários.