Matemática Discretapara Engenheiros

7. Complexidade

Backtracking é poderoso, mas também é custoso.

Seu tempo de execução depende de quantos nós da árvore de busca são realmente explorados.

No pior caso, esse número cresce exponencialmente.

7.1 A Complexidade Vem da Árvore de Busca

A complexidade do backtracking é determinada pelo tamanho da árvore de busca.

Cada nó representa uma solução parcial, e o algoritmo pode precisar visitar muitos desses nós.

Complexidade de tempo ≈ número de nós explorados.

7.2 Fator de Ramificação

Seja b o fator de ramificação, ou seja, o número máximo de filhos que um nó pode ter.

Se cada decisão oferece muitas opções, a árvore cresce muito rapidamente.

Quanto maior o fator de ramificação, maior tende a ser o tempo de execução.

7.3 Profundidade da Árvore

Seja d a profundidade máxima da árvore de busca.

Em muitos problemas, a profundidade corresponde ao número de variáveis de decisão.

Quanto mais profunda a árvore, mais caminhos possíveis existem.

7.4 Complexidade no Pior Caso

Se cada nó tem até b filhos e a árvore tem profundidade d, o número de nós pode ser da ordem de:

Essa é a complexidade padrão no pior caso do backtracking.

7.5 Exemplos

Diferentes problemas levam a diferentes valores de b e d.

• Subconjuntos: b = 2, d = n → O(2ⁿ)
• Permutações: aproximadamente O(n!)
• N-Rainhas: exponencial no pior caso
• Caminho Hamiltoniano: exponencial no pior caso

Ou seja, o custo depende fortemente do problema específico.

7.6 Complexidade de Espaço

Backtracking geralmente usa menos memória que métodos em largura.

Como explora um caminho por vez, o custo principal vem da pilha de recursão.

7.7 O Efeito da Poda

Em teoria, a poda não muda a classe de complexidade: continua sendo exponencial.

Mas na prática, ela pode reduzir drasticamente o número de nós explorados.

7.8 Conclusão

Backtracking é caro porque explora um espaço combinatório.

Seu custo depende de:

• fator de ramificação
• profundidade
• qualidade da poda