似乎迭代深化搜索应该具有比BFS更高的渐近时间复杂度，因为每次深度限制增加时，它必须从头开始搜索 .
但维基说不然，为什么？
如果树不 balancer 且答案比最深的叶子更靠近根，那么答案将通过深度限制找到，该深度限制小于树的最大深度，而深度优先搜索可能必须搜索一半树找到正确答案之前的最大深度 . 由于树中节点的数量可能随着深度呈指数增长，这可能是一个很好的讨价还价 - 最大深度为10，搜索大约1024/2 = 512个节点比多次搜索总计1 2 4稍贵一些...... 256 = 511个节点，所以任何比这更极端的东西都是纯粹的利润 - 而这个例子完全搜索深度8并包括深度8 .
（在某些情况下，在任意大的深度可能会有错误的答案） .
1 回答
如果树不 balancer 且答案比最深的叶子更靠近根，那么答案将通过深度限制找到，该深度限制小于树的最大深度，而深度优先搜索可能必须搜索一半树找到正确答案之前的最大深度 . 由于树中节点的数量可能随着深度呈指数增长，这可能是一个很好的讨价还价 - 最大深度为10，搜索大约1024/2 = 512个节点比多次搜索总计1 2 4稍贵一些...... 256 = 511个节点，所以任何比这更极端的东西都是纯粹的利润 - 而这个例子完全搜索深度8并包括深度8 .
（在某些情况下，在任意大的深度可能会有错误的答案） .