關於空間複雜度的一般困惑

Question

我無法理解空間複雜性。我的一般問題是：樹上算法的空間複雜度如何小於樹中節點的數量？下面是一個具體的例子：

如果b是支化因子 d是淺的目標節點的深度和， m是在狀態空間中的任何路徑的最大長度

對於DFS，空間複雜性是應該是O（bm）。我認爲這隻會是樹的大小？樹的其餘部分在哪裏，我們如何使用只有O（bm）空間複雜度的整個樹？

Answer 1

因爲空間複雜度代表除輸入外還需要的額外空間。

複雜性一般與圖靈機有關。算法需要的空間是它運行所需的額外數量的單元。輸入單元不被考慮在內，並且可以被算法重用以減少額外的存儲空間。

Answer 2

算法的空間複雜度通常與原始數據佔用的空間分開。

只是，例如，在搜索一棵樹時，您可能會留下一堆堆在下降的樹中的節點，以便到達某個特定的樹葉。在這種情況下，三者需要O（N）空間，但是搜索需要（假定一棵平衡樹）O（log N）空間，超過樹本身佔用的空間。