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

Question

看来，迭代深化搜索应该比BFS较高的时间复杂度，因为每一个深度的限制增加的时候，就必须从头开始其搜索。

但维基说，否则，为什么呢？

Answer 1

如果树是不是平衡，答案就在于更接近根部比最深的叶子，那么答案将被深度限制小于树的最大深度发现的，而深度优先搜索可能在找到正确的答案之前，必须搜索树的一半达到最大深度。由于树中节点的数量可能随着深度呈指数增长，所以这可能是一个很好的选择 - 最大深度为10时，大致搜索1024/2 = 512个节点的成本比多次搜索总共1 + 2 + 4 + ... 256 = 511节点，所以比这更极端的是纯粹的利润 - 并且该示例完全搜索深度达到并包括深度8的深度。

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