Tidskompleksiteten af en backtracking -algoritme er generelt
eksponentiel , selvom det kan variere afhængigt af problemet og dets begrænsninger. Der er ingen enkelt "tidskompleksiteten til backtracking, fordi det meget afhænger af:
* Antallet af valg på hvert trin: Hvis du har *B *valg på hvert trin, og dybden af søgningstræet er *D *, kan kompleksiteten være O (B
d
).
* Problemets specifikke begrænsninger og beskæringsteknikker: Backtracking involverer ofte beskæring af søgerummet. Hvis du effektivt kan beskære grene, der ikke vil føre til en løsning, kan du reducere søgerummet og forbedre ydelsen markant og forbedre ydelsen. Effektiviteten af beskæringsstrategien påvirker stærkt den sidste tidskompleksitet.
* Problemets art: Nogle problemer er i sagens natur mere tilgængelige for backtracking end andre.
Her er en sammenbrud af, hvorfor det generelt er eksponentielt og nogle eksempler:
* Eksponentiel karakter: Backtracking udforsker alle mulige kombinationer eller permutationer, indtil der findes en løsning. I det værste tilfælde kan det muligvis udforske en stor del af søgerummet, hvilket fører til eksponentiel vækst i antallet af besøgte noder.
* eksempler og deres kompleksiteter:
* n-queens Problem: At finde alle mulige placeringer af N -dronninger på et NXN -skakbræt, således at ingen to dronninger truer hinanden. Tidskompleksiteten er omtrent O (n!), I værste tilfælde. Beskæringsteknikker kan forbedre ydeevnen markant.
* Rejsende sælgerproblem (TSP): At finde den kortest mulige rute, der besøger hver by nøjagtigt en gang, og vender tilbage til startbyen. En naiv backtracking -tilgang ville have en tidskompleksitet af O (n!), Hvor 'n' er antallet af byer. Branch og bundet bruges som beskæring til hurtigere udførelse.
* Problem med undergrupper: Bestemmelse af, om der findes en undergruppe af et givet sæt numre, hvis sum er lig med en målværdi. Tidskompleksiteten kan være O (2
n
), hvor 'n' er antallet af elementer i sættet, da du muligvis skal overveje alle mulige undergrupper.
* Sudoku Solver: I værste tilfælde kan en backtracking Sudoku -solver muligvis prøve et stort antal muligheder for hver tom celle. Selvom teoretisk eksponentiel, gør god heuristik og begrænsninger sudoku i den virkelige verden til at løse meget hurtigt.
* Graffarve: Tildeling af farver til vertices af en graf, således at ingen to tilstødende vertices har samme farve. Værste tilfælde er eksponentiel, men effektiviteten afhænger af, hvordan du bestiller knudepunkterne.
* Faktorer, der påvirker tidskompleksiteten:
* Dybde af rekursionen: Jo dybere søgningstræet, jo flere beregninger kræves.
* Filmfaktor: Antallet af valg på hver knudepunkt på søgningstræet. En større forgreningsfaktor fører til hurtigere eksponentiel vækst.
* Beskæring: Effektiv beskæring reducerer søgerummet, hvilket forbedrer ydeevnen. Beskæring er den eneste vigtigste faktor at overveje.
Kortfattet:
Selvom det er vanskeligt at give en præcis tidskompleksitet for backtracking generelt, er det sikkert at sige, at det normalt er eksponentielt (O (B
d
) eller O (2
n
) eller o (n!)) I værste tilfælde. Den faktiske tidskompleksitet er stærkt påvirket af problemets struktur, effektiviteten af alle anvendte beskærende strategier og størrelsen på input. Det er vigtigt at designe backtracking -algoritmer med effektiv beskæring for at undgå at udforske unødvendige stier. I nogle tilfælde kan beskæring være så effektiv, at det gør algoritmen meget hurtigere i praksis, end dens værste tilfælde eksponentielle kompleksitet antyder. For mange problemer, selv med beskæring, forbliver backtracking imidlertid iboende ineffektiv til store inputstørrelser.
