迭代加深深度優先搜索比深度優先搜索更高的時間複雜度？

Question

看來，迭代深化搜索應該比BFS較高的時間複雜度，因爲每一個深度的限制增加的時候，就必須從頭開始其搜索。

但維基說，否則，爲什麼呢？

Answer 1

如果樹是不是平衡，答案就在於更接近根部比最深的葉子，那麼答案將被深度限制小於樹的最大深度發現的，而深度優先搜索可能在找到正確的答案之前，必須搜索樹的一半達到最大深度。由於樹中節點的數量可能隨着深度呈指數增長，所以這可能是一個很好的選擇 - 最大深度爲10時，大致搜索1024/2 = 512個節點的成本比多次搜索總共1 + 2 + 4 + ... 256 = 511節點，所以比這更極端的是純粹的利潤 - 並且該示例完全搜索深度達到幷包括深度8的深度。

（在某些情況下，有可能在任意大深度錯誤的答案）。