迭代深化深度优先搜索比深度优先搜索具有更高的时间复杂度

Question

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

但维基却不这么认为，为什么？

Answer 1

如果树不平衡，并且答案比最深的叶子更靠近根部，那么答案将通过小于树的最大深度的深度限制找到，而深度优先搜索可能必须搜索树的一半到最大深度才能找到正确答案。由于树中的节点数量可能会随着深度大致呈指数级增长，这可能是一个不错的选择——在最大深度为10的情况下，搜索大约1024/2=512个节点比总共1+2+4+的多次搜索稍微贵一些。。。256=511个节点，所以任何比这更极端的事情都是纯粹的利润——这个例子完全搜索深度8以内的深度。

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