Muitos algoritmos para um mesmo problema
Um algoritmo é um conjunto de passos exatos para resolver um problema. A maioria dos problemas pode ser resolvida por mais de um algoritmo. Por exemplo, para achar um nome numa lista você pode conferir todos os nomes ou, se a lista estiver em ordem, pode ir dividindo-a ao meio.
Os dois dão a resposta certa. A diferença é a eficiência: quanto trabalho e quanta memória cada um precisa. Um bom programador escolhe o algoritmo que continua rápido quando os dados ficam grandes.
Comparando algoritmos pelo tempo gasto
Medir com um cronômetro não é justo: um computador rápido faz um algoritmo lento parecer bom. Por isso contamos os passos básicos (comparações, trocas, somas) em função do tamanho da entrada n.
Melhor caso, caso médio e pior caso
O melhor caso é a entrada mais sortuda (o 13 está na primeira caixa: 1 passo). O pior caso é a mais azarada (o 13 não está lá: n passos). Em geral usamos o pior caso, porque ele é uma garantia: o algoritmo nunca será mais lento do que isso.
Complexidade de tempo e de espaço
A complexidade de tempo diz como o número de passos cresce com n. A complexidade de espaço diz como a memória extra cresce com n. O merge sort é rápido, mas precisa de memória extra; o bubble sort quase não precisa de memória extra, mas é lento.
Notação Big O
O Big O descreve a taxa de crescimento, ignorando detalhes pequenos. Ficamos só com o termo maior e jogamos fora os números constantes: 3n² + 5n + 2 vira O(n²), porque, para n grande, a parte n² é quase tudo.
| Big O | Nome | n = 16 | n = 1000 | Exemplo |
|---|---|---|---|---|
| O(1) | constante | 1 | 1 | ler o item 5 de um vetor |
| O(log n) | logarítmico | 4 | cerca de 10 | busca binária |
| O(n) | linear | 16 | 1000 | busca linear, achar o maior |
| O(n log n) | n log n | 64 | cerca de 10.000 | merge sort |
| O(n²) | quadrático | 256 | 1.000.000 | bubble sort, laços aninhados |
Regra rápida para o código: um laço sobre n itens é O(n); um laço dentro de outro é O(n²); dividir o problema ao meio a cada vez é O(log n).
Eficiência da busca linear e da busca binária
A busca linear confere os itens um por um. Pior caso: n comparações, ou seja, O(n). Funciona em qualquer lista, ordenada ou não.
A busca binária precisa de uma lista ordenada. Olhe o item do meio; se ele for grande demais, descarte a metade da direita, senão a da esquerda. Cada passo divide a lista ao meio, então o pior caso é cerca de log₂ n + 1 comparações: O(log n). Para 1.000.000 de itens, são cerca de 20 passos em vez de 1.000.000.
Eficiência dos algoritmos de ordenação
Bubble sort, insertion sort e selection sort usam um laço dentro de outro, então fazem cerca de n²/2 comparações: O(n²). O insertion sort é O(n) no melhor caso (uma lista que já está ordenada).
O merge sort divide a lista ao meio cerca de log₂ n vezes e faz cerca de n de trabalho em cada nível: O(n log n). Ele precisa de O(n) de memória extra.
A busca binária precisa de uma lista ordenada. Se você busca só uma vez, ordenar antes (n log n) custa mais do que uma busca linear (n). Se você busca muitas vezes, ordenar uma vez compensa.
Pré-condições, pós-condições e armadilhas da recursão
Uma pré-condição é o que precisa ser verdade antes de o algoritmo começar (busca binária: a lista está ordenada). Uma pós-condição é o que fica garantido quando ele termina (ordenação: cada item é menor ou igual ao próximo). Escrevê-las ajuda a testar e a provar um algoritmo.
Recursão significa que uma função chama a si mesma para um problema menor. Erros comuns:
- Não ter caso base, ou ter um caso base que nunca é alcançado: as chamadas nunca param (estouro de pilha).
- O problema não fica menor a cada chamada.
- Repetir o mesmo trabalho: um Fibonacci recursivo simples chama fib(3) várias e várias vezes, então cresce como O(2ⁿ). Guardar as respostas (memoização) deixa O(n).
- Recursão muito profunda usa muita memória, um quadro de pilha por chamada.
Experimente: corrida entre duas buscas
Escreva os números de 1 a 32 em papeizinhos e coloque-os em ordem, virados para baixo. Peça a um amigo que escolha um número secreto. Primeiro procure um por um e conte os papéis que virou. Depois procure sempre virando o papel do meio. Repita 5 vezes. Qual método nunca precisou de mais de 6 viradas? Confira com o controle deslizante no último passo do 3D (n = 32: log₂ 32 = 5).
Fórmulas e definições principais
- Busca linear: pior caso n comparações → O(n)
- Busca binária: pior caso cerca de log₂ n + 1 comparações → O(log n)
- Bubble / insertion / selection sort: cerca de n(n − 1)/2 comparações → O(n²)
- Merge sort: cerca de n log₂ n comparações → O(n log n)
- Regra do Big O: fique com o maior termo, jogue fora as constantes (5n² + 3n → O(n²))
- Dobrando n: O(1) igual, O(log n) +1, O(n) ×2, O(n²) ×4
Exemplos resolvidos
1. Uma lista tem 50 nomes. Quantas comparações a busca linear precisa no melhor e no pior caso?
Melhor caso: o nome é o primeiro → 1 comparação. Pior caso: o nome é o último ou não existe → 50 comparações. A busca linear é O(n).
2. Qual é o máximo de comparações que a busca binária precisa numa lista ordenada de 1024 itens?
Cada passo divide a lista ao meio: 1024 → 512 → 256 → 128 → 64 → 32 → 16 → 8 → 4 → 2 → 1. São 10 divisões, mais a última conferência: no máximo 11 comparações (log₂ 1024 = 10).
3. Dê o Big O de f(n) = 4n² + 10n + 7.
Fique com o maior termo (4n²) e jogue fora a constante 4: O(n²).
4. Um laço roda i de 1 até n e, dentro dele, outro laço roda j de 1 até n. Quantas vezes a linha de dentro é executada?
n vezes para cada um dos n valores de i: n × n = n². Complexidade de tempo O(n²).
5. Um programa O(n²) ordena 1000 itens em 2 segundos. Quanto tempo leva, aproximadamente, para 3000 itens?
n fica 3 vezes maior, então n² fica 3² = 9 vezes maior: cerca de 2 × 9 = 18 segundos.
6. Compare o bubble sort e o merge sort para n = 1000 itens.
Bubble sort: cerca de n²/2 = 500.000 comparações. Merge sort: cerca de n log₂ n = 1000 × 10 = 10.000. O merge sort faz cerca de 50 vezes menos trabalho, mas precisa de memória extra.
Erros comuns
- Medir a velocidade só com um cronômetro em um computador. Conte os passos em função de n.
- Usar a busca binária numa lista desordenada. A pré-condição dela é uma lista ordenada.
- Manter constantes no Big O, como escrever O(2n). É simplesmente O(n).
- Escrever uma função recursiva sem caso base, ou que não deixa o problema menor.