Pourquoi DFS est-il considéré comme ayant une complexité d'espace

Selon ces notes , DFS est considéré comme ayant une complexité d'espace , où b est le facteur de ramification de l'arbre et m est la longueur maximale de tout chemin dans l'espace d'état.$O(bm)$$b$$m$

La même chose est dite dans cette page Wikibook sur la recherche non informée .

Maintenant, l '"infobox" de l'article de Wikipedia sur DFS présente ce qui suit pour la complexité spatiale de l'algorithme:

, si le graphe entier est parcouru sans répétition, O (la plus longue longueur de chemin recherchée ) pour les graphes implicites sans élimination des nœuds en double$O(|V|)$$O($$)$

ce qui est plus similaire à ce que je pensais être la complexité spatiale de DFS, c'est-à-dire , où m est la longueur maximale atteinte par l'algorithme.$O(m)$$m$

Pourquoi est-ce que je pense que c'est le cas?

Eh bien, fondamentalement, nous n'avons pas besoin de stocker d'autres nœuds que les nœuds du chemin que nous examinons actuellement, il n'y a donc aucun intérêt à multiplier par dans l'analyse fournie à la fois par le Wikibook et les notes que je vous renvoie à.$b$

De plus, selon cet article sur IDA * de Richard Korf , la complexité spatiale de DFS est , où d est considéré comme le "seuil de profondeur".$O(d)$$d$

Alors, quelle est la complexité spatiale correcte de DFS?

Je pense que cela peut dépendre de l'implémentation, donc j'apprécierais une explication de la complexité de l'espace pour les différentes implémentations connues.

$b$$m$$[b]$$m$

1. $1,2,\ldots,b$

2. $1$$11,12,\ldots,1b$

3. $11$$111,112,\ldots,11b$

4. $\ldots$

5. $1^{m-1}$$1^m,1^{m-1}2,\ldots,1^{m-1}b$

À ce stade, la pile contient

$(b-1)m + 1$

Il y a deux points à souligner ici:

1. $O(bd)$$b$$d$$d$$b$$b$$O(d)$

2. $O(d)$$d$$b$

$O(bd)$$O(d)$

J'espère que cela t'aides,