Tidskompleksiteten af ​​backtracking -algoritmer er generelt eksponentiel , specifikt ofte udtrykt som o (b^d) , hvor:

* b er forgreningsfaktoren (antallet af mulige valg på hvert beslutningspunkt).

* d er dybden af ​​søgningstræet (det maksimale antal beslutninger, der skal træffes for at nå en løsning).

Forklaring:

Backtracking udforsker alle mulige løsninger ved systematisk at opbygge en kandidatløsning et trin ad gangen. På hvert trin kontrollerer det, om den nuværende kandidat er lovende (dvs. hvis det potentielt kan føre til en gyldig løsning). Hvis kandidaten er lovende, udforsker algoritmen rekursivt yderligere valg. Hvis kandidaten ikke er lovende (en "blindgyde"), er algoritmen * backtracks * til det forrige trin og prøver et andet valg.

Fordi algoritmen udforsker et træ af muligheder, og antallet af grene kan vokse hurtigt, kan tidskompleksiteten blive meget stor, især når dybden `D` øges.

Hvorfor eksponentiel?

Tænk på det som en træsøgning. Hvis hver knude i træet har `b` børn (forgreningsfaktor` b`), og den maksimale dybde af træet er 'd', så i værste tilfælde kan du potentielt udforske alle 'b^d` knudepunkter.

Vigtige overvejelser:

* Worst-Case Scenario: O (B^D) tidskompleksitet er typisk et * værste tilfælde * -scenarie. Den faktiske runtime afhænger stærkt af problemet og effektiviteten af ​​beskæringen (hvor effektivt algoritmen kan identificere og undgå at udforske kompromisløse grene).

* Beskæring: Gode ​​backtracking -algoritmer anvender forskellige beskæringsteknikker for at reducere søgerummet betydeligt. Beskæring kan dramatisk forbedre runtime, men det ændrer ikke den iboende eksponentielle karakter af algoritmen i værste tilfælde.

* Eksempel: Et klassisk eksempel er at løse N-Queens-problemet. For at placere N -dronninger på et NXN -skakbræt er forgreningsfaktoren relateret til antallet af tilgængelige kolonner i træk, og dybden er relateret til antallet af rækker. Den værste case-tidskompleksitet reduceres markant ved at kontrollere for konflikter (angribende dronninger) på hvert trin, der beskærer mange af de potentielle grene.

* Andre faktorer: Udover `b` og` d` kan andre faktorer påvirke runtime. For eksempel kan den tid det tager at evaluere, om en kandidatløsning er lovende, også en betydelig faktor.

* np-komplethed: Mange problemer, der er løst ved hjælp af backtracking, er NP-komplet. Dette betyder, at det antages, at der ikke er nogen polynomisk-tidsalgoritme til at løse dem generelt, og backtracking bliver ofte en nødvendig (dog undertiden ineffektiv) tilgang.

Kortfattet:

Mens backtracking kan være en stærk problemløsningsteknik, betyder dens eksponentielle tidskompleksitet, at den er bedst egnet til problemer, hvor:

* Problemstørrelsen er relativt lille.

* Effektive beskæringsstrategier kan anvendes til markant at reducere søgerummet betydeligt.

* En omtrentlig løsning er acceptabel, hvis den nøjagtige løsning er for tidskrævende til at finde.

Hvis dit problem er stort, og beskæring er ineffektivt, skal du muligvis overveje alternative algoritmer eller tilnærmelsesteknikker.