다음 알고리즘의 복잡성은 무엇입니까?

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 - 문제는