Técnicas Avançadas de Projeto e Análise

Uma técnica de projeto e análise é uma regra que constrói a solução por decisões sucessivas sobre um espaço de candidatos. A análise correspondente prova que a construção é ótima, ou atribui o custo T(n)/n a uma sequência de operações.

Enumeração com poda, escolha local e tabela de subproblemas deste tópico — e árvores geradoras, Floyd–Warshall e conjuntos disjuntos nos tópicos seguintes — partem dessa regra de decisão e dessa conta de custo.

As páginas se agrupam em quatro blocos. O primeiro monta uma configuração válida gerando candidatas e corta o prefixo que já violou a restrição.

O segundo fixa, em cada etapa, uma escolha local irreversível e justifica essa escolha por uma prova de troca.

O terceiro preenche uma tabela de subproblemas que se repetem: cada estado combina respostas ótimas já calculadas.

O quarto estima o custo de n operações pelo total T(n) da sequência, no pior caso dessa sequência.

Gerar as 2ⁿ ou n! candidatas, ou desfazer a última escolha num prefixo inviável, está em Backtracking e Força Bruta. Guardar o estado que reaparece e ler a célula está em Programação Dinâmica.

Ordenar atividades pelo término, fundir os dois menores pesos em Huffman e encher a mochila fracionária por densidade Pᵢ/Wᵢ estão em Algoritmos Gulosos. O mínimo de parentização da cadeia de matrizes está em Programação Dinâmica.

A escolha local que não se desfaz está em Algoritmos Gulosos. Construir um prefixo de decisões e desfazer a última está em Backtracking e Força Bruta.

Uma inserção que copia m elementos custa Θ(m). Análise Amortizada soma as cópias 1+2+4+⋯ < 2n com as n escritas e divide T(n) por n: O(1) por inserção.