次のアルゴリズムの複雑さは？

Question

このアルゴリズムは、ハミルトニアン経路の問題を解決します。 Gは、未定義のグラフであり、v開始頂点、 G.size()グラフのサイズ、G.get(v).gV現在の頂点のすべての隣接するベリファイです。

static private void dfs(HashMap<Integer, Virsune> G, int v) { 
    path.push(v); 
    // add v to the current path 
    onPath[v] = true; 

    if (path.size() == G.size()) { 
     System.out.println(path); 

     Integer[] tmp = new Integer[G.size()]; 
     System.arraycopy(path.toArray(), 0, tmp, 0, path.size()); 
     hamPaths.add(tmp); 
    } 

    for (int w : G.get(v).gV) { 
     if (!onPath[w]) { 
      dfs(G, w); 
     } 
    } 

    path.pop(); 
    onPath[v] = false; 

} 
    // main method 
    dfs(G,0); 

このアルゴリズムの複雑さはO（n！）だと言うことはできますか？

Answer 1

これはアルゴリズムのグラフのすべてのパスを列挙しています。

グラフ内のすべてのパスを列挙している場合、ランタイムにヒントが表示されます。完全なグラフには、本当にn！これは下限です。もしそれが上限であれば、私はそれをあなたに残しておきます。

FWIW - 問題がO（2^n）の中で解けるある