gpt4 book ai didi

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

转载 作者:塔克拉玛干 更新时间:2023-11-03 05:55:44 27 4
gpt4 key购买 nike

我做了一个算法来解决一个问题,但我不知道它的复杂性。该算法验证图形的所有顶点是否“好”。 “好”顶点是指可以按照自己开始的路径访问图中所有其他顶点的顶点。

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

谢谢,对不起我的英语。

最佳答案

我认为复杂度为 O(n^2),因为您通过调用使用嵌套循环:

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

关于java - 这个简单算法的复杂性,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/37647045/

27 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com