use*_*342 0 algorithm tree complexity-theory
我无法理解空间复杂性.我的一般问题是:树上算法的空间复杂度如何小于树中节点的数量？这是一个具体的例子:
如果b是分支因子,则d是最浅目标节点的深度,并且m是状态空间中任何路径的最大长度
对于DFS,空间复杂度应该是O(bm).我以为它总是那么大小的树？树的其余部分在哪里,我们如何使用只有O(bm)空间复杂度的整个树？
算法的空间复杂度通常与原始数据占用的空间分开.
例如,在搜索树时,您可能会在树中保留一堆节点,以便到达某个特定的叶子.在这种情况下,三个占用O(N)空间,但搜索(假设一个平衡树)O(log N)空间超过树本身占用的空间.