0

私は現在、いくつかの改訂に取り組んでおり、具体的には Big-O 記法について検討しています。同様の質問 (別のアルゴリズムを扱ったもの) をしましたが、正しい方法で行っているかどうかはまだわかりません。

私が検討しているアルゴリズムは、Exhaustive Search (別名ブルート フォースだと思います) で、次のようになります。

Input: G- the graph
   n- the current node
   p– the path so far
1) For every edge nm (from n to m) in G do
2)    If m ∉ p then
3)       p = p ∪ {m}
4)       Exhaustive(G, m, p)
5)    End If
6) End For

これまでのところ、このアルゴリズムは正しいという結果に達しましたO(n)。これは正しいですか? 私はそれが正しいとは思えませんし、それを解決する方法を正確に知りたいと思っています。何を探すべきか、毎回「数える」のは正確には何なのか、などなど。実行中の操作の数を数える必要があることは理解していますが、メモを取る/数える必要があるのはそれだけですか?

編集: 実際、このアルゴリズムが正しいことを知りました。これはO((n-1)!)正しいのですか? もしそうなら、この解決策はどのようにして解決できたのでしょうか?

4

1 に答える 1

1

通常（常にではありませんが）グラフの場合、入力サイズnはグラフ内のノードの数です。関数（ランタイムは言うまでもなく）が少なくともn何度も呼び出されることを証明するのはかなり簡単です-グラフを通る単一のパス（接続されていると仮定すると、すべてのノードが他のすべてのノードから何らかのパスを介して到達可能であると仮定します） `n'が呼び出します。

再帰関数の実行時間を計算する場合、実行時間の上限は、再帰関数が呼び出された回数に、1回の呼び出しで関数の実行時間を掛けたものになります。

最悪の場合の実行時間がであることを確認するにはO((n-1)!)、完全に接続されたグラフにあるパスの数を検討します。任意のノードから任意のノードに直接アクセスできます。これを言い換える別の方法は、開始状態を保存して、任意の順序でノードにアクセスできることです。これは、（n-1）要素の順列の数と同じです。パス上の各状態（ ）にO(n!)かかるすべてのエッジを反復処理しているため、実際にはそうなると思います。編集：より正確には、私たちはそれがだと言うことができます。詳細については、コメントを参照してください。O(n)n*(n-1)!big-omega(N!)

場合によっては、実際のコードよりもアルゴリズムが計算する内容、つまりすべての状態のカーディナリティ（ここではより具体的にはパス）を確認する方が簡単な場合があります。

于 2011-05-06T21:08:35.730 に答える