Komplexität dieses einfachen Algorithmus

Question

Ich habe einen Algorithmus, um ein Problem zu lösen, aber ich kenne seine Komplexität nicht. Der Algorithmus überprüft, ob alle Scheitelpunkte eines Graphen "gut" sind. Ein "guter" Eckpunkt ist ein Eckpunkt, der auf alle anderen Eckpunkte eines Graphen zugreifen kann, der einem Pfad folgt, der sich selbst gestartet hat.

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

Dank und sorry für mein Englisch.

Answer 1

ich denke, die Komplexität ist O (n^2), da Sie verwenden eine verschachtelte Schleife durch den Aufruf:

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