Computer Science › Algoritmos e Software
Um problema se qualifica para programação dinâmica exatamente quando tem subproblemas sobrepostos (a mesma chamada recursiva se repete) E subestrutura ótima (a resposta ótima ao todo se constrói das respostas ótimas às partes); nenhuma das duas sozinha basta.
Memoização pega uma função recursiva já correta e adiciona apenas um cache, verificado no início e preenchido no fim, colapsando o número de chamadas exponencial de Fibonacci ingênuo para O(n) subproblemas distintos calculados, sem eliminar o custo de pilha de chamada.
Tabulação resolve os mesmos subproblemas que memoização, no mesmo tempo assintótico, preenchendo uma tabela iterativamente do menor caso base para cima em vez de recursar para baixo com um cache, eliminando o custo de pilha de chamada por completo.
LCS é o primeiro exemplo de DP com subproblemas indexados por dois parâmetros independentes; sua recorrência ramifica em se os últimos caracteres de dois prefixos combinam, e uma tabela 2D preenchida por essa regra também permite recuperar a subsequência real por rastreamento reverso.
Mochila 0/1 é o contraponto honesto ao sucesso de guloso em seleção de atividades, um contraexemplo concreto mostra a estratégia de melhor razão valor/peso travando na escolha errada, enquanto a recorrência de DP K(i,c) = max(pular, pegar) encontra o ótimo verdadeiro.
LIS admite tanto uma DP direta O(n²) (L(i) = 1 + max sobre L(j) anteriores de valor menor) quanto uma abordagem O(n log n) mantendo o menor final possível por comprimento, atualizado por busca binária, uma aplicação direta da busca binária generalizada.
Uma rede de fluxo é um grafo direcionado com capacidade em toda aresta, uma fonte e um sumidouro; um fluxo válido respeita capacidade e conservação em todo vértice intermediário, e o fluxo máximo pergunta qual atribuição válida maximiza o valor total.
O grafo residual guarda, para toda aresta, a capacidade direta não usada mais uma aresta reversa de "desfazer"; o método repete encontrar um caminho de aumento e empurrar fluxo pelo gargalo até que nenhum caminho reste.
O valor de qualquer fluxo válido nunca excede a capacidade de nenhum corte s-t (dualidade fraca), e o valor do fluxo máximo é sempre exatamente igual à capacidade do corte mínimo, provado construtivamente a partir do ponto de término de Ford-Fulkerson.
Escolher sempre o caminho de aumento com menos arestas, via BFS no grafo residual, limita o número de iterações a O(V·E) independente das capacidades, contra uma escolha arbitrária de caminho cujo número de iterações pode depender diretamente do valor numérico das capacidades.
BFS explora um grafo nível por nível usando uma fila, e a disciplina FIFO da fila é exatamente o que garante que a primeira descoberta de todo vértice aconteça via um caminho mais curto em número de arestas, tudo em tempo O(V + E).
DFS mergulha completamente na subárvore alcançável de um vizinho antes de tentar o próximo, uma disciplina LIFO natural via pilha ou recursão; produz uma árvore comprida e sinuosa, com timestamps de descoberta e término aninhados que o próximo tópico usa diretamente.
Uma aresta de retorno em DFS direcionado (para um ancestral ainda na pilha) existe se e somente se o grafo tem um ciclo; quando não há ciclo, os mesmos tempos de término de DFS, lidos em ordem decrescente, produzem uma ordenação topológica válida.
Uma vez que arestas carregam pesos, "caminho mais curto" significa peso total mínimo, não menos arestas; toda solução se constrói sobre relaxamento, mantendo uma distância tentativa que nunca subestima a verdade, com a escolha de quais arestas relaxar e em que ordem distinguindo os algoritmos seguintes.
Dijkstra finaliza repetidamente o vértice não finalizado de menor distância tentativa usando um heap binário para extract-min O(log V), dando O((V+E) log V) no total; a prova de correção depende inteiramente de pesos de aresta não negativos.
Bellman-Ford abandona a estratégia gulosa e relaxa toda aresta V−1 vezes, garantindo distâncias corretas mesmo com pesos negativos; uma rodada V extra, ainda encontrando melhoria, prova um ciclo de peso negativo alcançável a partir da fonte.
Saber de antemão que um grafo é um DAG permite processar vértices em ordem topológica e relaxar cada aresta de saída exatamente uma vez, dando O(V + E), mais rápido que Dijkstra e Bellman-Ford, e tolerando arestas negativas já que não há ciclo negativo possível.
\"Existe caminho entre eles\" é uma relação de equivalência que particiona os vértices de um grafo em componentes conexos; rodar BFS de todo vértice ainda não visitado descobre cada componente exatamente uma vez, tudo ainda em O(V + E).
Um algoritmo guloso sempre toma a escolha localmente melhor e nunca reconsidera; o contraexemplo de troco de moedas com {1, 3, 4} mostra que isso pode produzir uma resposta válida mas comprovadamente não ótima, então correção de um algoritmo guloso é uma propriedade do problema específico, não uma garantia universal.
A propriedade de corte garante que, entre as arestas cruzando qualquer partição de vértices, a mais barata pertence a alguma MST; isso licencia uma estratégia gulosa com garantia de correção real, o modelo que tanto Kruskal quanto Prim instanciam.
Kruskal ordena todas as arestas por peso e as processa em sequência, aceitando cada uma a menos que union-find diga que seus extremos já estão conectados; a correção vem da propriedade de corte, e o tempo de execução O(E log E) é dominado pela ordenação, não pelas operações de union-find.
Prim cresce uma única árvore a partir de um vértice, extraindo repetidamente a aresta mais barata cruzando o corte árvore-versus-resto via um heap binário; compartilha o esqueleto de Dijkstra mas compara pesos de aresta crus, não distâncias de caminho acumuladas.
A regra gulosa de sempre selecionar a atividade compatível que termina mais cedo é comprovadamente ótima para seleção de atividades; o argumento de troca mostra que qualquer solução ótima pode ser transformada para concordar com a escolha gulosa sem perder tamanho, e a indução estende isso a toda a sequência.
Dividir para conquistar é recursão disciplinada de uma forma específica, divida o problema em instâncias fracionalmente menores, conquiste cada uma recursivamente, combine as respostas; a fração de redução, não o simples fato de encolher, é o que produz níveis logarítmicos.
A garantia real por trás de busca binária não é "o array está ordenado" mas que uma comparação basta para descartar metade dos candidatos; um array ordenado rotacionado preserva exatamente essa propriedade e ainda pode ser buscado em O(log n).
A árvore de recursão transforma uma recorrência auto-referente em uma figura, contando níveis e o trabalho por nível para chegar a T(n) = Θ(n log n) para merge sort e Θ(log n) para busca binária, sem precisar do Teorema Mestre completo.
Merge sort como a ilustração completa canônica de dividir para conquistar, com sua recorrência T(n) = 2T(n/2) + O(n) resolvida por completo, sua estabilidade provada a partir da comparação <=, e seu custo de espaço Θ(n) derivado da mecânica do próprio merge.
Quicksort faz o trabalho pesado durante dividir, não combinar, particionando o array em torno de um pivô escolhido usando apenas trocas in-place; os esquemas de Lomuto e Hoare fazem isso de formas diferentes, com garantias de retorno diferentes.
Um pivô fixo (primeiro ou último elemento) degrada quicksort para O(n²) em entradas comuns como arrays já ordenados; escolher o pivô uniformemente ao acaso quebra o vínculo entre entrada e sequência de escolhas ruins, tornando O(n log n) o esperado em qualquer entrada.
Modelar qualquer ordenação por comparação como uma árvore de decisão binária mostra que ela precisa de pelo menos n! folhas, forçando altura Ω(n log n); combinado com o limite superior O(n log n) do merge sort, isso prova que merge sort é assintoticamente ótimo entre ordenações por comparação.
As duas ordenações O(n log n) fazem trocas opostas, quicksort troca uma garantia de pior caso por particionamento in-place e melhor localidade de cache; merge sort troca espaço O(n) e sobrecarga de merge por O(n log n) incondicional e estabilidade.
Dividir para conquistar, guloso, e programação dinâmica se distinguem por uma pergunta estrutural, subproblemas independentes, uma escolha localmente melhor irrevogável e comprovadamente segura, ou subproblemas sobrepostos, reconhecer qual sinal um novo problema exibe é a habilidade transferível que esta disciplina construiu.
Part of the Computer Science curriculum.
Um problema se qualifica para programação dinâmica exatamente quando tem subproblemas sobrepostos (a mesma chamada recursiva se repete) E subestrutura ótima (a resposta ótima ao todo se constrói das respostas ótimas às partes); nenhuma das duas sozinha basta.
Memoização pega uma função recursiva já correta e adiciona apenas um cache, verificado no início e preenchido no fim, colapsando o número de chamadas exponencial de Fibonacci ingênuo para O(n) subproblemas distintos calculados, sem eliminar o custo de pilha de chamada.
Tabulação resolve os mesmos subproblemas que memoização, no mesmo tempo assintótico, preenchendo uma tabela iterativamente do menor caso base para cima em vez de recursar para baixo com um cache, eliminando o custo de pilha de chamada por completo.
LCS é o primeiro exemplo de DP com subproblemas indexados por dois parâmetros independentes; sua recorrência ramifica em se os últimos caracteres de dois prefixos combinam, e uma tabela 2D preenchida por essa regra também permite recuperar a subsequência real por rastreamento reverso.
Mochila 0/1 é o contraponto honesto ao sucesso de guloso em seleção de atividades, um contraexemplo concreto mostra a estratégia de melhor razão valor/peso travando na escolha errada, enquanto a recorrência de DP K(i,c) = max(pular, pegar) encontra o ótimo verdadeiro.
LIS admite tanto uma DP direta O(n²) (L(i) = 1 + max sobre L(j) anteriores de valor menor) quanto uma abordagem O(n log n) mantendo o menor final possível por comprimento, atualizado por busca binária, uma aplicação direta da busca binária generalizada.
Uma rede de fluxo é um grafo direcionado com capacidade em toda aresta, uma fonte e um sumidouro; um fluxo válido respeita capacidade e conservação em todo vértice intermediário, e o fluxo máximo pergunta qual atribuição válida maximiza o valor total.
O grafo residual guarda, para toda aresta, a capacidade direta não usada mais uma aresta reversa de "desfazer"; o método repete encontrar um caminho de aumento e empurrar fluxo pelo gargalo até que nenhum caminho reste.
O valor de qualquer fluxo válido nunca excede a capacidade de nenhum corte s-t (dualidade fraca), e o valor do fluxo máximo é sempre exatamente igual à capacidade do corte mínimo, provado construtivamente a partir do ponto de término de Ford-Fulkerson.
Escolher sempre o caminho de aumento com menos arestas, via BFS no grafo residual, limita o número de iterações a O(V·E) independente das capacidades, contra uma escolha arbitrária de caminho cujo número de iterações pode depender diretamente do valor numérico das capacidades.
BFS explora um grafo nível por nível usando uma fila, e a disciplina FIFO da fila é exatamente o que garante que a primeira descoberta de todo vértice aconteça via um caminho mais curto em número de arestas, tudo em tempo O(V + E).
DFS mergulha completamente na subárvore alcançável de um vizinho antes de tentar o próximo, uma disciplina LIFO natural via pilha ou recursão; produz uma árvore comprida e sinuosa, com timestamps de descoberta e término aninhados que o próximo tópico usa diretamente.
Uma aresta de retorno em DFS direcionado (para um ancestral ainda na pilha) existe se e somente se o grafo tem um ciclo; quando não há ciclo, os mesmos tempos de término de DFS, lidos em ordem decrescente, produzem uma ordenação topológica válida.
Uma vez que arestas carregam pesos, "caminho mais curto" significa peso total mínimo, não menos arestas; toda solução se constrói sobre relaxamento, mantendo uma distância tentativa que nunca subestima a verdade, com a escolha de quais arestas relaxar e em que ordem distinguindo os algoritmos seguintes.
Dijkstra finaliza repetidamente o vértice não finalizado de menor distância tentativa usando um heap binário para extract-min O(log V), dando O((V+E) log V) no total; a prova de correção depende inteiramente de pesos de aresta não negativos.
Bellman-Ford abandona a estratégia gulosa e relaxa toda aresta V−1 vezes, garantindo distâncias corretas mesmo com pesos negativos; uma rodada V extra, ainda encontrando melhoria, prova um ciclo de peso negativo alcançável a partir da fonte.
Saber de antemão que um grafo é um DAG permite processar vértices em ordem topológica e relaxar cada aresta de saída exatamente uma vez, dando O(V + E), mais rápido que Dijkstra e Bellman-Ford, e tolerando arestas negativas já que não há ciclo negativo possível.
\"Existe caminho entre eles\" é uma relação de equivalência que particiona os vértices de um grafo em componentes conexos; rodar BFS de todo vértice ainda não visitado descobre cada componente exatamente uma vez, tudo ainda em O(V + E).
Um algoritmo guloso sempre toma a escolha localmente melhor e nunca reconsidera; o contraexemplo de troco de moedas com {1, 3, 4} mostra que isso pode produzir uma resposta válida mas comprovadamente não ótima, então correção de um algoritmo guloso é uma propriedade do problema específico, não uma garantia universal.
A propriedade de corte garante que, entre as arestas cruzando qualquer partição de vértices, a mais barata pertence a alguma MST; isso licencia uma estratégia gulosa com garantia de correção real, o modelo que tanto Kruskal quanto Prim instanciam.
Kruskal ordena todas as arestas por peso e as processa em sequência, aceitando cada uma a menos que union-find diga que seus extremos já estão conectados; a correção vem da propriedade de corte, e o tempo de execução O(E log E) é dominado pela ordenação, não pelas operações de union-find.
Prim cresce uma única árvore a partir de um vértice, extraindo repetidamente a aresta mais barata cruzando o corte árvore-versus-resto via um heap binário; compartilha o esqueleto de Dijkstra mas compara pesos de aresta crus, não distâncias de caminho acumuladas.
A regra gulosa de sempre selecionar a atividade compatível que termina mais cedo é comprovadamente ótima para seleção de atividades; o argumento de troca mostra que qualquer solução ótima pode ser transformada para concordar com a escolha gulosa sem perder tamanho, e a indução estende isso a toda a sequência.
Dividir para conquistar é recursão disciplinada de uma forma específica, divida o problema em instâncias fracionalmente menores, conquiste cada uma recursivamente, combine as respostas; a fração de redução, não o simples fato de encolher, é o que produz níveis logarítmicos.
A garantia real por trás de busca binária não é "o array está ordenado" mas que uma comparação basta para descartar metade dos candidatos; um array ordenado rotacionado preserva exatamente essa propriedade e ainda pode ser buscado em O(log n).
A árvore de recursão transforma uma recorrência auto-referente em uma figura, contando níveis e o trabalho por nível para chegar a T(n) = Θ(n log n) para merge sort e Θ(log n) para busca binária, sem precisar do Teorema Mestre completo.
Merge sort como a ilustração completa canônica de dividir para conquistar, com sua recorrência T(n) = 2T(n/2) + O(n) resolvida por completo, sua estabilidade provada a partir da comparação <=, e seu custo de espaço Θ(n) derivado da mecânica do próprio merge.
Quicksort faz o trabalho pesado durante dividir, não combinar, particionando o array em torno de um pivô escolhido usando apenas trocas in-place; os esquemas de Lomuto e Hoare fazem isso de formas diferentes, com garantias de retorno diferentes.
Um pivô fixo (primeiro ou último elemento) degrada quicksort para O(n²) em entradas comuns como arrays já ordenados; escolher o pivô uniformemente ao acaso quebra o vínculo entre entrada e sequência de escolhas ruins, tornando O(n log n) o esperado em qualquer entrada.
Modelar qualquer ordenação por comparação como uma árvore de decisão binária mostra que ela precisa de pelo menos n! folhas, forçando altura Ω(n log n); combinado com o limite superior O(n log n) do merge sort, isso prova que merge sort é assintoticamente ótimo entre ordenações por comparação.
As duas ordenações O(n log n) fazem trocas opostas, quicksort troca uma garantia de pior caso por particionamento in-place e melhor localidade de cache; merge sort troca espaço O(n) e sobrecarga de merge por O(n log n) incondicional e estabilidade.
Dividir para conquistar, guloso, e programação dinâmica se distinguem por uma pergunta estrutural, subproblemas independentes, uma escolha localmente melhor irrevogável e comprovadamente segura, ou subproblemas sobrepostos, reconhecer qual sinal um novo problema exibe é a habilidade transferível que esta disciplina construiu.