🎯

Técnicas Algorítmicas

Para desenvolvedores sêniores que trabalham intensamente com frameworks como Spring Boot e soluções de persistência como Hibernate, os algoritmos e suas estruturas de projeto subjacentes podem parecer distantes do cotidiano. No entanto, o conhecimento profundo de recursão, divisão e conquista, algoritmos gulosos, backtracking e programação dinâmica é o que diferencia o arquiteto capaz de resolver problemas complexos de desempenho e otimização de recursos daqueles que apenas empilham dependências. Este módulo revisita estes conceitos vitais sob a ótica da JVM, avaliando limitações físicas, trade-offs e corretude.

🧵Analogia

Recursão e Backtracking — O Fio de Ariadne no Labirinto

Imagine entrar em um labirinto escuro procurando um tesouro sem ter um mapa completo. Uma estratégia puramente recursiva é: avance um passo. Se for um beco sem saída, retorne. Mas como você se lembra do caminho de volta para não se perder? Você usa o 'Fio de Ariadne', que na JVM é representado pela Call Stack (pilha de chamadas). Cada decisão de direção cria um novo nó no fio. Se você bater em uma parede, você recolhe o fio até a última bifurcação (isso é o 'unchoose' ou backtracking) e tenta o outro caminho. O perigo? Se o labirinto for circular e você esquecer de marcar por onde já passou (caso base ou controle de ciclo), o fio acabará de forma catastrófica (o temido StackOverflowError).

💡Conceito

Recursão, Call Stack e o Framework de Backtracking

A recursão divide um problema chamando a si mesma com dados reduzidos até atingir o caso base. Sem ele, a execução gera recursão infinita, estourando os limites de memória alocados para a stack da thread (StackOverflowError). Cada chamada recursiva aloca um novo stack frame contendo variáveis locais e o endereço de retorno. Vale ressaltar que a JVM padrão (HotSpot) não realiza Otimização de Chamada de Cauda (Tail Call Optimization - TCO) para poupar memória, pois exige a preservação do stack trace completo para auditoria de segurança baseada em pilha e geração de relatórios de depuração. O Backtracking estende a recursão para problemas de busca em espaços de estados, operando em um ciclo contínuo de: (1) Choose (efetuar alteração no estado), (2) Explore (chamar recursivamente para validar ramificações) e (3) Unchoose (reverter a alteração de estado ao retornar, liberando o caminho para testes alternativos).

🔧Exemplo

Gerador de Permutações via Backtracking

import java.util.*;

public class Permutador {
    public static List<List<Integer>> permutar(int[] nums) {
        List<List<Integer>> resultado = new ArrayList<>();
        // Controlamos o estado usado para poda (pruning)
        backtrack(resultado, new ArrayList<>(), nums, new boolean[nums.length]);
        return resultado;
    }

    private static void backtrack(List<List<Integer>> res, List<Integer> temp, int[] nums, boolean[] usado) {
        // Caso Base: completou uma permutação de tamanho N
        if (temp.size() == nums.length) {
            res.add(new ArrayList<>(temp)); // Cria cópia profunda pois temp é mutável e compartilhado
            return;
        }
        
        for (int i = 0; i < nums.length; i++) {
            if (usado[i]) continue; // Poda (pruning): evita processar elementos já presentes
            
            // 1. Choose (Escolher)
            usado[i] = true;
            temp.add(nums[i]);
            
            // 2. Explore (Explorar)
            backtrack(res, temp, nums, usado);
            
            // 3. Unchoose (Desfazer a escolha para o próximo loop)
            temp.remove(temp.size() - 1);
            usado[i] = false;
        }
    }
}

🧗Analogia

Algoritmos Gulosos vs DP — A Escalada da Montanha

Imagine escalar uma montanha sob neblina densa. Um algoritmo Guloso (Greedy) equivale a olhar apenas para os seus pés e, a cada bifurcação, escolher a trilha que sobe de forma mais íngreme naquele instante (escolha localmente ótima). É uma estratégia extremamente rápida e simples, mas que pode te deixar preso em um pequeno monte secundário (máximo local) sem nunca alcançar o cume real da montanha. Já a Programação Dinâmica (DP) é como mapear a montanha com um drone. O drone analisa todas as rotas possíveis, anota as altitudes de todos os acampamentos intermediários em uma planilha e calcula a trilha perfeita para o cume verdadeiro, mesmo que isso exija descer alguns metros antes de subir novamente.

💡Conceito

Algoritmos Gulosos e a Prova de Corretude por Troca

Algoritmos Gulosos (Greedy) tomam a melhor decisão local a cada passo na expectativa de encontrar o ótimo global. Eles são altamente eficientes porque não reavaliam decisões tomadas. Contudo, só garantem a otimalidade em problemas que exibem a propriedade da escolha gulosa (uma escolha localmente ótima leva a uma solução globalmente ótima) e subestrutura ótima (a solução ótima para o problema contém as soluções ótimas para os subproblemas). A prova matemática clássica de corretude de um algoritmo guloso utiliza o Exchange Argument (Argumento de Troca), demonstrando que se existisse uma solução ótima alternativa que difere da nossa em um passo, poderíamos realizar uma troca para alinhar com a escolha gulosa sem degradar o valor global da solução.

🔧Exemplo

Seleção de Atividades (Algoritmo Guloso)

import java.util.*;

record Atividade(int inicio, int fim) {}

public class SelecaoAtividades {
    public static List<Atividade> selecionarMaximo(List<Atividade> atividades) {
        List<Atividade> selecionadas = new ArrayList<>();
        if (atividades.isEmpty()) return selecionadas;
        
        // Critério guloso provado ótimo: ordenar atividades pelo horário de término (fim)
        atividades.sort(Comparator.comparingInt(Atividade::fim));
        
        // Seleciona a primeira atividade (a que termina mais cedo)
        Atividade ultima = atividades.get(0);
        selecionadas.add(ultima);
        
        for (int i = 1; i < atividades.size(); i++) {
            Atividade atual = atividades.get(i);
            // Se a atividade atual começa após o término da última, é compatível
            if (atual.inicio() >= ultima.fim()) {
                selecionadas.add(atual);
                ultima = atual; // Escolha gulosa atualizada
            }
        }
        return selecionadas;
    }
}

📓Analogia

Programação Dinâmica — O Caderno de Rascunho

Se você perguntar a uma criança quanto é '1 + 1 + 1 + 1 + 1', ela contará nos dedos e responderá '5'. Se você imediatamente adicionar '+ 1' no final e perguntar 'e agora?', ela dirá instantaneamente '6'. Ela não contou tudo de novo do zero; ela simplesmente lembrou que a soma dos primeiros números era 5 e somou 1 a esse resultado. Isso é Programação Dinâmica. Em vez de recalcular subproblemas sobrepostos repetidamente e desperdiçar tempo de processamento, nós escrevemos as respostas intermediárias em um 'caderno de rascunho' (cache de memoização ou matriz de tabulação) para que possamos consultá-las instantaneamente quando necessário.

💡Conceito

DP: Memoization (Top-Down) vs Tabulation (Bottom-Up)

A Programação Dinâmica (DP) aplica-se a problemas que possuem subestrutura ótima e subproblemas sobrepostos. Existem duas formas principais de implementação: (1) Top-Down com Memoization: Mantém a estrutura recursiva natural do problema, mas intercepta cada retorno gravando o resultado em um cache (array ou hash map). É uma abordagem preguiçosa (lazy) porque calcula apenas os estados estritamente necessários. No entanto, sofre com a sobrecarga de stack frames na JVM. (2) Bottom-Up com Tabulation: Remove a recursão completamente. Resolve primeiro os casos base e preenche sistematicamente uma tabela física (array) de baixo para cima. É uma abordagem iterativa e mais performática na JVM. Adicionalmente, a tabulação ordenada permite técnicas de otimização de espaço, reduzindo a complexidade de memória (por exemplo, de O(N) para O(1) em Fibonacci, mantendo apenas as duas últimas posições).

🔧Exemplo

Coin Change (DP Bottom-Up com Otimização)

import java.util.Arrays;

public class CoinChange {
    public static int calcularMinimoMoedas(int[] moedas, int valorAlvo) {
        // dp[i] armazenará o menor número de moedas para alcançar o valor i
        int[] dp = new int[valorAlvo + 1];
        
        // Preenche o array com valor sentinela (simulando infinito)
        Arrays.fill(dp, valorAlvo + 1);
        dp[0] = 0; // Caso base: 0 moedas para valor 0
        
        // Tabulação Bottom-Up iterativa
        for (int i = 1; i <= valorAlvo; i++) {
            for (int moeda : moedas) {
                if (moeda <= i) {
                    // Transição: dp[i] é o menor entre o valor atual e usar a moeda
                    dp[i] = Math.min(dp[i], dp[i - moeda] + 1);
                }
            }
        }
        
        // Se o valor contido no alvo ainda for o sentinela, é impossível dar o troco
        return dp[valorAlvo] > valorAlvo ? -1 : dp[valorAlvo];
    }
}