アルゴリズムの勉強をしています。問題がわからないのでお力をお貸しください。
一般に深さがd、最大分岐数がbの木の探索で、幅優先探索と深さ優先探索の最悪時間計算量と最悪空間計算量を考えているのですが、
最悪の場合は幅優先も深さ優先も同じだと考えました。
まず最悪空間計算量に関して、
ノードの総数(グラフの頂点数)が最悪空間計算量になるので、
根から順に各深さごとのノード数を考えると1,b,b^2,b^3...,b^(d-1),b^dとなっていくいので
空間計算量はこの和ですが、オーダーは最大のもののみで表示しO(b^d)になる。
次に最悪時間計算量ですが、
これは木の辺の総数が最悪時間計算量にあたり、辺の数は深さ1で分岐数のb本、深さ2で分岐数のb^2本...という感じなので
結局オーダーは同じでO(b^d)かと思いました。
どうでしょうか。私の解答はあっていますでしょうか。ご回答お願いします。
回答1件
あなたの回答
tips
プレビュー
バッドをするには、ログインかつ
こちらの条件を満たす必要があります。
2019/07/15 02:56
2019/07/15 03:00