Hva er tids Kompleksitet av et dybde-først søk?

En dybde-først-søk er en algoritme som prosedyre søker en graf eller trestruktur ved å reise så langt ned treet som det kan før sikkerhetskopiering. Tiden at algoritmen tar å fullføre avhenger av antallet av noder i grafen. I verste fall må algoritmen besøke hver node i grafen.

tre Grafer

I forbindelse med diagrammene, er et tre en graf hvor hver node, bortsett fra origo "root" node har en enkel foreldrenode hvis avstamning spor tilbake til rotnoden. Diagrammet danner en struktur lik den til et juletre, gradvis utvider seg og legge til nye noder og barn på hvert nivå. I et tre, er antall barn hver node har treets "forgrening faktor." Antall generasjoner i treet er treets "dybde".

Dybde-først søk

En dybde-først søk er en metode for å søke gjennom et tre, der algoritmen går ned treet til den finner målnoden. Starter fra rotnoden, går algoritmen ned til det neste barnet, og deretter at barns barnebarn, gjenta prosessen til den finner en barnløs "blad" node. Etter den finner at node, det går opp igjen til det finner en ikke-gransket node. Hvis det ikke er mer undersøkt noder, stopper den.

Algoritme Tid Kompleksitet

Tiden for å traversere et treet via dybde-først søk er avhengig av antall hjørner i diagrammet og kantene mellom dem. I verste tilfelle må algoritmen reise gjennom hvert topp-punkt og langs hver kant, slik at den tid det vil ta er det antall hjørner og antall kanter, eller "V + E". For tre, er antall kanter tilsvarer nodene minus en, slik at den totale tiden er "2V - 1." Hvis hver node i grafen har samme antall barn - en konstant forgrening faktor - så denne gangen er lik som faktor opphøyd av treet dybde.

andre hensyn

Ved implementering av noen algoritme, hastigheten av algoritmen avhenger av to faktorer: antall beregninger må gjøre og tiden det tar å få tilgang til de ressursene den trenger for å kjøre - vanligvis minne. Jo mer minne et program krever, jo lengre tid tar det å kjøre. En dybde-først søk må huske de foregående noder det besøkte, slik det verste tilfellet mengden minne det krever er lik antallet av noder i treet.