Ποια είναι η ώρα Πολυπλοκότητα του βάθους - First Search

; Μια αναζήτηση πρώτα κατά βάθος είναι ένας αλγόριθμος που αναζητά διαδικαστικά μια δομή γράφημα ή ένα δέντρο με το ταξίδι στο μέτρο κάτω από το δέντρο , όπως μπορείτε πριν από τη δημιουργία αντιγράφων ασφαλείας . Ο χρόνος που ο αλγόριθμος χρειάζεται για να τελειώσει εξαρτάται από τον αριθμό των κόμβων στο γράφημα . Στη χειρότερη περίπτωση , ο αλγόριθμος πρέπει να επισκεφθεί κάθε κόμβο του γραφήματος . Δέντρο Γραφήματα
Η

Στο πλαίσιο των γραφημάτων , ένα δέντρο είναι ένα γράφημα στο οποίο κάθε κόμβος εκτός από την καταγωγή "root" κόμβος έχει ένα μοναδικό κόμβο γονέα του οποίου καταγωγή ίχνη πίσω στον κόμβο ρίζα . Το γράφημα σχηματίζει μια δομή παρόμοια με εκείνη του ένα χριστουγεννιάτικο δέντρο , επεκτείνεται σταδιακά και με την προσθήκη νέων κόμβων και τα παιδιά σε κάθε επίπεδο . Σε ένα δέντρο , ο αριθμός των παιδιών κάθε κόμβος έχει είναι του δέντρου " παράγοντας διακλάδωσης . " Ο αριθμός των γενεών στο δέντρο είναι το «βάθος ». Του δέντρου εικόνων
Βάθος - First Search
Η

μια αναζήτηση πρώτα κατά βάθος είναι μια μέθοδος που ψάχνουν μέσα από ένα δέντρο , στο οποίο ο αλγόριθμος περπατά κάτω από το δέντρο μέχρι να βρει τον κόμβο στόχου . Ξεκινώντας από τον κόμβο ρίζας , ο αλγόριθμος βόλτες κάτω στο επόμενο παιδί και στη συνέχεια το εγγόνι του συγκεκριμένου παιδιού , επαναλαμβάνοντας τη διαδικασία μέχρι να βρει ένα άτεκνο " φύλλο " του κόμβου . Αφού διαπιστώνει ότι κόμβο , περπατά ξανά μέχρι να βρει ένα unexamined κόμβο . Αν δεν υπάρχουν πλέον εξετάζονται κόμβους , να σταματήσει.

Η Αλγόριθμος Χρονική Πολυπλοκότητα
Η

Ο χρόνος για να διασχίσει ένα δέντρο με αναζήτηση πρώτα κατά βάθος εξαρτάται από τον αριθμό των κορυφών στο γράφημα και τις άκρες μεταξύ τους. Στη χειρότερη περίπτωση , ο αλγόριθμος πρέπει να ταξιδέψει μέσα από κάθε κορυφή και κατά μήκος κάθε ακμής , έτσι ώστε ο χρόνος θα χρειαστεί είναι ο αριθμός των κορυφών και ο αριθμός των ακμών , ή " V + E." Για ένα δέντρο, ο αριθμός των ακμές είναι ίσες με τους κόμβους μείον ένα , έτσι ώστε ο συνολικός χρόνος είναι " 2V - . 1 " Εάν κάθε κόμβο του γραφήματος έχει τον ίδιο αριθμό παιδιών - ένα σταθερό παράγοντα διακλάδωσης - τότε αυτή τη φορά ισούται με το συντελεστή υψωμένο στη δύναμη του βάθους του δέντρου
εικόνων Άλλα θέματα
Η

Κατά την εφαρμογή οποιουδήποτε αλγορίθμου , η ταχύτητα του αλγορίθμου εξαρτάται από δύο παράγοντες : . ο αριθμός των υπολογισμών που πρέπει να κάνει και ο χρόνος που απαιτείται για να έχουν πρόσβαση στους πόρους που χρειάζεται για να τρέξει - συνήθως τη μνήμη . Η περισσότερη μνήμη ένα πρόγραμμα απαιτεί , τόσο περισσότερος χρόνος χρειάζεται για να τρέξει . Μια αναζήτηση πρώτα κατά βάθος πρέπει να θυμόμαστε τις προηγούμενες κόμβους επισκεφτεί , έτσι ώστε το ποσό χειρότερη περίπτωση της μνήμης που χρειάζεται είναι ίσος με τον αριθμό των κόμβων στο δέντρο .
Η
εικόνων