Defina o que “melhor” significa.
Antes de ordenar candidatos, declare objetivo, restrições e a chave local: menor término, maior ganho marginal, menor peso ou maior densidade. Prioridade sem contrato é apenas intuição.
strategy / local choice
próxima lente Greedy Algorithm.
Escolher bem agora — quando a estrutura do problema permite confiar no futuro.
visualização passo a passo
stage / GreedyQual atividade termina primeiro?
201
302
403
504
605
706
foco atual / ordenar pelo fima faixa mostra o estado, não uma medição de tempo real
ação / progresso comparação / estado conflito / limite
telemetria / estratégia
passo01ordenar pelo fim
ordemfim crescenteestado observado
códigolinha 1JavaScript
estadopausadocontrole manual
/ o que está acontecendoordenar pelo fim
ordenar pelo fim
proteja o horizonte.
Antes da primeira escolha, colocamos as atividades em uma ordem que preserva o maior espaço possível para o restante.
→
princípio /
A melhor escolha local pode levar a uma solução ótima quando existe a propriedade de escolha gulosa.
limite que não pode ser omitido
Uma estratégia gulosa não é sinônimo de “escolha o maior valor”. Sem uma prova ou propriedade adequada, a decisão local pode bloquear a melhor solução global.
complexidade / mapa rápido
melhorO(n)
médioO(n log n)
piorO(n log n)
A seleção custa O(n) quando as atividades já estão ordenadas; nesta implementação, ordenar a entrada com toSorted domina o custo e leva a O(n log n).
Como ler esta réguaEla não mede o tempo do seu aparelho: compara o crescimento quando aumentam os itens, os estados possíveis ou as decisões de uma estratégia.
operações
O(n log n) · Itens em níveis
Todos os itens são tratados, mas as decisões são organizadas em níveis. O log₂(n) indica quantas divisões pela metade cabem até chegar a casos pequenos.
Dobrar n adiciona um nível de decisão; por isso o crescimento é maior que O(n), mas bem menor que uma comparação entre todos os pares.comparação / duas técnicas
Compare o crescimento lado a lado
Escolha duas técnicas diferentes. As curvas usam a mesma escala visual para explicar como o custo tende a aumentar.
Comparações prontasaplique um par didático
Use este par para contrastar uma escolha local eficiente com o custo de preencher e reutilizar estados em problemas de capacidade. Greedy Algorithm e Dynamic Programming usam parâmetros diferentes: O(n·C) depende da capacidade C, e O(bᵈ) depende da ramificação b e da profundidade d. A régua contrasta modelos de crescimento; só compare a inclinação sob hipóteses explícitas sobre como esses parâmetros aumentam.
/ por baixo do palco
Uma escolha, um futuro.
O destaque acompanha a decisão atual. Leia o pseudocódigo antes de trocar de linguagem; a implementação é uma tradução, não um novo algoritmo.
01ordenar atividades pelo fim
02último_fim ← −∞
03para atividade em atividades:
04 se início ≥ último_fim:
05 aceitar atividade
06 último_fim ← fim
implementação / JavaScript
01const ordered = activities.toSorted((a, b) => a.end - b.end); // Sort activities by finishing time02let lastEnd = -Infinity;03const selected = [];04for (const activity of ordered) {05 if (activity.start >= lastEnd) {06 selected.push(activity);07 lastEnd = activity.end;08 }09}10return selected;/ leitura técnica · escolhas locaisUma decisão local
Uma decisão local
não é uma prova.
Greedy constrói uma solução ao escolher, em cada etapa, o candidato de melhor prioridade local que ainda preserva a viabilidade. A regra pode ser excelente, mas só é correta quando a estrutura do problema permite justificar que aquela escolha cabe em alguma solução ótima.
Mostre que a escolha é segura.
Parta de uma solução ótima e prove que ela pode ser transformada em outra que contenha a escolha atual, sem perder viabilidade nem piorar o resultado. Este é o argumento de troca.
Resolva o que ainda resta.
Depois de fixar uma escolha segura, a continuação precisa ser ótima para o subproblema residual. Com isso, a corretude avança por indução até a condição de parada.
invariante / leitura da bancada
O destaque verde mostra uma escolha que parece melhor no estado atual. A animação explica a regra local; ela não demonstra, sozinha, que o resultado é ótimo. Para isso, a classe de entradas precisa satisfazer uma prova de escolha segura ou uma garantia explícita de aproximação.
/ três garantias possíveisExato, aproximativo
Exato, aproximativo
ou heurístico.
Um mesmo estilo de decisão pode ter compromissos completamente diferentes. Documentar a garantia evita afirmar optimalidade onde existe apenas bom desempenho observado.
EXATOÓtimo em toda instância do contratoExemplo: seleção de atividades com menor término primeiro.
APROXIMATIVOQualidade limitada por uma razão formalExemplo: Set Cover guloso possui garantia, mas pode não ser ótimo.
HEURÍSTICOÚtil, porém sem garantia universal provadaExige avaliação empírica e limites bem documentados.
NÃO BASTASubestrutura ótima isoladaEla não implica, por si só, que uma regra local seja segura.
/ contraste que evita erros
Quando a escolha local abre — ou fecha — o futuro.
Na seleção de atividades, terminar cedo preserva espaço para intervalos seguintes; a troca sustenta a regra. Já em Knapsack 0/1, escolher a maior densidade pode bloquear uma combinação indivisível de maior valor. O caso fracionário é diferente: nele a densidade é uma escolha válida.
PROBLEMAREGRA LOCALGARANTIA
Atividadesterminar primeiroótimo, com argumento de troca
Knapsack fracionáriomaior valor/pesoótimo, pois itens podem ser divididos
Knapsack 0/1maior valor/pesopode falhar; use programação dinâmica ou outra prova
Moedasmaior moeda possíveldepende do sistema de denominações
decisão de uso
Prove antes de comprometer.
Use Greedy quando houver uma escolha local claramente formulada, uma prova de segurança e uma continuação ótima para o residual. Se encontrar um contraexemplo pequeno, a regra não serve para aquela classe de entradas. Quando a solução pode ser apenas aproximada, declare a razão de qualidade; quando não houver garantia, trate-a como heurística, não como algoritmo ótimo.
fontes / para continuar