私のアルゴリズム分析コースの教師は、ブレスファースト検索の時間計算量はO（V + E）であると教えてくれましたが、人工知能コースの教師は、BFSの複雑さはO（b d ）であると言っています。私が彼に質問したとき、彼は私に論理的な理由を与えました。「理論計算機科学では、グラフは検索アルゴリズムに入力される明示的なデータ構造であるため、O（V + E）が適切です。AIでは、グラフはしばしば表されます。初期状態、アクション、遷移モデルによって暗黙的に、多くの場合無限です。このため、複雑さはO（b d）"で表されます。今私は2つの質問があります
人工知能では、通常、巨大な/無限のグラフを処理します。したがって、これらのグラフにO(V+E)は情報がなく、十分ではないため、より適切な境界を取得しようとします。この境界はですO(B^d)。ここBで、は分岐係数でありd、は解の深さです。この背後にある理論的根拠は、各深さでB方向に「分岐」すると、O(B^d)ノードを探索することになります。
さらに、アルゴリズムコースの従来のBFSは探索アルゴリズムであることに注意してください。これはグラフ全体を探索する（すべての頂点を探索する）必要がありますが、AIではパスファインディングとして使用します。ソースからターゲットへのパスが見つかるまで探索します。 。（必要はありません。グラフ全体を調べることが不可能な場合もあります）
また、ブランチファクターBがあり、すべての葉が深さのあるツリー（ノードが2回検出されない）を見ると、ツリーdには正確にB + B^2 + B^3 + ... + B^d < B^(d+1)ノードがあるため、必要な場合は
O（V + E）とO（b ^ d）がどのように等しいか、最初のものは線形の複雑さのように見え、2番目のものは指数関数的です。
最初のグラフは入力であるため、入力のサイズ、つまりグラフは線形です。
2つ目も、グラフのサイズが線形であり、解の深さが指数関数的です。これは別の要因ですが、頂点を2回以上トラバースする必要がないため、グラフのサイズは線形です。
したがって、ここでは、基本的にO(B^d)はのサブセットであり、複雑さが入力の一部ではないO(V+E)の関数であるという事実に「苦しむ」ことができれば、それよりも有益です。d
ビッグO表記について話すとき、それは、入力が何であれ、上限があるため、同じままである必要があることを意味します。Big Oが有限のデータ入力のみを処理するかどうか？
グラフが無限大の場合、f（n）ごと、および定数c、N-ごとに、大きなOは有益ではないため、c*f(n) < infinity無限大のグラフについて話す場合は役に立ちません。