Mengapa DFS dianggap memiliki kompleksitas ruang

Menurut catatan ini , DFS dianggap memiliki kompleksitas ruang , di mana b adalah faktor percabangan dari pohon dan m adalah panjang maksimum dari setiap jalur di ruang negara.$O(bm)$$b$$m$

Hal yang sama juga dikatakan di halaman Wikibook ini pada Pencarian Tidak Informasi .

Sekarang "infobox" dari artikel Wikipedia tentang DFS menyajikan berikut untuk kompleksitas ruang dari algoritma:

, jika seluruh grafik dilintasi tanpa pengulangan, O ( panjang jalur terpanjang dicari ) untuk grafik tersirat tanpa menghilangkan duplikat node$O(|V|)$$O($$)$

yang lebih mirip dengan apa yang saya pikir adalah kompleksitas ruang DFS, yaitu, , di mana m adalah panjang maksimum yang dicapai oleh algoritma.$O(m)$$m$

Mengapa saya berpikir demikian?

Yah, pada dasarnya kita tidak perlu menyimpan node lain selain node dari path yang saat ini kita lihat, jadi tidak ada gunanya mengalikan dengan dalam analisis yang disediakan baik oleh Wikibook dan catatan yang saya referensikan kepada Anda untuk.$b$

Selain itu, menurut makalah ini pada IDA * oleh Richard Korf , kompleksitas ruang DFS adalah , di mana d dianggap sebagai "cutoff kedalaman".$O(d)$$d$

Jadi, apa kompleksitas ruang DFS yang benar?

Saya pikir itu mungkin tergantung pada implementasinya, jadi saya akan menghargai penjelasan tentang kompleksitas ruang untuk implementasi yang dikenal berbeda.

$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$

Pada titik ini, tumpukan berisi

$(b-1)m + 1$

Ada dua hal yang perlu diperhatikan di sini:

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

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

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

Semoga ini membantu,