1
次の2つの関数の時間複雑度を計算しようとしていますが、関数を呼び出す。時間の複雑さを計算するときに考慮しますか？この関数はif文の条件チェックで呼び出され、o（n）を持ちます。また、私はJavaでソート関数のビルドを使用してリストをソートしていますが、それも計算する必要がありますか？このコードセグメントの時間複雑度はO（n^2）かO（n^3）
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;
}
メソッドAのリストをループし、Aを呼び出す別のプライベートメソッドBの中にループを入れるメソッドをリファクタリングすると、そのタスクを達成するために必要な操作の数が変わりますか？タスクは突然O（1）になります。つまり、リストのサイズに関係なく、一定の時間内に実行されますか？ –
関数内で起こるすべてを考慮する必要があります。たとえば、 'disjointSet.union'と' disjointSet.find'を呼び出します。これらの操作の複雑さも考慮する必要がありますが、それがコードであるかどうかは不明です。 – Cephalopod