이 간단한 알고리즘의 복잡성

Question

문제를 해결하기위한 알고리즘을 수행했지만 그 복잡성을 알지 못합니다. 알고리즘은 그래프의 모든 정점이 "양호"한지 확인합니다. "좋은"정점은 자신을 시작한 경로를 따라 그래프의 다른 모든 정점에 액세스 할 수있는 정점입니다. 내 영어에 대한

public static boolean verify(Graph graph) 
{ 
    for(int i=0; i < graph.getVertex().size(); i++) 
    { 
     // List of vertexes visited 
     ArrayList<Character> accessibleVertex = new ArrayList<Character>(); 
     getChildren(graph.getVertex().get(i), graph.getVertex().get(i).getName(), accessibleVertex);  

     // If the count of vertex without father equals a count of the list of vertexes visited, his is a "good" vertex 
     if((graph.getVertex().size()-1) == accessibleVertex.size()) 
      return true; 
    } 

    return false; 
} 

private static void getChildren(Vertex vertex, char fatherName, ArrayList<Character> accessibleVertex) 
{ 
    // Ignore the 'father' 
    if(vertex.getName() != fatherName) 
     addIfUnique(vertex.getName(), accessibleVertex); 

    for(int i=0; i < vertex.getEdges().size(); i++) 
    { 
     getChildren(vertex.getEdges().get(i).otherVertex(), fatherName, accessibleVertex); 
    } 
} 

private static void addIfUnique(char name, ArrayList<Character> accessibleVertex) 
{ 
    boolean uniqueVertex = true; 

    for(int i=0; i < accessibleVertex.size(); i++) 
    { 
     if(accessibleVertex.get(i).equals(name)) 
      uniqueVertex = false; 
    } 

    if(uniqueVertex) 
     accessibleVertex.add(name); 
} 

Graph tested

감사하고 죄송합니다.

Answer 1

난 당신이 중첩 루프를 사용하기 때문에 호출하여 복잡도가 O (N^2) 생각 :

getChildren(graph.getVertex().get(i), graph.getVertex().get(i).getName(), accessibleVertex);