L'Espace/temps de la Complexité de la Profondeur d'Abord de Recherche

J'ai regardé divers autres StackOverflow réponse et ils sont tous différents de ce que mon professeur a écrit dans son diapositives.

Profondeur de la Première Recherche a une complexité temporelle en O(b^m), où b est le
maximum facteur de branchement de l'arbre de recherche, et m est la profondeur maximale
de l'espace d'état. Terrible si m est beaucoup plus grand que d, mais si la recherche
l'arbre est "touffu", peut-être beaucoup plus rapide que la Largeur de la Première Recherche.

Il continue à dire..

L'espace de la complexité est O(bm), c'est à dire l'espace linéaire de la longueur de l'action
séquence de! Besoin seulement de stocker un seul chemin de la racine à la feuille
nœud, le long avec le reste de la non développé des nœuds frère pour chaque noeud sur
chemin d'accès.

Une autre réponse sur StackOverflow déclare qu'il est O(n + m).

Parcours en profondeur d'abord de la recherche et de l'ampleur de recherche sont les termes génériques qui peuvent se référer à un grand nombre d'algorithmes, comme la recherche d'un arbre ou de faire une attaque par force brute sur les états d'un jeu.

OriginalL'auteur TheRapture87 | 2016-04-07