Сложность этого простого алгоритма

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);