A complexidade do tempo dos algoritmos de retrocesso é geralmente exponencial , especificamente frequentemente expresso como o (b^d) , onde:

* b é o fator de ramificação (o número de opções possíveis em cada ponto de decisão).
* d é a profundidade da árvore de pesquisa (o número máximo de decisões que precisam ser tomadas para chegar a uma solução).

Explicação:

O backtracking explora todas as soluções possíveis, construindo sistematicamente uma solução candidata uma etapa de cada vez. A cada etapa, ele verifica se o candidato atual é promissor (ou seja, se poderia levar a uma solução válida). Se o candidato for promissor, o algoritmo explora recursivamente mais opções. Se o candidato não for promissor (um "beco sem saída"), o algoritmo * retorna * para a etapa anterior e tenta uma escolha diferente.

Como o algoritmo explora uma árvore de possibilidades, e o número de galhos pode crescer rapidamente, a complexidade do tempo pode se tornar muito grande, especialmente à medida que a profundidade `d 'aumenta.

Por que exponencial?

Pense nisso como uma pesquisa de árvore. Se cada nó na árvore tiver `B '(fator de ramificação` b`) e a profundidade máxima da árvore é `d`, então, na pior das hipóteses, você pode potencialmente explorar todos os nós` b^d`.

Considerações importantes:

* Cenário de pior caso: A complexidade do tempo o (b^d) é tipicamente um cenário * pior dos casos *. O tempo de execução real depende fortemente do problema e da eficácia da poda (com que eficácia o algoritmo pode identificar e evitar explorar ramificações pouco promissoras).
* poda: Bons algoritmos de retrocesso empregam várias técnicas de poda para reduzir significativamente o espaço de pesquisa. A poda pode melhorar drasticamente o tempo de execução, mas não altera a natureza exponencial inerente do algoritmo nos piores casos.
* Exemplo: Um exemplo clássico está resolvendo o problema da n-Queens. Para colocar o N Queens em um quadro de xadrez NXN, o fator de ramificação está relacionado ao número de colunas disponíveis em uma linha e a profundidade está relacionada ao número de linhas. A complexidade do pior caso de tempo é significativamente reduzida pela verificação de conflitos (atacando rainhas) em cada etapa, o que poda muitos dos ramos em potencial.
* Outros fatores: Além de `b` e` d`, outros fatores podem afetar o tempo de execução. Por exemplo, o tempo necessário para avaliar se uma solução candidata é promissora também pode ser um fator significativo.
* NP-Completude: Muitos problemas resolvidos usando o backtracking são NP-completos. Isso significa que acredita-se que não existe um algoritmo de tempo polinomial para resolvê-los em geral, e o retorno geralmente se torna uma abordagem necessária (embora às vezes ineficiente).

em resumo:

Embora o retrocesso possa ser uma poderosa técnica de solução de problemas, sua complexidade de tempo exponencial significa que é mais adequada para problemas onde:

* O tamanho do problema é relativamente pequeno.
* Estratégias de poda eficazes podem ser empregadas para reduzir significativamente o espaço de pesquisa.
* Uma solução aproximada é aceitável se a solução exata for muito demorada para encontrar.

Se o seu problema for grande e a poda for ineficaz, pode ser necessário considerar algoritmos alternativos ou técnicas de aproximação.