看来迭代加深搜索的渐近时间复杂度应该比BFS高，因为每增加一次depth-limit，都要从头开始搜索。
但 wiki 另有说法，为什么？
最佳答案
如果树不平衡并且答案比最深的叶子更靠近根，那么答案将通过小于树的最大深度的深度限制找到，而深度优先搜索可能有在找到正确答案之前搜索树的一半到最大深度。由于树中的节点数可能随深度大致呈指数增长，这可能是一个很好的交易 - 最大深度为 10，搜索大约 1024/2 = 512 个节点比多次搜索总计 1 + 2 + 4 + ... 256 = 511 个节点，所以任何比这更极端的东西都是纯利润 - 该示例完全搜索深度达到并包括深度 8。
(在某些情况下，任意大的深度都可能出现错误答案)。
关于algorithm - 迭代加深深度优先搜索比深度优先搜索的时间复杂度更高？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/23209272/