关于迭代加深深度优先搜索（IDDFS）空间复杂度的疑问

• 核心结论先明确：IDDFS的空间复杂度确实是O(bd)（部分资料也会简化表述为O(d)，本质逻辑一致），绝非O(b^d)，根源在于它的运行机制：
  • IDDFS是多次执行独立的深度受限DFS，每一轮的深度限制从1开始逐步递增。每一轮DFS结束后，该轮占用的栈空间会被完全释放，才会启动下一轮更深的搜索。
• 针对你提到的图示疑问：
  • 当算法处理节点C及其子节点时，节点B的子节点不在内存中。处理B分支是上一轮（更浅深度限制）的DFS操作，那一轮结束后栈已清空，当前轮是重新从根节点出发遍历C的分支，此时内存里仅保留根到当前节点（C或其子节点）的一条路径。
  • 图示里的涂黑节点是所有被访问过的节点的总记录，不是同一时刻存在于内存中的节点。每一轮DFS只会在内存中维护当前的搜索路径，不会同时持有多个分支的节点。
• 关于最坏情况的空间复杂度：
  • 哪怕目标节点在最深层（比如你说的G节点），IDDFS在搜索时也只会在内存中保存当前的一条搜索路径，路径长度为当前深度限制d，每个节点最多关联b个子节点的指针/引用，但整体空间开销是线性的O(bd)，而非指数级的O(b^d)——后者是广度优先搜索（BFS）的空间复杂度，因为BFS需要同时保存同一层的所有节点。

内容的提问来源于stack exchange，提问作者Crocs123