幅優先探索、と深さ優先探索の時間計算量について質問です

Question

アルゴリズムの勉強をしています。問題がわからないのでお力をお貸しください。

一般に深さがｄ、最大分岐数がbの木の探索で、幅優先探索と深さ優先探索の最悪時間計算量と最悪空間計算量を考えているのですが、

最悪の場合は幅優先も深さ優先も同じだと考えました。

まず最悪空間計算量に関して、
ノードの総数（グラフの頂点数）が最悪空間計算量になるので、
根から順に各深さごとのノード数を考えると1,b,b^2,b^3...,b^(d-1),b^dとなっていくいので
空間計算量はこの和ですが、オーダーは最大のもののみで表示しO(b^d)になる。

次に最悪時間計算量ですが、
これは木の辺の総数が最悪時間計算量にあたり、辺の数は深さ１で分岐数のb本、深さ2で分岐数のb^2本...という感じなので
結局オーダーは同じでO(b^d)かと思いました。

どうでしょうか。私の解答はあっていますでしょうか。ご回答お願いします。

Answer 1

通常はノード数との対比で求めると思います。O(N) ですね。ただツリーは探索に有利になるよう作るものなので、最悪でも O(log n) とかになることが多いんじゃないかと思います。b と d を使うことがあるのかはちょっとイメージできませんが、使うとすればそれでいいのではないかと思います。ただ、例えばバイナリツリーのように全探索の必要のないツリーもあるので、それは実装次第としか言えません。

Comments

[asapan]

ご回答ありがとうございます。
そうですね、仰る通りなのですが、これはただアルゴリズムに関して考察する問題なので通常はどう...という話ではなく、こういう状況のときはどうなるかを考えるものになっております。

これで問題ないだろうとのこと、ありがとうございます。

[Zuishin]

いえ、アルゴリズム次第ということです。それが何もないので、このようなざっくりとしたことしか答えられません。