Os principais conceitos do livro, explicados sem complicação
Algoritmo é só uma palavra chique pra "um conjunto de passos pra resolver um problema". O livro usa exemplos bem visuais pra mostrar como pequenas decisões na hora de programar podem fazer uma diferença gigantesca quando o tanto de dado cresce. Aqui vai um resumo dos principais capítulos, do jeito mais simples possível.
Pesquisa binária: por que dividir é mais rápido que procurar um por um
Imagina procurar uma palavra no dicionário. Você não começa na primeira página e vai virando uma por uma — você abre no meio, vê se a palavra vem antes ou depois, e repete esse processo, descartando metade das páginas a cada tentativa. Isso é pesquisa binária, e ela é muito mais rápida do que checar item por item.
Aqui entra um conceito central do livro: a velocidade de um algoritmo não é medida em segundos, porque isso depende do computador, da internet, de um monte de coisa. Ela é medida em quantas operações o algoritmo precisa fazer conforme a quantidade de dados cresce — e isso é representado pela notação Big O. Uma pesquisa simples cresce na proporção do tamanho da lista (chamada de O(n)); a pesquisa binária cresce muito mais devagar (O(log n)). Quanto maior a lista, maior a vantagem da binária.
Como o computador guarda as coisas: arrays e listas
Pensa na memória do computador como um armário gigante cheio de gavetas numeradas. Quando você precisa guardar vários itens, tem duas formas comuns de fazer isso: array ou lista encadeada.
No array, todos os itens ficam um do lado do outro, em gavetas vizinhas — isso torna a leitura super rápida, porque o computador sabe exatamente onde cada item está. Na lista encadeada, os itens ficam espalhados por aí, e cada um guarda o endereço de onde está o próximo. Isso torna inserir ou remover itens bem mais rápido, já que você não precisa reorganizar nada — só ajustar os "endereços". A troca é simples: array é melhor pra ler, lista é melhor pra inserir e remover.
Recursão: uma função que chama a si mesma
Recursão é quando uma função, no meio do seu próprio código, chama ela mesma de novo. Toda função recursiva precisa de duas partes: um caso-base (a condição que faz ela parar) e um caso recursivo (onde ela chama a si mesma de novo, com um problema menor). Cada chamada vai se empilhando na memória do computador — literalmente numa estrutura chamada pilha — e se essa recursão for grande demais, ela pode consumir bastante memória.
Quicksort: dividir para conquistar
O quicksort é um dos algoritmos de ordenação mais usados, e ele segue uma estratégia chamada "dividir para conquistar": pega um problema grande, quebra ele em pedaços menores, resolve cada pedaço e junta tudo de novo. Na prática, ele escolhe um elemento aleatório como referência (o pivô), separa os menores de um lado e os maiores do outro, e repete isso recursivamente. Em média, o tempo de execução dele é bem eficiente — mais rápido, inclusive, que outro algoritmo parecido chamado merge sort, por causa de detalhes de implementação que fazem diferença na prática, mesmo quando os dois "crescem" matematicamente parecido.
Tabelas hash: a estrutura mais versátil do livro
Uma tabela hash combina uma função que transforma qualquer informação num número (a função hash) com um array. É isso que torna possível, por exemplo, buscar o preço de um produto pelo nome dele quase instantaneamente, sem precisar percorrer uma lista inteira. Tabelas hash são extremamente rápidas pra buscar, inserir e remover itens, e são ótimas pra modelar relações entre duas coisas (tipo "esse nome de usuário pertence a essa senha"). O único cuidado é com colisões — quando duas informações diferentes acabam caindo no mesmo lugar — e com o fator de carga, que indica se a tabela está ficando cheia demais e precisa ser redimensionada.
Pesquisa em largura: o caminho mais curto entre dois pontos
Essa técnica responde a uma pergunta bem comum: existe um caminho entre o ponto A e o ponto B? E, se existir, qual é o caminho mais curto? Ela funciona em cima de grafos — estruturas que representam conexões entre coisas. Um grafo pode ser direcionado (a relação só vale num sentido, tipo "Rama deve dinheiro a Adit") ou não direcionado (a relação vale nos dois sentidos, tipo "Ross namorou Rachel"). Pra fazer a pesquisa em largura funcionar corretamente, é essencial usar uma fila — que respeita a ordem de chegada — e nunca verificar a mesma pessoa duas vezes, senão o algoritmo pode entrar num loop sem fim.
Algoritmo de Dijkstra: quando o caminho tem "peso"
A pesquisa em largura é ótima quando todos os caminhos têm o mesmo "custo". Mas e quando alguns caminhos são mais rápidos, mais baratos ou mais curtos que outros? Aí entra o algoritmo de Dijkstra, que calcula o caminho mais barato num grafo com pesos — desde que todos esses pesos sejam positivos. Se algum peso for negativo, é preciso usar outro algoritmo, chamado Bellman-Ford.
Algoritmos gulosos: resolver aproximadamente quando o exato é caro demais
Um algoritmo guloso toma sempre a melhor decisão possível naquele momento, na esperança de que essas pequenas decisões boas somadas resultem numa solução boa no final — mesmo sem garantia de que seja a melhor solução possível. Eles são úteis principalmente pra um tipo de problema chamado NP-completo, que não tem uma solução rápida conhecida. Nesses casos, como não dá pra calcular a resposta perfeita em tempo razoável, usar um algoritmo guloso como aproximação — simples de escrever e rápido de rodar — costuma ser a melhor saída.
Programação dinâmica: resolver quebrando em pedacinhos
Programação dinâmica é útil quando você está tentando otimizar algo dentro de um limite — por exemplo, encaixar o máximo de valor possível numa mochila com peso limitado. A ideia central é dividir o problema em subproblemas menores e guardar as respostas desses subproblemas pra não precisar recalculá-las depois. Não existe uma fórmula única que funcione pra todo problema desse tipo — cada caso pede que você pense em como quebrar aquele problema específico em partes menores.
K-vizinhos mais próximos: aprender por comparação
Esse algoritmo é usado em machine learning pra duas tarefas: classificação (colocar algo dentro de uma categoria) e regressão (estimar um número, tipo um preço). A lógica é simples: pra classificar um item novo, você olha pros K itens mais parecidos com ele que você já conhece, e usa essas semelhanças pra tomar a decisão. Pra isso funcionar bem, é preciso primeiro transformar cada item — uma fruta, um usuário, o que for — numa lista de números comparáveis (isso se chama extrair características), e escolher essas características com cuidado, porque é disso que depende a qualidade do resultado.
No fim das contas, o livro mostra que algoritmo bom não é sobre decorar fórmula — é sobre reconhecer o tipo de problema que você tem na mão e saber qual ferramenta combina melhor com ele.