java - 有没有更快的算法来构造该图的邻接表？

我的问题是找到一个更好的算法来填充邻接列表。
规格：

G = (V , E ) //the graph
V ={w} //vertex in this case each vertex is an array
E={⟨u,v⟩| u,v ∈V ∧ u>v} // edge only if u > v
u > v only if  foreach i u̸=v ∧ u[i]≥v[i]. // (u>v and v>w => u>w)

我的天真代码复杂度O（（v+1）*v/ 2）o o（n^ 2）是

private void riempiAdj() {
    for(int i=0;i<nodi.length;i++)
        for(int j=i+1;j<nodi.length;j++)
            if(nodi[i].eMaggiore(nodi[j]))
                nodi[i].adj.inserisci(nodi[j]);
}

nodi是顶点数组
adj是邻接列表
AdjList.inserisci(Vertex t)将顶点t添加到邻接列表o（1）
Vertex.eMaggiore(Vertex t)在this>t O（1）中返回true
存在O（V）或O（V＊（？）v）复杂性的算法？

最佳答案

在最坏的情况下，你试图建立的图形有Θ（| V | 2）边（边的总数是0+1+2++| v-1=v（v-1）/2），因此任何为图显式构建邻接列表的算法都必须在最坏情况下执行Ω（v 2），因为需要添加许多边。
由于这里的边有一个很好的模式，可以想象您可以创建某种延迟计算的邻接列表，仅在需要时创建边，尽管这是一个单独的问题。