关于空间复杂度的普遍困惑
我无法理解空间复杂性。我的一般问题是：树上算法的空间复杂度如何小于树中节点的数量？这是一个具体的例子：
如果b是分支因子 d 是最浅目标节点的深度， m 是状态空间中任意路径的最大长度
对于 DFS，空间复杂度假设为 O(bm)。我以为它总是树的大小？树的其余部分在哪里？我们如何以 O(bm) 空间复杂度使用整个树？
I'm having trouble understanding space complexity. My general question is: how can the space complexity of an algorithm on a tree be smaller than the number of nodes in the tree? Here's a specific example:
If b is the branching factor
d is Depth of shallowest goal node and,
m is Maximum length of any path in the state space
For DFS, the space complexity is supposed to be O(bm). I thought it would just always be the size of the tree? Where's the rest of the tree and how do we use the entire tree with only O(bm) space complexity?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
算法的空间复杂度通常与原始数据占用的空间是分开的。
举例来说，在搜索一棵树时，您可能会在树中保留一堆节点，您将通过该树向下到达某个特定的叶子。在这种情况下，三者占用 O(N) 空间，但搜索（假设平衡树）占用树本身占用的 O(log N) 空间。
The space complexity of an algorithm is normally separate from the space taken by the raw data.
Just for example, in searching a tree you might keep a stack of the nodes in the tree you descended through to get to some particular leaf. In this case, the three takes O(N) space, but the search takes (assuming a balanced tree) O(log N) space over and above what the tree itself occupies.
因为空间复杂度代表了除了输入之外它所占用的额外空间。
一般来说，复杂性的定义与图灵机相关。算法占用的空间是其运行所需的额外单元数。输入单元不被考虑在内，并且可以被算法重用以减少额外的存储。
Because space complexity represents the extra space it takes besides the input.
Complexity, in general, is defined related to turing machines. The space an algorithm takes is the extra number of cells needed for it to run. The input cells are not taken into account, and can be reused by the algorithm to reduce extra storage.