我正在尝试计算以下两个函数的时间复杂度，但我很困惑，因为我在其中一个循环中调用了一个函数。我们在计算时间复杂度的时候有没有考虑。该函数在 if 语句条件检查中调用，并且它具有 o(n)。另外，我正在使用 Java 中的内置排序函数对列表进行排序，我是否也必须计算它？
public static List<Edge> getMSTUsingKruskalAlgorithm(int[][] graph, int[] singlePort) {
List<Edge> edges = getEdges(graph);
List<Edge> edges2 = getEdges(graph);
DisjointSet disjointSet = new DisjointSet(graph.length);
int chp=1000,x=-1,y=-1;
List<Edge> mstEdges = new ArrayList<>();
for(int i=0;i<singlePort.length;i++){
chp=1000;
x=-1;
y=-1;
for(Edge edge:edges){
if(( edge.x==singlePort[i]) && (!find(singlePort,edge.y))) {
if(edge.w<chp){
chp=edge.w;
x=edge.x;
y=edge.y;
}
}
}
int xSet = disjointSet.find(x);
int ySet = disjointSet.find(y);
if (xSet != ySet) {
disjointSet.union(x,y);
mstEdges.add(new Edge(x,y,chp));
edges2.remove(new Edge(x,y,chp));
for(Edge edge2:edges)
{
if(edge2.x==x || edge2.y==x)
edges2.remove(edge2);
}// end of loop
}// end of if statement
}// end of loop
Collections.sort(edges2);
for (Edge edge : edges2) {
int xSet = disjointSet.find(edge.x);
int ySet = disjointSet.find(edge.y);
if (xSet != ySet) {
disjointSet.union(edge.x, edge.y);
mstEdges.add(edge);
}
}
return mstEdges;
}
private static boolean find( int [] arr, int val)
{
boolean x= false;
for (int i=0;i<arr.length;i++)
if(arr[i]==val)
{ x=true;
break;}
return x;
}
最佳答案
你的外层循环是 O(n) 其中 n 是 singlePort 中的元素数
您的内部循环是 O(m)，其中 m 是边列表中的边数。
在此循环中，您调用 find(singlePort) 函数 - 将其视为嵌套循环
find() 函数是O(n) 其中n 是arr 中元素的数量> 这是 singlePort。
你有三层嵌套循环，因此你增加了它们的时间复杂度。注意:退出条件始终是运行时的良好指标
n * m * n = n^2 * m
如果 m == n 那么你的算法是 O(n * n * n) = O(n^3)
否则，从它的写法来看，我们最多只能说:
O(n^2 * m)
关于java - 这个代码段的时间复杂度是O(n^2)还是O(n^3)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/47188426/