O que e um algoritmo?
Um algoritmo e um conjunto de instrucoes 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 diferenca entre um algoritmo bom e um ruim pode ser a diferenca entre resolver algo em 30 operacoes ou em 1 bilhao. E exatamente sobre isso que vamos falar.
Pesquisa Binaria
Imagine que voce esta procurando um nome em uma lista telefonica com 128 nomes ordenados alfabeticamente. A abordagem mais ingenua seria olhar nome por nome, do inicio ao fim. No pior caso, voce faria 128 verificacoes.
A pesquisa binaria funciona de forma muito mais inteligente: voce abre no meio da lista, verifica se o nome que busca vem antes ou depois, e descarta metade dos itens de uma so vez. Depois repete o processo na metade restante.
Com 128 nomes, o maximo de etapas e 7 (porque log2 128 = 7). Se a lista tiver 256 nomes, sao apenas 8 etapas. Dobramos a entrada e adicionamos apenas uma unica etapa a mais.
Requisito fundamental
A pesquisa binaria so funciona com listas ordenadas. Se a lista nao estiver em ordem, voce precisa ordena-la primeiro ou usar outro metodo de busca.
Implementacao 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 # nao encontrado
# Exemplo de uso
minha_lista = [1, 3, 5, 7, 9, 11, 13, 15]
print(pesquisa_binaria(minha_lista, 7)) # 3 (indice do elemento)
print(pesquisa_binaria(minha_lista, 10)) # NoneA cada iteracao, o espaco de busca e dividido pela metade. Isso resulta em uma complexidade de O(log n).
Logaritmos
Se exponenciacao e multiplicar uma base por ela mesma varias vezes, o logaritmo e a operacao inversa: ele responde “quantas vezes preciso multiplicar a base para chegar nesse numero?”.
- 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 numero
Na ciencia da computacao, quando falamos de O(log n), geralmente estamos nos referindo a log na base 2. E por isso que a pesquisa binaria e tao eficiente: cada etapa elimina metade do problema.
Notacao Big O
A notacao Big O descreve o quanto um algoritmo escala conforme o tamanho da entrada cresce. Ela nao mede o tempo em segundos, mas sim o numero de operacoes no pior caso.
Comparacao pratica
Considere uma lista com 1 bilhao de elementos (10^9):
| Algoritmo | Operacoes |
|---|---|
| Busca simples O(n) | 1.000.000.000 |
| Busca binaria O(log n) | ~30 |
A diferenca e absurda. Enquanto a busca simples precisa verificar cada elemento, a busca binaria resolve o problema em cerca de 30 passos.
Complexidades mais comuns
| Notacao | Nome | Exemplo |
|---|---|---|
| O(1) | Constante | Acessar um elemento de array por indice |
| O(log n) | Logaritmica | Pesquisa binaria |
| O(n) | Linear | Busca simples (percorrer toda a lista) |
| O(n log n) | Linearitmica | Quicksort, Merge sort |
| O(n^2) | Quadratica | Selection sort, loops aninhados |
| O(n!) | Fatorial | Caixeiro-viajante (forca bruta) |
O que significa na pratica?
Para ter uma nocao concreta, veja quantas operacoes 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 | impossivel |
| 1.000 | 1 | ~10 | 1.000 | ~9.966 | 1.000.000 | impossivel |
A complexidade O(n!) e especialmente assustadora: para n = 20, estamos falando de aproximadamente 2,4 quintilhoes de operacoes. E por isso que problemas como o do caixeiro-viajante nao tem solucao 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 posicoes sequenciais na memoria
- Leitura por indice e instantanea: O(1)
- Insercao e problematica: se nao houver espaco contiguo disponivel, todos os elementos precisam ser movidos — O(n)
- Tamanho geralmente fixo (ou precisa realocar)
Listas encadeadas
- Cada elemento guarda uma referencia (ponteiro) para o proximo
- Os itens podem estar espalhados pela memoria
- Insercao e rapida: basta atualizar os ponteiros — O(1)
- Leitura por posicao exige percorrer a lista desde o inicio — O(n)
Resumo comparativo
| Operacao | Array | Lista encadeada |
|---|---|---|
| Leitura | O(1) | O(n) |
| Insercao | O(n) | O(1) |
| Delecao | O(n) | O(1) |
Quando usar cada um?
- Arrays: quando voce precisa acessar elementos por indice com frequencia (ex.: tabela de precos, ranking)
- Listas encadeadas: quando insercoes e remocoes sao frequentes e a leitura sequencial e aceitavel (ex.: fila de tarefas, playlist)
Na pratica, a maioria das linguagens modernas oferece estruturas hibridas (como ArrayList em Java ou list em Python) que combinam o melhor dos dois mundos.
Quicksort
O Quicksort e um dos algoritmos de ordenacao mais usados na pratica. Ele utiliza a tecnica Dividir para Conquistar (Divide and Conquer), que consiste em:
- Definir um caso base (geralmente um array vazio ou com um unico elemento, que ja esta ordenado)
- Reduzir o problema ate chegar ao caso base
Dividir para Conquistar
A tecnica DC (Divide and Conquer) e uma estrategia geral para resolver problemas:
- Divida o problema em subproblemas menores
- Conquiste cada subproblema recursivamente
- Combine os resultados
A pesquisa binaria tambem usa essa logica: divide o espaco de busca ao meio a cada etapa. O Quicksort aplica o mesmo principio para ordenacao.
Como funciona
- Escolha um elemento como pivo (pivot)
- Particione o array em dois sub-arrays: elementos menores que o pivo e elementos maiores que o pivo
- Aplique o Quicksort recursivamente em cada sub-array
- Combine os resultados
Implementacao 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 pivo
A escolha do pivo impacta diretamente a performance:
- Pivo fixo (primeiro elemento): simples, mas perigoso. Se o array ja estiver ordenado, o Quicksort degenera para O(n^2)
- Pivo aleatorio: estrategia recomendada. Ao escolher aleatoriamente, a probabilidade de cair no pior caso e muito baixa
- Mediana de tres: escolhe a mediana entre o primeiro, o meio e o ultimo elemento. Boa heuristica
Complexidade
| Caso | Complexidade | Quando acontece |
|---|---|---|
| Melhor caso | O(n log n) | Pivo divide o array ao meio |
| Caso medio | O(n log n) | Pivo aleatorio, divisoes razoaveis |
| Pior caso | O(n^2) | Pivo e sempre o menor ou maior elemento |
Na pratica, o caso medio e o mais comum, e o Quicksort tende a ser mais rapido que outros algoritmos O(n log n) como o Merge Sort, por ter constantes menores e melhor uso de cache.
Conclusao
Esses conceitos formam a base para entender a eficiencia de qualquer software:
- Pesquisa binaria transforma buscas de bilhoes de operacoes em dezenas
- Big O nos da uma linguagem comum para comparar algoritmos
- Arrays e listas encadeadas tem trade-offs claros que impactam a performance
- Quicksort mostra como a tecnica Dividir para Conquistar resolve problemas de ordenacao de forma elegante
Entender algoritmos nao e apenas exercicio academico. E o que separa um sistema que aguenta escala de um que trava com mil usuarios.