java - 这个简单算法的复杂性

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

图测试

谢谢和对不起我的英语。

Answer 1

我认为复杂性是 O(n^2)，因为您通过调用使用嵌套循环：

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