Algoritmos

O panorama e o vocabulário

Imagine que você precisa achar um nome numa lista telefônica. Você pode ler cada linha desde o começo, ou pode abrir o livro no meio e decidir qual metade manter. Os dois jeitos estão corretos, mas o segundo é muito mais rápido. Comparar receitas assim é o coração do estudo de algoritmos.

Para cada algoritmo fazemos três perguntas. Ele está correto, ou seja, sempre dá a resposta certa? Quanto tempo ele leva quando a entrada cresce? Quanta memória extra ele usa? Para responder a segunda, contamos passos e descrevemos como essa contagem cresce com o tamanho n da entrada, usando a notação Big O.

Veja como a última barra é gigante perto das outras. Com só mil itens, um algoritmo quadrático já faz cem vezes mais trabalho que uma boa ordenação. Com um milhão de itens, a diferença vira um milhão de vezes mil. É por isso que nos importamos com a ideia, e não só com uma máquina rápida.

As quatro técnicas de projeto

Palavras que aparecem em todas as seções

Ordenações elementares: bolha, seleção, inserção

Ordenar é colocar itens em ordem. Os três jeitos mais simples são fáceis de explicar e de escrever. Todos levam cerca de n² passos no pior caso, então são usados para entradas pequenas, ou como ajudantes dentro de algoritmos mais espertos.

Insertion sort: arrumando cartas de baralho

A regra que sempre vale é o invariante: antes de tratar a posição i, as posições 0 a i − 1 estão ordenadas. Depois de tratá-la, as posições 0 a i estão ordenadas e o resto do array não foi tocado. Para inserir, o algoritmo desloca os itens maiores uma casa para a direita e coloca o item novo no espaço vazio.

O custo depende de quão desordenada está a entrada. Se já está ordenada, o item novo nunca é menor que o vizinho da esquerda, então cada passo custa uma comparação e o total é cerca de n. Se está invertida, cada item viaja até o começo e o total é cerca de n²/2. Mais exatamente, o custo é cerca de n mais o número de inversões. Se cada item está a no máximo k posições do seu lugar final, há no máximo cerca de n·k inversões, então o custo é cerca de n·k. Por isso o insertion sort é a melhor escolha para dados quase ordenados.

Dá para usar busca binária para achar o lugar do item novo, o que reduz as comparações para cerca de log n por item. Mas o deslocamento continua necessário, e num array ele é o custo maior. Então esse truque só compensa quando comparar é bem mais caro que mover.

Selection sort: escolher o menor

Olhe todos os itens ainda desordenados, ache o menor e troque-o com o primeiro deles. Repita para a próxima posição. Achar o menor de m itens sempre exige m − 1 comparações, mesmo que o array já esteja ordenado. Então o total é sempre (n − 1) + (n − 2) + ... + 1 = n(n − 1)/2 comparações. Ele não é adaptativo.

Em compensação, ele move muito pouco: uma troca por rodada, ou seja, no máximo n − 1 trocas no total. Se mover um registro grande é caro e comparar é barato, o selection sort é uma boa opção.

Bubble sort: o maior sobe

Percorra o array da esquerda para a direita e troque todo par de vizinhos fora de ordem. No fim da primeira passada, o maior item 'borbulhou' até a última posição. Depois de k passadas, os k maiores estão nos seus lugares finais, então cada passada pode parar uma posição antes.

Passada 1 em [3, 1, 2]:
  [3, 1, 2]  3 > 1, troca
  [1, 3, 2]  3 > 2, troca
  [1, 2, 3]  o maior está no fim
Passada 2: nenhuma troca -> para

Trocar dois vizinhos fora de ordem remove exatamente uma inversão e não cria nenhuma. Por isso o número de trocas do bubble sort é exatamente o número de inversões da entrada. Se você acrescentar uma flag que lembra se a passada trocou algo, o algoritmo para depois de uma passada sem trocas, porque isso prova que tudo está em ordem. Com a flag, uma entrada ordenada custa só cerca de n passos.

Merge sort

Suponha que dois amigos tenham, cada um, uma pilha de folhas de lição de casa já ordenada por nome. Para juntar as pilhas numa só pilha ordenada, basta olhar a folha do topo de cada pilha e pegar a menor. Repita até as duas pilhas acabarem. Esse passo de juntar se chama merge (intercalação), e o merge sort é construído em cima dele.

O merge sort tem três passos. Dividir o array em duas metades, ordenar cada metade chamando o merge sort de novo, e intercalar as duas metades ordenadas. Um array com um item já está ordenado, então a divisão para aí. Isso é divisão e conquista.

          [6 2 8 3]
          /       \
      [6 2]       [8 3]
      /   \       /   \
    [6]   [2]   [8]   [3]
      \   /       \   /
      [2 6]       [3 8]
          \       /
          [2 3 6 8]

O custo é descrito por uma recorrência: T(n) = 2·T(n/2) + n. Duas metades, mais uma intercalação que toca cada item uma vez. A árvore de recursão tem cerca de log₂ n níveis, e cada nível faz cerca de n de trabalho no total. Então o merge sort custa n·log₂ n.

A divisão é feita pela posição (o meio), nunca olhando os valores. Então o formato da árvore é sempre o mesmo, seja qual for a ordem dos dados. Um array ordenado, um invertido e um aleatório têm a mesma ordem de crescimento. Só o número exato de comparações muda um pouco.

Quantas comparações uma intercalação precisa?

Cada comparação manda exatamente um item para a saída. Quando uma pilha acaba, o resto da outra é copiado sem comparar. O pior caso é quando as pilhas estão entrelaçadas de modo que uma delas fique com um único item no final. Intercalar m e n itens leva então no máximo m + n − 1 comparações.

Memória extra e estabilidade

• Memória. Intercalar dentro do mesmo array sem espaço extra é difícil e lento. A solução clássica copia os itens para um buffer e os escreve de volta em ordem. Esse buffer tem tamanho n, então o merge sort clássico não é in-place.
• Estabilidade. Quando o item da metade esquerda e o da metade direita são iguais, pegue o da esquerda, porque ele veio primeiro na entrada. Copie o da esquerda quando left[i] <= right[j]. Usar < estrito pegaria o da direita nos empates e quebraria a estabilidade.

// PT: pega da esquerda nos empates, para chaves iguais manterem a ordem
if (left[i] <= right[j]) {
	out.push(left[i++]);
} else {
	out.push(right[j++]);
}

O teste do dobro

Quando n dobra, um algoritmo n·log n leva um pouco mais que o dobro do tempo (cerca de 2 × (1 + 1/log₂ n)), bem menos que as quatro vezes de um algoritmo quadrático. Num benchmark, uma razão perto de 2 indica crescimento linear ou n log n, e uma razão perto de 4 indica n².

Bônus: contar inversões

O merge sort consegue contar as inversões de um array em tempo n log n. As inversões dentro de cada metade são contadas pela recursão. As que cruzam as metades são contadas durante a intercalação: quando o próximo item a copiar vem da metade direita, ele é menor que todos os itens que ainda esperam na metade esquerda, então somamos ao contador o número de itens que restam na esquerda.

Quicksort e estratégias de pivô

Imagine uma professora que pede à turma para se alinhar por altura. Ela escolhe um aluno, o pivô, e diz: 'mais baixos que o pivô à esquerda, mais altos à direita'. Agora o pivô está exatamente onde vai ficar no final. Os dois grupos são ordenados pelo mesmo método, e ninguém precisa juntá-los depois.

antes:    [ 6  2  8  3  5 ]      pivô = 5 (o último)
depois:   [ 2  3 |5| 6  8 ]
            <= 5  pivô  > 5
depois ordena a parte esquerda e a direita

Esse passo se chama particionamento, e é nele que está o trabalho. O quicksort é o oposto do merge sort: a divisão é difícil e o passo de combinar é vazio. Um jeito popular de particionar (chamado Lomuto) usa o último item como pivô e mantém um marcador i no fim da região dos itens pequenos. Cada item menor ou igual ao pivô é trocado para logo depois dessa região. No fim, o pivô é trocado para a posição seguinte à região.

function partition(a: number[], lo: number, hi: number): number {
	const pivot = a[hi];
	let i = lo - 1; // PT: fim da região dos 'pequenos'
	for (let j = lo; j < hi; j++) {
		if (a[j] <= pivot) {
			i++;
			[a[i], a[j]] = [a[j], a[i]];
		}
	}
	[a[i + 1], a[hi]] = [a[hi], a[i + 1]];
	return i + 1; // PT: lugar final do pivô
}

Tudo depende do pivô

O melhor pivô é a mediana: ela corta a faixa ao meio, então há cerca de log₂ n níveis de trabalho n cada, e o total é n·log n. O pior pivô é o menor ou o maior item: as partes têm 0 e n − 1 itens, há n níveis, e o custo é (n − 1) + (n − 2) + ... + 1 = n(n − 1)/2, que é n². Nesse pior caso, cada par de itens é comparado exatamente uma vez.

A mediana de três olha o primeiro, o do meio e o último item e usa a mediana desses três como pivô. Com pivô aleatório, o pior caso deixa de pertencer a uma certa entrada (como a ordenada). Ele pertence a uma sequência azarada de sorteios, então a média é sobre as escolhas do algoritmo, e um adversário não consegue montar uma entrada ruim de antemão.

Memória: in-place, mas com uma pilha

O quicksort reorganiza os itens dentro do array, então é in-place. Mas cada chamada recursiva usa um pouco de memória na pilha de chamadas. Com partes equilibradas, a profundidade é cerca de log n. Com as piores partes, é n. Um truque comum é recursar na parte menor e fazer um laço na maior, o que mantém a profundidade em log n mesmo nos casos ruins.

Muitas chaves iguais

Se o particionamento tem só duas regiões ('menor ou igual' e 'maior') e as n chaves são todas iguais, todos os itens vão para o mesmo lado, as partes têm 0 e n − 1 itens, e o custo é n², seja qual for o pivô. A correção clássica é o particionamento em três vias (a bandeira holandesa): colocar as chaves menores, iguais e maiores que o pivô em três grupos, e recursar só no primeiro e no último. Com poucas chaves diferentes, o custo fica perto de linear.

Quicksort híbrido

A maioria das chamadas do quicksort trata faixas minúsculas. Para dez itens, escolher um pivô e fazer duas chamadas custa mais que o trabalho em si. Por isso muitas bibliotecas entregam toda faixa menor que uma constante k (por exemplo 16) ao insertion sort. Isso não muda a ordem de crescimento, que continua n log n, mas baixa a constante, e o melhor k é achado medindo. No benchmark deste repositório, um limiar de algumas dezenas de itens ajudou tanto em C++ quanto em Rust.

Heapsort

Um heap é uma árvore genealógica com uma regra rígida. Num max-heap, todo pai é maior ou igual aos seus filhos. Então o maior item da árvore inteira está sempre no topo, a raiz. A árvore também é completa: todo nível está cheio, exceto talvez o último, que é preenchido da esquerda para a direita.

Uma árvore dentro de um array

Como a árvore é completa, ela cabe num array simples, nível por nível, sem ponteiros. As relações viram aritmética sobre o índice.

        9            índice: 0  1  2  3  4  5
      /   \          valor:  9  4  5  1  3  2
     4     5
    / \   /
   1   3 2

Sift-down e a construção do heap

O sift-down (também chamado heapify) conserta um nó: compare-o com o maior filho, troque se o filho for maior, e repita descendo por esse caminho. Para transformar um array qualquer em heap, aplique o sift-down em cada nó interno, do último até a raiz. Em [2, 8, 5, 1], o último nó interno (índice 1) está bom, depois a raiz 2 troca com o 8 e o array vira [8, 2, 5, 1].

Construir um heap assim custa só n, e não n log n. A razão é que o custo de um nó é a sua própria altura, e a maioria dos nós é baixa: cerca de n/2 são folhas (altura 0), n/4 têm altura 1, n/8 têm altura 2, e a soma n/4·1 + n/8·2 + n/16·3 + ... fica abaixo de n. Se você construir o heap inserindo os itens um a um e subindo cada um (sift-up), o custo de um nó é a sua profundidade, e a maioria dos nós é profunda, então o total é n log n.

A ordenação em si

1. Construa um max-heap no array (custo n).
2. Troque a raiz (o maior) com o último item do heap. Ela já está no lugar final.
3. Encolha o heap em um item e faça o sift-down da nova raiz.
4. Repita os passos 2 e 3 até o heap ter um item (n − 1 vezes, cada uma custando cerca de log n).

O total é n log n em todos os casos, com memória extra constante. É a única ordenação clássica com as duas propriedades. O preço é que ela não é estável, porque as trocas pulam sobre chaves iguais, e que lê a memória em posições espalhadas, o que a deixa mais lenta na prática que um bom quicksort.

Ordenações em tempo linear: counting, radix, bucket

Todas as ordenações das seções anteriores são ordenações por comparação. Existe um limite duro para elas: para distinguir as n! ordens possíveis de n itens usando só perguntas de sim ou não, são necessárias pelo menos log₂(n!) perguntas, que é cerca de n·log n. Nenhuma ordenação por comparação consegue vencer isso, por mais esperta que seja.

A saída é parar de comparar. Se as chaves são inteiros pequenos, podemos usar as próprias chaves como posições. Essas ordenações usam a estrutura das chaves, então o limite não vale para elas.

Counting sort

1. Conte quantas vezes cada valor aparece num array C.
2. Faça uma soma acumulada em C, de modo que C[v] passe a ser quantos itens são menores ou iguais a v. Isso diz onde termina o grupo de v na saída.
3. Percorra a entrada de trás para frente, coloque cada item na posição C[v] − 1 da saída e decremente C[v].

entrada:         [1, 3, 1, 0, 3]      valores 0..3
contagens:       [1, 2, 0, 2]
soma acumulada:  [1, 3, 3, 5]
saída:           [0, 1, 1, 3, 3]

O custo é n + k, em que k é o tamanho da faixa de valores (de 0 a k). É ótimo quando k é cerca de n, e péssimo quando k é enorme. Ir de trás para frente no passo 3 mantém itens iguais na ordem original, então a ordenação é estável. Isso importa para a próxima.

Radix sort (LSD)

O radix sort ordena números dígito por dígito, começando pelo dígito menos significativo (LSD), o da direita. Cada passada usa uma ordenação estável (em geral counting sort) sobre um dígito. A estabilidade é essencial: quando dois números têm o mesmo dígito da passada atual, eles precisam ficar na ordem que as passadas anteriores deram.

início:        329 457 657 839 436 720 355
passada unid.: 720 355 436 457 657 329 839
passada dez.:  720 329 436 839 355 457 657
centenas:      329 355 436 457 657 720 839

Com d dígitos na base k, o custo é d·(n + k). O número de passadas é o número de dígitos da chave: um inteiro de 32 bits tratado como 4 bytes (base 256) precisa de 4 passadas. Uma base maior significa menos passadas, mas um array de contagem maior. Um truque bonito: para n inteiros entre 0 e n³ − 1, escolha a base n. Cada número tem no máximo 3 dígitos, então 3 passadas de custo cerca de n cada uma ordenam tudo em tempo linear. Para uma faixa de n^c, são c passadas.

Bucket sort

Divida o intervalo de valores em baldes (buckets) de largura igual, jogue cada item no seu balde, ordene cada balde (em geral com insertion sort) e junte tudo. É linear em média se os dados estão bem espalhados pelo intervalo, porque assim cada balde recebe poucos itens. Se a maioria dos dados cai num balde só, o custo vira o da ordenação interna, que é n² com insertion sort.

Estabilidade, ordenação in-place e adaptativa

Velocidade não é a única coisa que importa na hora de escolher uma ordenação. Três propriedades dizem como um algoritmo se comporta com registros reais, com limites de memória e com dados que já estão quase em ordem.

Estável

Uma ordenação é estável se itens com chaves iguais saem na mesma ordem relativa em que chegaram. Isso importa quando os registros carregam mais que a chave. Suponha uma lista de alunos ordenada por nome. Se você agora ordenar por turma com um algoritmo estável, cada turma mantém seus alunos em ordem alfabética. Isso dá uma ordenação por dois critérios: ordene primeiro pela chave menos importante e por último pela mais importante. É também a razão pela qual o radix sort LSD funciona.

Como uma ordenação pode quebrar a estabilidade? Movendo um item para longe num único salto. Imagine o selection sort nas cartas 7♥, 7♠, 3♣. Ele troca a primeira carta com a menor, o 3♣. O resultado é 3♣, 7♠, 7♥. Os dois setes trocaram de lugar. Algoritmos que só movem um item para além de vizinhos estritamente maiores, ou que copiam itens na ordem de chegada, são estáveis.

In-place

Uma ordenação é in-place se trabalha dentro do array de entrada, com no máximo cerca de log n de memória extra (por exemplo, uma pilha de recursão). O merge sort precisa de um buffer de tamanho n, então não é in-place. O quicksort é, porque sua pilha é pequena. O heapsort é, com memória extra constante.

Adaptativa

Uma ordenação é adaptativa se fica mais rápida quando a entrada está mais perto de ordenada. O insertion sort custa cerca de n mais as inversões, e o bubble sort com a flag também para cedo. Seleção, merge e heapsort fazem quase o mesmo trabalho para qualquer ordem. Ordenações de bibliotecas como o Timsort usam a mesma ideia em escala maior: elas acham trechos que já estão ordenados e intercalam só esses trechos.

Busca: sequencial, binária, interpolação

Buscar é achar um item, chamado de chave, numa coleção. O método certo depende de uma pergunta: a coleção está ordenada?

Busca sequencial

Olhe os itens um por um até achar a chave ou chegar ao fim. Funciona em qualquer coleção. O melhor caso é 1 comparação, o pior é n, e se toda posição é igualmente provável para a chave, uma busca com sucesso faz em média (n + 1)/2 comparações. Tudo isso é linear em n.

Uma pequena melhoria é a sentinela. Normalmente cada rodada testa duas coisas: 'cheguei ao fim?' e 'este é a chave?'. Se você primeiro copiar a chave para uma posição extra no fim do array, o laço tem certeza de parar na chave, e o primeiro teste deixa de ser necessário. O custo continua linear, mas a constante é menor, um detalhe que a notação Big O não mostra.

Busca binária

A busca binária exige que os dados estejam ordenados. Olhe o item do meio. Se for a chave, pare. Se a chave for maior, ela não pode estar na metade esquerda, então faça low = mid + 1. Se for menor, faça high = mid − 1. Repita até o intervalo ficar vazio. Em dados desordenados, a comparação com o meio não diz nada sobre os outros itens, e o método falha.

function binarySearch(a: number[], key: number): number {
	let low = 0;
	let high = a.length - 1;
	while (low <= high) {
		// PT: low + (high - low) / 2 não estoura um int de 32 bits
		const mid = low + Math.floor((high - low) / 2);
		if (a[mid] === key) return mid;
		if (a[mid] < key) low = mid + 1;
		else high = mid - 1;
	}
	return -1;
}

Cada passo divide o intervalo ao meio, então o número máximo de olhadas é ⌊log₂ n⌋ + 1. Numa busca sem sucesso o número é o mesmo: um intervalo de 7 vira 3, depois 1, depois 0, ou seja, 3 olhadas. Arrays de tamanho 2ᵏ − 1 formam árvores perfeitas com k níveis.

Dobrar o array acrescenta só um passo: 1 milhão de itens precisam de 20 olhadas e 1 bilhão precisa de 30.

Dois detalhes famosos

• O bug do overflow. Escrever mid = (low + high) / 2 com inteiros de 32 bits quebra quando low + high passa de 2³¹ − 1, o que acontece em arrays ordenados com mais de cerca de um bilhão de itens. A soma fica negativa. Um programa correto no papel pode falhar numa máquina real porque os inteiros têm tamanho fixo. Escreva mid = low + (high − low) / 2.
• Chaves repetidas. Para achar a primeira ocorrência de uma chave em O(log n), não pare quando a achar. Procure o primeiro índice cujo valor é maior ou igual à chave (um lower bound): quando a[mid] >= key, mantenha a metade esquerda incluindo mid. Ela nunca para cedo, e sempre leva cerca de log₂ n passos.

Busca por interpolação

Quando você procura 'Zebra' num dicionário, não o abre no meio: abre perto do fim. A busca por interpolação faz isso. Se os valores crescem mais ou menos em linha reta entre v[lo] e v[hi], ela estima a posição da chave nessa reta.

// PT: a chave está a uma fração do caminho entre as duas pontas
pos = lo + (hi - lo) * (key - v[lo]) / (v[hi] - v[lo]);

Se os valores estão bem espalhados, o intervalo encolhe muito rápido (cerca de log log n passos em média). Se não estão, por exemplo quando crescem exponencialmente, a estimativa gruda numa das pontas e o intervalo encolhe um item por vez, então o custo pode chegar a n. A velocidade da busca por interpolação depende da distribuição das chaves.

Divisão e conquista

Como se come uma pizza gigante? Uma fatia por vez. A divisão e conquista resolve um problema grande cortando-o em cópias menores do mesmo problema. Ela sempre tem três passos: dividir o problema, conquistar cada parte resolvendo-a recursivamente, e combinar as respostas. A recursão para no caso base, um problema tão pequeno que a resposta é imediata.

Merge sort, quicksort e busca binária são divisão e conquista. Nesses algoritmos as partes são frações do problema (a metade, um terço), então a profundidade da recursão é logarítmica. Insertion e selection sort são diferentes: são incrementais, porque encolhem o problema em um item por passo. Isso leva a n etapas e, em geral, a um custo quadrático.

O custo como recorrência

Se um algoritmo faz a subproblemas de tamanho n/b e gasta f(n) para dividir e combinar, então T(n) = a·T(n/b) + f(n). Para resolver, compare f(n) com n^(log_b a), que é o número de folhas da árvore de recursão. Esse é o teorema mestre.

Para a busca binária também dá para expandir à mão: T(n) = T(n/2) + c = T(n/4) + 2c = ... = c·log₂ n, porque log₂ n conta quantas vezes n pode ser dividido por 2 até chegar a 1. Na recorrência T(n) = 4T(n/2) + n com n = 8, os níveis custam 8, 16, 32 e 64: a base domina, como diz o teorema.

Dois truques clássicos

• Exponenciação por quadrados sucessivos. Para calcular xⁿ, use xⁿ = (xⁿ/²)² quando n é par e xⁿ = x · xⁿ⁻¹ quando n é ímpar. O expoente cai pela metade a cada vez, então o número de multiplicações é cerca de log n em vez de n − 1. Para x¹⁰: x², x⁴, x⁵, x¹⁰ são só 4 multiplicações.
• Karatsuba. Multiplicar dois números de n dígitos do jeito da escola divide cada um em duas metades e precisa de 4 produtos de n/2 dígitos, o que custa Θ(n²). O Karatsuba acha um jeito com só 3 produtos e algumas somas a mais. Como o número de subproblemas a aparece no expoente log_b a, ir de 4 para 3 baixa o custo de n² para cerca de n^1,585. O Strassen faz o mesmo para matrizes, com 7 produtos em vez de 8.

Quando não funciona bem

A divisão e conquista é ótima quando os subproblemas são independentes, como as duas metades de um array. A função Fibonacci ingênua, fib(n) = fib(n − 1) + fib(n − 2), também se divide em problemas menores, mas eles se sobrepõem: fib(n − 2) é calculado de novo dentro de fib(n − 1). As chamadas se multiplicam e o tempo é exponencial. A cura é lembrar as respostas, que é a programação dinâmica.

Algoritmos gulosos

Uma criança que come primeiro a coisa mais gostosa do prato, depois a segunda mais gostosa, está sendo gulosa. Um algoritmo guloso monta a resposta um passo por vez e, a cada passo, escolhe o que parece melhor agora. Ele nunca olha para o futuro e nunca muda de ideia.

Isso deixa os algoritmos gulosos rápidos e simples. Mas ele só está correto se o problema tem a propriedade da escolha gulosa: sempre existe uma solução ótima que contém a escolha localmente melhor. Sem uma prova disso, um algoritmo guloso é só uma heurística.

Dar troco

Um caixa com moedas de 1, 5, 10, 25 e 50 centavos dá troco usando sempre a maior moeda que ainda cabe. Para 68 centavos: 50, 10, 5, 1, 1, 1, ou seja, 6 moedas. Com essas moedas a regra sempre dá o menor número de moedas. Mas com outras moedas ela pode falhar.

Seleção de atividades

Muitas atividades querem a mesma sala. Cada uma tem hora de início e de fim. Qual escolha dá o maior número de atividades sem sobreposição? Pegue a atividade que termina mais cedo, descarte as que se sobrepõem a ela e repita. A prova usa um argumento de troca: pegue qualquer solução ótima e troque a primeira atividade dela pela que termina mais cedo. A solução continua válida e com o mesmo tamanho. Então alguma solução ótima começa com a escolha gulosa, e o mesmo raciocínio vale para o tempo que sobra.

Mochila fracionária e mochila 0-1

Você tem uma mochila com limite de peso e itens com valor e peso. Na mochila fracionária você pode levar parte de um item (como areia ou farinha). Ordene os itens por valor por quilo e leve primeiro a melhor razão. Cada quilo é usado com o material mais valioso ainda disponível, então isso é ótimo.

Exemplo com capacidade 10: o item X vale 20 e pesa 5 (razão 4), e o item Y vale 18 e pesa 6 (razão 3). O guloso leva todo o X e 5/6 do Y, ou seja, 20 + 15 = 35. Na mochila 0-1 você precisa levar o item inteiro ou deixá-lo, e a mesma regra pode falhar. Com capacidade 10 e os itens A (valor 36, peso 6, razão 6), B (valor 25, peso 5, razão 5) e C (valor 25, peso 5, razão 5), a regra da razão leva o A e nada mais cabe, ou seja, 36. Mas B e C juntos pesam 10 e valem 50. A prova do caso fracionário precisa da opção de preencher o espaço restante com uma fração. A versão 0-1 precisa de uma tabela que compara 'levar' e 'não levar' para cada item e capacidade, e isso é programação dinâmica.

Onde o guloso está provado correto

• Árvore geradora mínima (Prim e Kruskal, na seção de grafos).
• Caminhos mínimos com pesos não negativos (Dijkstra).
• Seleção de atividades e mochila fracionária.
• Códigos de Huffman, que comprimem texto dando códigos curtos às letras comuns.
• Troco com sistemas de moedas 'bem comportados'.

O guloso como heurística

O problema do caixeiro viajante é NP-difícil: não se conhece algoritmo que ache o melhor percurso em tempo polinomial. A heurística do vizinho mais próximo começa numa cidade e vai sempre para a cidade mais próxima ainda não visitada. É rápida, mas não garante nada sobre o tamanho do percurso: trechos baratos no começo podem forçar trechos muito longos no fim. Em geral ela é melhorada pelo 2-opt, uma busca local que remove cruzamentos do percurso. Nos experimentos deste repositório com 5 a 12 cidades, o vizinho mais próximo ficou em média 8% acima do melhor percurso, e o 2-opt só 0,6%. Mas esses números descrevem aquelas instâncias, não são uma promessa.

Programação dinâmica

Se alguém perguntar '1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 é quanto?' e você disser 8, e depois a pessoa acrescentar mais um '+ 1' e perguntar de novo, você não conta do zero. Você lembra do 8 e diz 9. A programação dinâmica (PD) é isso: resolver cada problema pequeno uma só vez, anotar a resposta e reaproveitá-la sempre que o mesmo problema pequeno voltar.

A PD funciona quando o problema tem duas propriedades.

• Subestrutura ótima. A melhor resposta é montada a partir das melhores respostas de subproblemas menores. É isso que torna a PD correta.
• Subproblemas sobrepostos. O mesmo subproblema aparece muitas vezes. É isso que faz a PD valer a pena. Sem sobreposição, a PD não está errada, só não ganha nada da recursão simples.

Duas formas de escrever

O custo da PD é sempre: o número de subproblemas distintos vezes o trabalho de cada um, supondo que os menores já estão prontos. Para o Fibonacci com memoização, são n + 1 subproblemas de custo constante, então o tempo é linear. A recursão ingênua faz 2·fib(n + 1) − 1 chamadas, que cresce cerca de 1,618 vez a cada +1 em n.

Problema 1: troco com moedas quaisquer

Seja dp[v] o menor número de moedas que formam o valor v. Então dp[0] = 0 e dp[v] = 1 + min(dp[v − c]) sobre as moedas c que cabem em v. A tabela tenta toda moeda para todo valor, então não cai na armadilha do guloso. Com moedas 1, 5 e 6:

Problema 2: a mochila 0-1

A célula (i, w) guarda o melhor valor usando os i primeiros itens com capacidade w. É o maior de duas opções: não levar o item i, que é a célula (i − 1, w), ou levá-lo, que é o seu valor mais a célula (i − 1, w − peso), se ele couber. Com capacidade 4 e os itens P (valor 5, peso 2), Q (valor 4, peso 3) e R (valor 3, peso 1), as linhas são:

A mochila é NP-difícil, mas O(n·W) parece polinomial. O truque: isso é pseudopolinomial. O tempo é polinomial no valor numérico de W, e não no número de bits necessários para escrevê-lo. Se W = 2⁶⁴, a entrada tem só 64 bits para a capacidade, mas a tabela teria 2⁶⁴ colunas. Para capacidades pequenas é excelente na prática.

Problema 3: subsequência comum mais longa (LCS)

Uma subsequência mantém a ordem das letras, mas elas não precisam estar coladas. A célula (i, j) guarda o tamanho da LCS das i primeiras letras de uma palavra e das j primeiras da outra. Se as últimas letras são iguais, a célula é 1 mais a célula da diagonal. Senão, é a maior entre a célula de cima e a da esquerda. O custo é m·n. Para CAT e ACT:

Cada célula da LCS depende só da linha atual e da anterior, então dá para guardar apenas duas linhas. Você ganha memória, mas perde as decisões que levam à resposta: ainda sabe o tamanho, mas não consegue reconstruir a subsequência. Essa troca entre memória e reconstruir a solução aparece em quase todo problema de PD.

Backtracking e força bruta

Você está num labirinto. A cada cruzamento escolhe um caminho. Se chega a um beco sem saída, volta ao último cruzamento e tenta outro caminho. Isso é backtracking: uma busca em profundidade por respostas parciais que monta a solução uma decisão por vez e volta atrás quando um caminho não pode dar certo.

Seu poder está na poda. Quando uma solução parcial já é impossível, o algoritmo a descarta, e com ela todas as soluções completas que cresceriam a partir dela. Resolvedores de sudoku, labirintos e o problema das n rainhas funcionam assim.

Força bruta: tentar tudo

O método mais simples é a força bruta: gerar todo candidato e testar cada um. É fácil de acertar e funciona para entradas pequenas. Mas os candidatos se multiplicam muito rápido. No problema do caixeiro viajante, um percurso é uma ordem das cidades. Fixar a cidade de partida remove as rotações equivalentes e deixa (n − 1)! ordens para testar. Com 5 cidades são 24.

O fatorial cresce mais rápido que qualquer exponencial: cada cidade a mais multiplica o trabalho pelo número de cidades, um multiplicador que não para de crescer. Ir de 13 para 14 cidades deixa 13 vezes mais lento, e de 13 para 16 cidades deixa 13 × 14 × 15 = 2.730 vezes mais lento. No benchmark deste repositório, a força bruta levou cerca de 0,2 segundo com 11 cidades e 1,7 segundo com 12 em TypeScript, e passou de 10 segundos com 13 cidades. Uma linguagem 2 ou 3 vezes mais rápida compra cerca de uma cidade a mais.

Escolher uma boa representação

O jeito de descrever um candidato pode remover candidatos antes de qualquer busca. Pegue o problema das 8 rainhas (colocar 8 rainhas num tabuleiro de xadrez sem que uma ataque outra). Escolher 8 casas livremente entre 64 dá mais de 4 bilhões de possibilidades. Permitir só uma rainha por linha dá 8⁸ = 16 milhões. Permitir uma rainha por linha e por coluna, que são permutações, dá 8! = 40.320. O backtracking corta ainda mais, porque descarta uma colocação parcial assim que duas rainhas dividem uma diagonal.

A poda precisa ser segura

Toda regra de poda se apoia numa propriedade monótona: algo que, uma vez quebrado, continua quebrado em toda extensão. Exemplo: achar um subconjunto de números cuja soma seja exatamente T, descartando um ramo sempre que a soma parcial passa de T. Isso só está correto se todos os números forem não negativos, porque então a soma só pode crescer. Se números negativos são permitidos, um número posterior poderia trazer a soma de volta para baixo, e a poda jogaria fora respostas válidas. Antes de podar, pergunte qual suposição sobre a entrada sustenta a poda.

Branch and bound

No caixeiro viajante dá para guardar o melhor percurso completo achado até agora, como um limite. Se um caminho parcial já é tão longo quanto esse limite ou mais, nenhuma forma de completá-lo vence o melhor percurso, então você descarta o ramo. Isso se chama branch and bound (ramificar e limitar). O corte é seguro porque as distâncias não são negativas, então um caminho nunca encurta ao ser estendido. Um bom primeiro limite, por exemplo vindo da heurística do vizinho mais próximo, faz a poda começar mais cedo.

• Held-Karp é uma resposta de programação dinâmica que lembra, para cada conjunto de cidades visitadas e última cidade, o melhor caminho. Custa n²·2ⁿ, que ainda é exponencial mas muito menor que n!.
• Heurísticas como o vizinho mais próximo e o 2-opt trocam a garantia do melhor percurso por velocidade.

Algoritmos em grafos: caminho mínimo, árvore geradora, ordenação topológica

Um grafo é um conjunto de pontos, chamados vértices, ligados por linhas, chamadas arestas. Cidades e estradas, amigos e amizades, tarefas e suas dependências são grafos. As arestas podem ter um peso, como uma distância ou um custo, e podem ter direção. Seja V o número de vértices e E o número de arestas.

Árvore geradora mínima

Uma árvore geradora de um grafo conexo e não direcionado é um conjunto de arestas que liga todos os vértices sem ciclos. Começando com V vértices separados, cada aresta que não forma ciclo junta dois grupos, e são necessárias V − 1 junções para sobrar um grupo só. Então toda árvore geradora tem exatamente V − 1 arestas. A árvore geradora mínima (AGM) é a de menor peso total. Pense no conjunto mais barato de cabos para ligar todas as casas de uma cidade.

• Kruskal. Ordene as arestas por peso. Percorra-as e aceite toda aresta que junta dois grupos diferentes (conferido com uma estrutura chamada conjuntos disjuntos, ou union-find). Pare quando V − 1 arestas forem aceitas.
• Prim. Comece de um vértice e faça crescer uma única árvore. A cada passo, acrescente a aresta mais barata que liga a árvore a um vértice de fora. Os dois são gulosos, e os dois dão o mesmo peso total.

arestas: R-S 1, P-Q 2, Q-R 3, P-R 4, Q-S 6

Kruskal, em ordem de peso:
  R-S 1  aceita
  P-Q 2  aceita
  Q-R 3  aceita (junta {P,Q} e {R,S})
  P-R 4  rejeita (fecharia um ciclo)
  Q-S 6  rejeita
4 vértices -> 3 arestas, peso total 1 + 2 + 3 = 6

Caminho mínimo: Dijkstra

O Dijkstra acha o caminho mais curto de uma origem para todos os outros vértices. Ele guarda a melhor distância conhecida de cada vértice. A cada passo escolhe o vértice ainda não finalizado de menor distância, finaliza-o e relaxa suas arestas: se dist[u] + peso(u, v) < dist[v], então dist[v] é atualizado. A ideia é gulosa e correta porque estender um caminho nunca o deixa mais barato.

arestas: S-A 7, S-B 2, B-A 3, A-T 1, B-T 8

início:       S=0
finaliza S:   A=7, B=2
finaliza B:   A=min(7, 2+3)=5, T=2+8=10
finaliza A:   T=min(10, 5+1)=6
menor caminho de S a T: S-B-A-T = 6

Com um heap, o Dijkstra roda em cerca de (V + E)·log V. Ele exige pesos não negativos. Uma aresta negativa quebra a prova. Exemplo: arestas S → A com peso 3, S → B com peso 4 e B → A com peso −2. O Dijkstra finaliza o A com distância 3 (é a menor) e nunca o reabre, mas o caminho mínimo real até A é S → B → A, com custo 2. O Bellman-Ford resolve o problema: relaxa todas as arestas V − 1 vezes, em O(V·E), e também detecta ciclos negativos.

Ordenação topológica

Um grafo direcionado pode modelar dependências: 'meias antes dos sapatos'. Uma ordenação topológica lista os vértices de modo que, para toda aresta u → v, u venha antes de v. Ela só existe se o grafo não tem ciclo. Um ciclo é uma dependência circular (A precisa de B, B precisa de A), que nenhuma ordem consegue satisfazer. Pode haver várias ordenações válidas.

O algoritmo de Kahn repete isto: remover um vértice de grau de entrada zero (sem dependência pendente), colocá-lo na saída e diminuir em um o grau de entrada dos seus sucessores. Pegue Meias → Sapatos, Calça → Sapatos e Calça → Cinto. Meias e Calça começam com 0, então remova Meias (Sapatos vai a 1), remova Calça (Sapatos e Cinto vão a 0), e depois Sapatos e Cinto. O resultado: Meias, Calça, Sapatos, Cinto.

Se o algoritmo termina tendo removido menos de V vértices, o resto do grafo tem um ciclo: esses vértices sempre esperam por outro do mesmo ciclo. É assim que gerenciadores de pacotes e ferramentas de build avisam de uma dependência circular. O algoritmo de Kahn custa V + E. Para conferir uma ordem dada, percorra as arestas e confirme que a origem de cada uma aparece antes do destino.

Escolhendo a ferramenta certa

Agora você tem uma caixa de ferramentas. A habilidade é olhar um problema e escolher a ferramenta certa. Estas perguntas ajudam.

Escolhendo uma ordenação

Erros comuns

• Usar busca binária em dados que não estão ordenados.
• Confiar numa regra gulosa sem prova. Procure um contraexemplo primeiro.
• Usar Dijkstra com arestas negativas.
• Esquecer a memória de um algoritmo: o merge sort precisa de um buffer, o quicksort precisa de uma pilha.
• Culpar a linguagem quando o problema é o algoritmo. Na corrida de ordenação deste repositório, o merge sort em Python com 10.000 valores (32,7 ms) venceu o bubble sort em C++ (69,0 ms).