反復深化深さ優先探索
IDDFSの時間計算量は、平衡のとれた木では深さ優先探索と同じ O ( b d ) {\displaystyle O(b^{d})} である。
反復深化探索では、底辺レベルのノードは1回展開され、その1つ上のレベルのノードは2回、根ノードは d + 1 {\displaystyle d+1} 回展開される。したがって総展開回数は次のようになる。
( d + 1 ) 1 + ( d ) b + ( d − 1 ) b 2 + . . . + 3 b d − 2 + 2 b d − 1 + b d {\displaystyle (d+1)1+(d)b+(d-1)b^{2}+...+3b^{d-2}+2b^{d-1}+b^{d}}
例えば b = 10 {\displaystyle b=10} で d = 5 {\displaystyle d=5} の場合、具体的には次のようになる。
6 + 50 + 400 + 3,000 + 20,000 + 100,000 = 123,456
これは、幅優先探索や深さ制限探索を行ったときのノード展開回数に対して11%の増加にしかならない。分岐係数が大きくなればオーバーヘッドも小さくなるが、分岐係数が2だったとしても、幅優先探索の2倍にしかならない。そのため、時間計算量は O ( b d ) {\displaystyle O(b^{d})} で、空間計算量は O ( b d ) {\displaystyle O(bd)} となる。一般に、探索空間が広く深さが未知の場合、反復深化深さ優先探索が最も好ましい方法とされている。