Algorithms, and how fast they grow.

O livro e o mapaThe book and the map

Entendendo Algoritmos (Grokking Algorithms, de Aditya Bhargava) ensina algoritmos com desenhos e exemplos do dia a dia, sem exigir matemática pesada. Um algoritmo é só uma receita: uma sequência de passos que resolve um problema. A pergunta do livro é sempre a mesma: existe um jeito mais rápido de fazer isso?Grokking Algorithms (Portuguese edition: Entendendo Algoritmos, by Aditya Bhargava) teaches algorithms with drawings and everyday examples, without heavy maths. An algorithm is just a recipe: a sequence of steps that solves a problem. The book’s question is always the same: is there a faster way to do this?

Para responder, o livro usa uma régua: a notação Big O. Por isso esta nota começa por ela e depois percorre os capítulos na ordem do livro. Cada algoritmo vem com a ideia, um exemplo e um código curto em Python.To answer it, the book uses one ruler: Big O notation. That is why this note starts there and then walks through the chapters in the book’s order. Each algorithm comes with the idea, an example and a short Python snippet.

Notação Big OBig O notation

Big O responde a uma pergunta: se a entrada ficar maior, quanto mais trabalho o algoritmo faz? Ela não mede segundos (isso depende do computador), mede a velocidade de crescimento do número de passos.Big O answers one question: if the input gets bigger, how much more work does the algorithm do? It does not measure seconds (that depends on the computer); it measures how fast the number of steps grows.

Um exemplo para começar: o livro de telefonesA first example: the phone book

Você quer achar “Moura” numa lista telefônica de 1.000 nomes em ordem alfabética. Um jeito é começar na primeira página e ir lendo: no pior caso, 1.000 passos. Outro é abrir no meio, ver se “Moura” vem antes ou depois e descartar metade: cerca de 10 passos. Com 1.000.000 de nomes, o primeiro jeito faz até 1.000.000 de passos; o segundo, cerca de 20. Os dois resolvem o problema, mas crescem de forma muito diferente. Big O dá nome a essa diferença.You want to find “Moore” in a phone book of 1,000 names in alphabetical order. One way is to start on the first page and read on: in the worst case, 1,000 steps. Another is to open in the middle, check whether “Moore” comes before or after, and discard half: about 10 steps. With 1,000,000 names the first way takes up to 1,000,000 steps; the second takes about 20. Both solve the problem, but they grow very differently. Big O gives that difference a name.

Como se lêHow to read it

O(n) lê-se “O de n”. O n é o tamanho da entrada (quantos itens) e o que está dentro dos parênteses diz como o número de passos cresce com n.O(n) reads “O of n”. The n is the input size (how many items) and what is inside the parentheses says how the number of steps grows with n.

O que o logaritmo quer dizerWhat the logarithm means

log₂ 8 = 3 responde: “quantas vezes preciso dividir 8 por 2 até chegar em 1?” (8 → 4 → 2 → 1, três vezes). É por isso que O(log n) cresce tão devagar: dobrar a entrada soma um passo. De 1.000 para 2.000 itens a busca binária faz só mais 1 palpite.log₂ 8 = 3 answers: “how many times must I halve 8 until I reach 1?” (8 → 4 → 2 → 1, three times). That is why O(log n) grows so slowly: doubling the input adds one step. Going from 1,000 to 2,000 items, binary search needs just 1 more guess. In Big O the base is dropped, so we write log n.

Quantos passos de verdade?How many steps, really?

Se cada passo levasse 1 milissegundo, O(n²) com um milhão de itens levaria uns 31 anos, enquanto O(n log n) levaria cerca de 5 horas e meia. A escolha do algoritmo importa mais do que o computador.If each step took 1 millisecond, O(n²) on a million items would take about 31 years, while O(n log n) would take about five and a half hours. The choice of algorithm matters more than the computer.

As quatro regras de bolsoFour rules of thumb

1. Pense no pior caso. Big O costuma dizer quanto o algoritmo pode demorar no pior caso. Na busca simples o pior caso é o item estar na última posição (ou não existir): n passos.Think worst case. Big O usually states how long the algorithm can take in the worst case. In simple search the worst case is the item being last (or missing): n steps.
2. Ignore constantes. Dois laços um depois do outro dão 2n passos, mas escrevemos O(n). Big O compara o formato do crescimento, não o número exato.Drop constants. Two loops one after the other give 2n steps, but we write O(n). Big O compares the shape of the growth, not the exact count.
3. Fique com o termo que domina. n² + n é O(n²), porque para n grande o n² engole o n. Um laço seguido de um laço duplo é O(n²).Keep the dominant term. n² + n is O(n²), because for large n the n² swallows the n. A loop followed by a nested loop is O(n²).
4. Laços aninhados multiplicam, laços em sequência somam. Um for dentro de outro: n × n. Um for depois do outro: n + n.Nested loops multiply, sequential loops add. A for inside another: n × n. One for after another: n + n.

def first_item(items):          # O(1): one step, however long the list is
    return items[0]

def contains(items, target):    # O(n): in the worst case looks at every item
    for item in items:
        if item == target:
            return True
    return False

def has_duplicates(items):      # O(n²): compares every item with every other
    for i in range(len(items)):
        for j in range(i + 1, len(items)):
            if items[i] == items[j]:
                return True
    return False

def halvings(n):                # O(log n): halves the problem each time
    steps = 0
    while n > 1:
        n //= 2
        steps += 1
    return steps

Memória também contaMemory counts too

O mesmo raciocínio vale para o espaço. Somar números com um laço usa uma variável a mais: O(1) de memória. Copiar a lista para outra usa O(n). Muitas vezes se troca memória por velocidade: a tabela hash do capítulo 5 gasta espaço extra para achar em um passo.The same reasoning applies to space. Summing numbers in a loop uses one extra variable: O(1) memory. Copying the list into another uses O(n). We often trade memory for speed: the hash table of chapter 5 spends extra space to find things in one step.

Capítulo 1: busca bináriaChapter 1: binary search

Estou pensando num número de 1 a 100 e você tenta adivinhar. Chutar 1, 2, 3… é a busca simples: no pior caso 100 palpites. Chutar 50 e ouvir “é maior” ou “é menor” é a busca binária: cada palpite elimina metade, e 7 palpites bastam para 100 números.I am thinking of a number from 1 to 100 and you try to guess it. Guessing 1, 2, 3… is simple search: 100 guesses in the worst case. Guessing 50 and hearing “higher” or “lower” is binary search: each guess eliminates half, and 7 guesses are enough for 100 numbers.

def simple_search(items, target):       # O(n)
    for index, item in enumerate(items):
        if item == target:
            return index
    return None


def binary_search(items, target):       # O(log n); items must be sorted
    low, high = 0, len(items) - 1
    while low <= high:
        mid = (low + high) // 2
        guess = items[mid]
        if guess == target:
            return mid
        if guess > target:
            high = mid - 1
        else:
            low = mid + 1
    return None

O problema do caixeiro-viajanteThe travelling salesperson problem

O livro fecha o capítulo com um vendedor que precisa passar por n cidades gastando o mínimo de estrada. A solução óbvia testa todas as ordens: O(n!). Com 5 cidades são 120 rotas; com 10, 3,6 milhões; com 20, mais de 2 quintilhões. É o exemplo clássico de um algoritmo que existe, mas é lento demais.The book closes the chapter with a salesperson who must visit n cities using the least road. The obvious solution tries every order: O(n!). With 5 cities that is 120 routes; with 10, 3.6 million; with 20, over 2 quintillion. It is the classic example of an algorithm that exists but is too slow.

Capítulo 2: memória e ordenação por seleçãoChapter 2: memory and selection sort

Antes de ordenar, o livro mostra como os dados ficam na memória. Imagine uma gaveta numerada por onde você guarda coisas.Before sorting, the book shows how data sits in memory. Picture a numbered set of drawers where you keep things.

• Array: os itens ficam em gavetas vizinhas. Ler o item de índice 5 é imediato, mas inserir no meio obriga a empurrar todos os seguintes.Array: items sit in neighbouring drawers. Reading index 5 is immediate, but inserting in the middle forces you to shift everything after it.
• Lista encadeada: cada item guarda o endereço do próximo e pode estar em qualquer gaveta. Inserir é fácil (muda um endereço), mas para chegar ao 5º item é preciso passar pelos 4 anteriores.Linked list: each item stores the address of the next and can live in any drawer. Inserting is easy (change one address), but reaching the 5th item means walking through the previous 4.

*Depois de já estar na posição. Chegar até ela custa O(n). Na prática, arrays vencem na maioria dos casos porque a leitura é muito usada e os itens vizinhos ficam no cache do processador.*Once you are already at the position. Getting there costs O(n). In practice arrays win in most cases because reading is so common and neighbouring items sit in the processor cache.

Ordenação por seleçãoSelection sort

A ideia: ache o menor item, passe-o para uma lista nova, repita. Encontrar o menor custa n passos e isso se repete n vezes, então o total é O(n²). (Na verdade n + (n−1) + … + 1, mas Big O ignora a metade, que é uma constante.)The idea: find the smallest item, move it to a new list, repeat. Finding the smallest costs n steps and this repeats n times, so the total is O(n²). (It is really n + (n−1) + … + 1, but Big O drops the half, a constant.)

def find_smallest(items):
    smallest, smallest_index = items[0], 0
    for i in range(1, len(items)):
        if items[i] < smallest:
            smallest, smallest_index = items[i], i
    return smallest_index


def selection_sort(items):              # O(n²)
    items = list(items)                 # works on a copy
    result = []
    while items:
        result.append(items.pop(find_smallest(items)))
    return result

Capítulo 3: recursãoChapter 3: recursion

Recursão é uma função que chama a si mesma com um problema menor. A analogia do livro: procurar a chave numa caixa que tem outras caixas dentro. Você abre uma caixa; se achar uma caixa menor, repete o mesmo processo nela; se achar a chave, para.Recursion is a function that calls itself with a smaller problem. The book’s analogy: looking for a key in a box that holds other boxes. You open a box; if you find a smaller box, you repeat the same process on it; if you find the key, you stop.

Toda função recursiva precisa de duas partes: o caso base, que para a recursão, e o caso recursivo, que chama a função de novo com algo menor. Sem caso base ela chama a si mesma para sempre, até estourar a memória.Every recursive function needs two parts: the base case, which stops the recursion, and the recursive case, which calls the function again with something smaller. Without a base case it calls itself forever, until memory runs out.

def factorial(n):
    if n <= 1:                  # base case: stops the recursion
        return 1
    return n * factorial(n - 1) # recursive case: a smaller problem


def total(numbers):             # sum of a list, no loop
    if not numbers:
        return 0
    return numbers[0] + total(numbers[1:])

A pilha de chamadasThe call stack

O computador guarda as chamadas pendentes numa pilha: a última a entrar é a primeira a sair, como pratos empilhados. Em factorial(3) a pilha chega a 3 chamadas. Cada chamada ocupa memória, então recursão muito profunda usa muito espaço (O(n) para o fatorial). Toda recursão pode virar um laço; às vezes o laço é mais barato, às vezes a recursão é mais clara. O livro diz: o laço pode ser mais rápido, a recursão torna a solução mais fácil de entender.The computer keeps pending calls in a stack: last in, first out, like stacked plates. In factorial(3) the stack reaches 3 calls. Each call takes memory, so very deep recursion uses a lot of space (O(n) for factorial). Any recursion can become a loop; sometimes the loop is cheaper, sometimes recursion is clearer. The book’s take: a loop may be faster, but recursion makes the solution easier to understand.

Capítulo 4: quicksort e dividir e conquistarChapter 4: quicksort and divide and conquer

Dividir e conquistar (D&C) é um jeito de pensar com dois passos: ache o caso mais simples (o caso base) e descubra como reduzir o problema até ele cair nesse caso.Divide and conquer (D&C) is a way of thinking in two steps: find the simplest case (the base case) and work out how to shrink the problem until it falls into that case.

Exemplo: dividir um terrenoExample: splitting a plot of land

Você tem um terreno de 1.680 × 640 m e quer dividi-lo em quadrados iguais, os maiores possíveis. Caso base: se um lado é múltiplo do outro, o lado menor é o quadrado. Senão, corte o maior quadrado possível (640 × 640) e repita com o que sobrou (400 × 640), e assim por diante, até sobrar um quadrado de 80 × 80. É o algoritmo de Euclides, e é D&C puro.You have a 1,680 × 640 m plot and want to split it into equal squares, as large as possible. Base case: if one side is a multiple of the other, the smaller side is the square. Otherwise cut the largest possible square (640 × 640) and repeat with the leftover (400 × 640), and so on, until a 80 × 80 square remains. That is Euclid’s algorithm, and it is pure D&C.

QuicksortQuicksort

1. Escolha um item como pivô.Pick an item as the pivot.
2. Separe o resto em dois grupos: os menores que o pivô e os maiores.Split the rest into two groups: smaller than the pivot and larger.
3. Ordene cada grupo do mesmo jeito (recursão) e junte: menores + pivô + maiores.Sort each group the same way (recursion) and join: smaller + pivot + larger.

def quicksort(items):                   # O(n log n) on average
    if len(items) < 2:                  # base case
        return items
    pivot = items[0]
    smaller = [x for x in items[1:] if x <= pivot]
    larger = [x for x in items[1:] if x > pivot]
    return quicksort(smaller) + [pivot] + quicksort(larger)

Exemplo: [5, 2, 9, 1], pivô 5. Menores: [2, 1]; maiores: [9]. Ordenando os menores sai [1, 2]. Resultado: [1, 2] + [5] + [9].Example: [5, 2, 9, 1], pivot 5. Smaller: [2, 1]; larger: [9]. Sorting the smaller gives [1, 2]. Result: [1, 2] + [5] + [9].

Por que O(n log n) e quando vira O(n²)Why O(n log n) and when it becomes O(n²)

Se o pivô divide a lista mais ou menos ao meio, a pilha tem cerca de log n níveis e cada nível percorre n itens: n × log n. Se o pivô for sempre o menor ou o maior item (por exemplo, a lista já ordenada e o pivô sempre o primeiro), a pilha tem n níveis: O(n²). A defesa é escolher o pivô ao acaso (ou o do meio): na média o resultado é O(n log n).If the pivot splits the list roughly in half, the stack has about log n levels and each level walks n items: n × log n. If the pivot is always the smallest or largest item (for example, an already sorted list with the first item as pivot), the stack has n levels: O(n²). The defence is to pick the pivot at random (or the middle one): on average it is O(n log n).

Capítulo 5: tabelas hashChapter 5: hash tables

Pense no caixa de um mercado que sabe o preço de tudo de cabeça. Você diz “leite” e ele responde “5 reais” sem folhear um catálogo. A tabela hash é isso: uma estrutura que associa chaves a valores e responde em um passo. Em Python, é o dict.Think of a supermarket cashier who knows every price by heart. You say “milk” and they answer “$0.99” without flipping through a catalogue. A hash table is that: a structure that maps keys to values and answers in one step. In Python it is the dict.

Por dentro há um array e uma função hash: ela recebe a chave e devolve sempre o mesmo índice. A chave “leite” cai na posição 4, por exemplo, e o valor fica lá. Para ler, a função diz onde olhar.Inside there is an array and a hash function: it takes the key and always returns the same index. The key “milk” lands on slot 4, say, and the value is stored there. To read, the function tells you where to look.

voted = {}


def check_voter(name):
    if voted.get(name):                 # O(1) on average
        return "send them away"
    voted[name] = True
    return "let them vote"

UsosUses

• Busca por nome: agenda de telefones, DNS (domínio → IP).Lookup by name: phone book, DNS (domain → IP).
• Evitar duplicados: a lista de quem já votou (o exemplo do código).Avoiding duplicates: the list of who already voted (the code example).
• Cache: guardar o resultado de uma consulta cara para não repeti-la.Caching: keep the result of an expensive query so you do not repeat it.

Colisões e fator de cargaCollisions and load factor

Uma colisão acontece quando duas chaves dão o mesmo índice. A saída comum é guardar uma lista curta naquela posição. Se a lista crescer demais, a busca vira O(n). Para evitar isso: uma boa função hash (espalha bem) e um fator de carga baixo, que é itens ÷ posições. Quando passa de uns 0,7, a tabela cresce e redistribui os itens.A collision happens when two keys give the same index. The common fix is to keep a short list at that slot. If the list grows too long, lookup becomes O(n). To avoid it: a good hash function (spreads well) and a low load factor, which is items ÷ slots. Past roughly 0.7 the table grows and redistributes the items.

Capítulo 6: busca em larguraChapter 6: breadth-first search

Um grafo é um conjunto de nós ligados por arestas: pessoas e amizades, cidades e estradas, páginas e links. A busca em largura (BFS) responde a duas perguntas: existe um caminho de A até B? e qual é o menor, em número de passos?A graph is a set of nodes joined by edges: people and friendships, cities and roads, pages and links. Breadth-first search (BFS) answers two questions: is there a path from A to B? and which is the shortest, in number of steps?

O exemplo do livro: você quer achar, entre seus amigos, alguém que venda manga. Primeiro pergunta aos amigos diretos; se nenhum vende, pergunta aos amigos dos amigos, e assim por diante. Os mais próximos são verificados antes dos mais distantes, e por isso o primeiro vendedor encontrado está no menor caminho.The book’s example: you want to find a mango seller among your contacts. First you ask your direct friends; if none sells, you ask friends of friends, and so on. The nearest are checked before the farthest, so the first seller found is on the shortest path.

A ferramenta é uma fila (primeiro a entrar, primeiro a sair, como a fila do banco). Os amigos entram na fila; ao tirar alguém, você o verifica e coloca os amigos dele no fim. E guarde quem já foi verificado: sem isso, Alice e Bob (amigos de Peggy) fariam você verificar Peggy duas vezes e, em grafos com ciclos, nunca terminar.The tool is a queue (first in, first out, like a bank line). Friends join the queue; when you take someone out you check them and add their friends at the end. And remember who was already checked: without that, Alice and Bob (both friends of Peggy) would make you check Peggy twice and, in graphs with cycles, never finish.

from collections import deque

graph = {
    "you": ["alice", "bob", "claire"],
    "bob": ["anuj", "peggy"],
    "alice": ["peggy"],
    "claire": ["thom", "jonny"],
    "anuj": [], "peggy": [], "thom": [], "jonny": [],
}


def is_seller(name):
    return name.endswith("m")           # in the book: "name ends with m"


def search(start):
    queue = deque(graph[start])
    searched = set()
    while queue:
        person = queue.popleft()        # first in, first out
        if person in searched:
            continue
        if is_seller(person):
            return person
        queue.extend(graph[person])
        searched.add(person)
    return None

Custo: O(V + E), onde V são os nós (vértices) e E as arestas: cada pessoa entra na fila uma vez e cada amizade é olhada uma vez.Cost: O(V + E), where V is the nodes (vertices) and E the edges: each person enters the queue once and each friendship is looked at once.

Árvores e ordenação topológicaTrees and topological sort

Uma árvore é um grafo sem ciclos e com uma raiz (como uma árvore genealógica ou as pastas do computador). E, se as arestas têm sentido e dependem umas das outras (“escovar os dentes depende de acordar”), a ordenação topológica monta uma lista de tarefas respeitando as dependências: é o que um gerenciador de pacotes faz.A tree is a graph without cycles and with a root (like a family tree or the folders on your computer). And if edges have a direction and depend on each other (“brushing teeth depends on waking up”), topological sort builds a task list that respects the dependencies: it is what a package manager does.

Capítulo 7: algoritmo de DijkstraChapter 7: Dijkstra’s algorithm

A busca em largura acha o caminho com menos passos. Mas e se cada aresta tiver um custo (minutos, quilômetros, reais)? Num grafo ponderado, o caminho com menos passos pode ser o mais caro. Dijkstra acha o caminho de menor custo total.Breadth-first search finds the path with the fewest steps. But what if each edge has a cost (minutes, kilometres, money)? In a weighted graph the path with fewest steps can be the most expensive one. Dijkstra finds the path of lowest total cost.

1. Encontre o nó mais barato de alcançar que ainda não foi processado.Find the cheapest node still unprocessed.
2. Atualize o custo de seus vizinhos: se passar por este nó sai mais barato, guarde o novo custo e o “pai”.Update its neighbours’ costs: if going through this node is cheaper, store the new cost and the “parent”.
3. Marque o nó como processado e repita até chegar ao destino.Mark the node as processed and repeat until you reach the target.
4. Siga os “pais” de trás para frente para montar o caminho.Follow the “parents” backwards to rebuild the path.

import heapq

graph = {
    "start": {"a": 6, "b": 2},
    "a": {"end": 1},
    "b": {"a": 3, "end": 5},
    "end": {},
}


def dijkstra(graph, source, target):
    costs = {source: 0}
    parents = {}
    heap = [(0, source)]                # (cost, node), smallest cost first
    while heap:
        cost, node = heapq.heappop(heap)
        if node == target:
            break
        if cost > costs.get(node, float("inf")):
            continue                    # outdated entry
        for neighbor, weight in graph[node].items():
            new_cost = cost + weight
            if new_cost < costs.get(neighbor, float("inf")):
                costs[neighbor] = new_cost
                parents[neighbor] = node
                heapq.heappush(heap, (new_cost, neighbor))
    path = [target]
    while path[-1] != source:
        path.append(parents[path[-1]])
    return costs[target], path[::-1]

Capítulo 8: algoritmos gulosos e problemas NP-completosChapter 8: greedy algorithms and NP-complete problems

Um algoritmo guloso escolhe, a cada passo, a melhor opção agora, sem olhar para o futuro. Nem sempre dá a resposta perfeita, mas costuma dar uma boa, e rápido.A greedy algorithm picks, at each step, the best option right now, without looking ahead. It does not always give the perfect answer, but it usually gives a good one, fast.

Exemplo: marcar aulas numa salaExample: scheduling classes in a room

Muitas aulas disputam a mesma sala e você quer caber o máximo delas. Estratégia gulosa: pegue a aula que termina mais cedo, descarte as que se sobrepõem a ela, repita. Esse caso específico é ótimo, não só aproximado.Many classes compete for the same room and you want to fit as many as possible. Greedy strategy: take the class that ends earliest, discard those that overlap it, repeat. This particular case is optimal, not just approximate.

Exemplo: cobertura de estações de rádioExample: covering states with radio stations

Você quer que seu programa de rádio chegue a 8 estados usando o menor número de estações, e cada estação cobre alguns estados. Testar todas as combinações é O(2ⁿ). O guloso escolhe a estação que cobre mais estados ainda descobertos, repete, e termina rápido (aqui, 4 estações).You want your radio show to reach 8 states using as few stations as possible, and each station covers a few states. Trying every combination is O(2ⁿ). The greedy picks the station covering the most still-uncovered states, repeats, and finishes fast (here, 4 stations).

states_needed = {"mt", "wa", "or", "id", "nv", "ut", "ca", "az"}
stations = {
    "kone": {"id", "nv", "ut"},
    "ktwo": {"wa", "id", "mt"},
    "kthree": {"or", "nv", "ca"},
    "kfour": {"nv", "ut"},
    "kfive": {"ca", "az"},
}

final_stations = set()
while states_needed:
    best_station, states_covered = None, set()
    for station, states in stations.items():
        covered = states_needed & states
        if len(covered) > len(states_covered):
            best_station, states_covered = station, covered
    states_needed -= states_covered
    final_stations.add(best_station)

NP-completoNP-complete

Há problemas para os quais ninguém conhece um algoritmo rápido, como o caixeiro-viajante e a cobertura de conjuntos acima. Eles são chamados NP-completos. O livro dá pistas para reconhecer um: o algoritmo roda rápido com poucos itens e fica absurdamente lento quando eles aumentam; o enunciado fala em “todas as combinações” ou “todas as ordens”; você não consegue dividir em subproblemas menores. Nesses casos, em vez de procurar a resposta perfeita, use um algoritmo de aproximação (como o guloso) e aceite uma resposta boa.There are problems for which nobody knows a fast algorithm, like the travelling salesperson and the set cover above. They are called NP-complete. The book gives clues to spot one: the algorithm is fast with few items and absurdly slow as they grow; the statement says “all combinations” or “all orders”; you cannot break it into smaller subproblems. In those cases, instead of chasing the perfect answer, use an approximation algorithm (like the greedy one) and accept a good answer.

Capítulo 9: programação dinâmicaChapter 9: dynamic programming

Programação dinâmica resolve um problema difícil quebrando-o em subproblemas menores, resolvendo cada um uma só vez e guardando as respostas numa tabela (grade). O truque é descobrir quais são os subproblemas.Dynamic programming solves a hard problem by splitting it into smaller subproblems, solving each one only once and storing the answers in a table (grid). The trick is finding what the subproblems are.

Problema da mochilaThe knapsack problem

Você é ladrão (hipoteticamente) com uma mochila que aguenta 4 kg. Itens: violão (1 kg, R$ 1.500), aparelho de som (4 kg, R$ 3.000) e notebook (3 kg, R$ 2.000). O guloso levaria o som (o mais caro) e ficaria com R$ 3.000. A grade abaixo testa cada capacidade de 1 a 4 kg, adicionando um item por linha. Cada célula é o maior valor possível com os itens até aquela linha e aquele peso.You are a (hypothetical) thief with a knapsack that holds 4 kg. Items: guitar (1 kg, $1,500), stereo (4 kg, $3,000) and laptop (3 kg, $2,000). Greedy would take the stereo (the priciest) and end with $3,000. The grid below tests each capacity from 1 to 4 kg, adding one item per row. Each cell is the best value possible using the items up to that row and that weight.

A última célula vem da fórmula: max(valor sem o item, valor do item + melhor com o peso que sobra). Para o notebook com 4 kg: máximo entre 3.000 (de cima) e 2.000 + 1.500 (notebook + o melhor com 1 kg) = 3.500. A resposta é violão + notebook.The last cell comes from the formula: max(value without the item, item value + best with the leftover weight). For the laptop at 4 kg: the max of 3,000 (from above) and 2,000 + 1,500 (laptop + the best at 1 kg) = 3,500. The answer is guitar + laptop.

def knapsack(items, capacity):          # items: [(name, weight, value)]
    grid = [[0] * (capacity + 1) for _ in range(len(items) + 1)]
    for i, (name, weight, value) in enumerate(items, start=1):
        for w in range(1, capacity + 1):
            best = grid[i - 1][w]                       # without this item
            if weight <= w:
                best = max(best, value + grid[i - 1][w - weight])
            grid[i][w] = best
    return grid[-1][-1]

Custo: O(itens × capacidade), muito melhor que testar todos os subconjuntos (O(2ⁿ)).Cost: O(items × capacity), far better than trying every subset (O(2ⁿ)).

Maior subsequência e maior substring comumLongest common substring and subsequence

O mesmo molde de grade serve para comparar duas palavras, como faz um corretor ortográfico ou o diff do git. Para fish e hish, a maior substring comum (letras seguidas) é ish, de tamanho 3. A subsequência aceita letras não vizinhas, desde que na mesma ordem: fosh e fish compartilham fsh (3).The same grid template compares two words, as a spell checker or git’s diff does. For fish and hish, the longest common substring (consecutive letters) is ish, length 3. A subsequence allows non-adjacent letters in the same order: fosh and fish share fsh (3).

def longest_common_substring(a, b):
    best = 0
    cell = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
    for i in range(1, len(a) + 1):
        for j in range(1, len(b) + 1):
            if a[i - 1] == b[j - 1]:
                cell[i][j] = cell[i - 1][j - 1] + 1
                best = max(best, cell[i][j])
    return best


def longest_common_subsequence(a, b):
    cell = [[0] * (len(b) + 1) for _ in range(len(a) + 1)]
    for i in range(1, len(a) + 1):
        for j in range(1, len(b) + 1):
            if a[i - 1] == b[j - 1]:
                cell[i][j] = cell[i - 1][j - 1] + 1
            else:
                cell[i][j] = max(cell[i - 1][j], cell[i][j - 1])
    return cell[-1][-1]

Capítulo 10: k-vizinhos mais próximosChapter 10: k-nearest neighbours

Para classificar algo novo, olhe o que se parece com ele. É o k-NN. O exemplo do livro: frutas. Se você tem laranjas e toranjas num gráfico de tamanho × cor e aparece uma fruta nova, olhe as k mais próximas (por exemplo 3) e vote: se a maioria for toranja, é toranja.To classify something new, look at what resembles it. That is k-NN. The book’s example: fruit. If you have oranges and grapefruits on a size × colour chart and a new fruit shows up, look at the nearest k (say 3) and vote: if most are grapefruit, it is a grapefruit.

“Perto” é calculado com a fórmula da distância. Com duas características é o teorema de Pitágoras; com cinco, a mesma conta com mais termos: √((a₁−b₁)² + (a₂−b₂)² + …). O livro usa isso para recomendar filmes: cada pessoa vira um ponto (as notas que deu a cada gênero) e você recomenda o que a pessoa mais próxima gostou.“Near” is computed with the distance formula. With two features it is the Pythagorean theorem; with five, the same sum with more terms: √((a₁−b₁)² + (a₂−b₂)² + …). The book uses this to recommend movies: each person becomes a point (the ratings they gave to each genre) and you recommend what the nearest person liked.

from math import sqrt

ratings = {                 # comedy, action, drama, horror, romance (invented)
    "priyanka": (3, 4, 4, 1, 4),
    "justin": (4, 3, 5, 1, 5),
    "morpheus": (2, 5, 1, 3, 1),
}


def distance(a, b):
    return sqrt(sum((x - y) ** 2 for x, y in zip(a, b)))


def nearest(name, k=1):
    others = [(distance(ratings[name], r), n) for n, r in ratings.items() if n != name]
    return sorted(others)[:k]

Aqui nearest("priyanka") devolve Justin (distância 2,0), então os filmes que Justin adorou são bons candidatos para Priyanka. (Notas inventadas, só para ilustrar.)Here nearest("priyanka") returns Justin (distance 2.0), so the movies Justin loved are good candidates for Priyanka. (Invented ratings, for illustration only.)

Regressão, escolha de características e aprendizado de máquinaRegression, picking features and machine learning

• Classificação responde “a qual grupo pertence?” (sim/não, laranja/toranja). Regressão responde “quanto?”: prever uma nota ou quantos pães vender amanhã tirando a média dos vizinhos.Classification answers “which group does it belong to?” (yes/no, orange/grapefruit). Regression answers “how much?”: predict a rating or how many loaves to sell tomorrow by averaging the neighbours.
• Escolher boas características é o que mais pesa: devem estar ligadas ao que se quer prever e não podem ter viés (por exemplo, pedir só notas de quem ama comédia).Picking good features matters most: they must relate to what you predict and must not be biased (for example, asking only people who love comedy).
• Com a distância do cosseno, em vez da euclidiana, duas pessoas que dão notas altas e baixas em padrões parecidos são vizinhas mesmo que uma seja mais generosa.With cosine similarity instead of Euclidean distance, two people who give highs and lows in similar patterns are neighbours even if one is more generous.
• O k-NN é a porta de entrada do aprendizado de máquina: reconhecimento de dígitos (OCR), filtro de spam e recomendação, em que o modelo é “treinado” com exemplos já conhecidos.k-NN is the gateway to machine learning: digit recognition (OCR), spam filters and recommendation, where the model is “trained” on known examples.

Capítulo 11: para onde ir depoisChapter 11: where to go next

O último capítulo é um mapa rápido de dez ideias para estudar em seguida, cada uma com uma frase de apresentação.The last chapter is a quick map of ideas to study next, each with a one-line introduction.

Resumo: algoritmo e Big OCheat sheet: algorithm and Big O

Como estudar e aplicarHow to study and apply

1. Antes de escrever um laço dentro de outro, pergunte: isto é O(n²)? Dá para trocar um dos laços por um dict ou um set?Before writing a loop inside another, ask: is this O(n²)? Can one of the loops be replaced by a dict or a set?
2. Antes de buscar muitas vezes numa lista, considere ordená-la (e usar bisect) ou convertê-la num set.Before searching a list many times, consider sorting it (and using bisect) or converting it to a set.
3. Para relações entre coisas (amigos, rotas, dependências), desenhe o grafo primeiro; quase sempre é BFS ou Dijkstra.For relationships between things (friends, routes, dependencies), draw the graph first; it is almost always BFS or Dijkstra.
4. Se o problema parece exigir “todas as combinações”, suspeite de NP-completo e procure uma aproximação.If the problem seems to require “all the combinations”, suspect NP-complete and look for an approximation.
5. Para praticar: implemente cada código desta nota sem olhar, depois cronometre com listas de 1.000, 10.000 e 100.000 itens e confira se o tempo cresce como o Big O prevê.To practise: implement each snippet in this note without looking, then time it with lists of 1,000, 10,000 and 100,000 items and check that the time grows as Big O predicts.