A complexidade do tempo de um algoritmo de retrocesso é geralmente exponencial , embora possa variar dependendo do problema e de suas restrições. Não existe uma complexidade "the" "the" para voltar atrás, porque depende muito de:

* O número de opções em cada etapa: Se você tiver *b *opções em cada etapa, e a profundidade da árvore de pesquisa é *d *, então a complexidade pode ser O (b d ).

* As restrições e técnicas de poda específicas do problema: A troca de retorno geralmente envolve poda o espaço de pesquisa. Se você puder podar efetivamente as filiais que não levarão a uma solução, poderá reduzir significativamente o espaço de pesquisa e melhorar o desempenho. A eficiência da estratégia de poda afeta fortemente a complexidade do tempo final.

* A natureza do problema: Alguns problemas são inerentemente mais passíveis de voltar atrás do que outros.

Aqui está um colapso de por que geralmente é exponencial e alguns exemplos:

* Natureza exponencial: O backtracking explora todas as combinações ou permutações possíveis até que uma solução seja encontrada. No pior cenário, pode ter que explorar uma grande parte do espaço de pesquisa, levando a um crescimento exponencial no número de nós visitados.

* Exemplos e suas complexidades:

* N-Queens Problema: Encontrar todos os canais possíveis de N Queens em um tabuleiro de xadrez NXN, de modo que não há duas rainhas se ameaçam. A complexidade do tempo é de aproximadamente O (n!), No pior cenário. As técnicas de poda podem melhorar significativamente o desempenho.

* Problema de vendedor viajante (TSP): Encontrar a rota mais curta possível que visita cada cidade exatamente uma vez e retorna à cidade inicial. Uma abordagem ingênua de retrocesso teria uma complexidade de tempo de O (n!), Onde 'n' é o número de cidades. A ramificação e o limite são usados ​​como poda para uma execução mais rápida.

* Soma do subconjunto Problema: Determinando se existe um subconjunto de um determinado conjunto de números cuja soma é igual a um valor alvo. A complexidade do tempo pode ser O (2 n ), onde 'n' é o número de elementos no conjunto, pois você pode precisar considerar todos os subconjuntos possíveis.

* SUDOKU SOLVER: Na pior das hipóteses, um solucionador sudoku de retrocesso pode tentar um grande número de possibilidades para cada célula vazia. Embora teoricamente exponenciais, boas heurísticas e restrições tornam muito rápido o sudoku do mundo real.

* Coloração de gráfico: Atribuindo cores aos vértices de um gráfico de modo que dois vértices adjacentes tenham a mesma cor. O pior caso é exponencial, mas a eficiência depende de como você solicita os nós.

* fatores que afetam a complexidade do tempo:

* profundidade da recursão: Quanto mais profunda a árvore de pesquisa, mais cálculos são necessários.
* Fator de ramificação: O número de opções em cada nó da árvore de pesquisa. Um fator de ramificação maior leva a um crescimento exponencial mais rápido.
* poda: A poda eficaz reduz o espaço de pesquisa, melhorando o desempenho. A poda é o fator mais importante a considerar.

em resumo:

Embora seja difícil dar uma complexidade precisa de tempo para voltar em geral, é seguro dizer que geralmente é exponencial (o (b d ) ou O (2 n ) ou O (n!)) No pior caso. A complexidade do tempo real é fortemente influenciada pela estrutura do problema, pela eficiência de quaisquer estratégias de poda utilizadas e o tamanho da entrada. É importante projetar algoritmos de retrocesso com poda eficaz para evitar explorar caminhos desnecessários. Em alguns casos, a poda pode ser tão eficaz que torna o algoritmo muito mais rápido na prática do que a sua pior complexidade exponencial sugeriria. No entanto, para muitos problemas, mesmo com a poda, o retorno permanece inerentemente ineficiente para grandes tamanhos de entrada.