くうかん‐けいさんりょう〔‐ケイサンリヤウ〕【空間計算量】
空間計算量
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2015/11/08 04:34 UTC 版)
深さ制限探索は深さ優先探索の一種であるため、空間計算量は通常の深さ優先探索と同じである。
※この「空間計算量」の解説は、「深さ制限探索」の解説の一部です。
「空間計算量」を含む「深さ制限探索」の記事については、「深さ制限探索」の概要を参照ください。
空間計算量
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/07/20 15:01 UTC 版)
見つかったノードを全て記録する必要があるので、幅優先探索の空間計算量はO(|V|)となる。ここで|V|はグラフ内のノードの数である。または、 O ( B M ) {\displaystyle O(B^{M})} ということができる。Bは枝分かれの最大数で、Mは木の最長経路の長さ。指数関数故に、幅優先探索は大量の情報から探索する事に向かない根拠になる。
※この「空間計算量」の解説は、「幅優先探索」の解説の一部です。
「空間計算量」を含む「幅優先探索」の記事については、「幅優先探索」の概要を参照ください。
ウィキペディア小見出し辞書の「空間計算量」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ。
- 空間計算量のページへのリンク
