我无法理解空间复杂性 . 我的一般问题是：树上算法的空间复杂度如何小于树中节点的数量？这是一个具体的例子：
如果b是分支因子，则d是最浅目标节点的深度，并且m是状态空间中任何路径的最大长度
对于DFS，空间复杂度应该是O（bm） . 我以为它会一直是树的大小？树的其余部分在哪里？我们如何使用只有O（bm）空间复杂度的整个树？
因为空间复杂性代表了除输入之外所需的 extra 空间 .
通常，复杂性与图灵机相关 . 算法所采用的空间是运行所需的额外单元数 . 输入单元不被考虑在内，并且可以由算法重用以减少额外的存储 .
算法的空间复杂度通常与原始数据占用的空间分开 .
例如，在搜索树时，您可能会在树中保留一堆节点，以便到达某个特定的叶子 . 在这种情况下，三个占用O（N）空间，但搜索（假设一个 balancer 树）O（log N）空间超过树本身占用的空间 .
2 回答
因为空间复杂性代表了除输入之外所需的 extra 空间 .
通常，复杂性与图灵机相关 . 算法所采用的空间是运行所需的额外单元数 . 输入单元不被考虑在内，并且可以由算法重用以减少额外的存储 .
算法的空间复杂度通常与原始数据占用的空间分开 .
例如，在搜索树时，您可能会在树中保留一堆节点，以便到达某个特定的叶子 . 在这种情况下，三个占用O（N）空间，但搜索（假设一个 balancer 树）O（log N）空间超过树本身占用的空间 .