algorithm - 迭代加深深度优先搜索比深度优先搜索的时间复杂度更高？

Question

似乎迭代加深搜索应该比 BFS 具有更高的渐近时间复杂度，因为每次增加深度限制时，它都必须从头开始搜索。

但是wiki说不然，为什么？

Answer 1

如果树不平衡并且答案比最深的叶子更靠近根，那么将通过小于树的最大深度的深度限制找到答案，而深度优先搜索可能必须搜索一半在找到正确答案之前，树的最大深度。由于树中的节点数量可能会随着深度大致呈指数增长，这可能是一个很好的交易 - 最大深度为 10，搜索大约 1024/2 = 512 个节点比总计 1 + 2 + 4 + 的多个搜索稍微贵一些... 256 = 511 个节点，所以任何比这更极端的都是纯利润 - 该示例完全搜索深度，包括深度 8。

（在某些情况下，在任意大的深度可能会有错误的答案）。