图形表示基准

图形表示基准

一个有用的表格，用于处理各种图形实现：

OPERATION    EDGE LIST      ADJ LIST  ADJ MATRIXdegree(v)      O(m)         O(d(v))     O(n)incidentEdges(v)          O(m)         O(d(v))     O(n)areAdjacent(v1,v2)        O(m)         O(min(d(v1),d(v2))     O(1)addVertex(v)   O(1)         O(1)        O(n²)addEdge(v)     O(1)         O(1)        O(1)removeVertex(v)O(m)         O(m)        O(n²)removeEdge(e)  O(m)         O(d(v1)+d(v2))         O(1)memory         O(m+n)       O(m+n)      O(n²)

其中，

m

是边数，

n

是顶点数，

d(vertex)

是顶点邻接表中的元素数。adj矩阵实现具有

O(n²)

添加和删​​除顶点的功能，因为您必须重新分配矩阵。

刚刚准备了这篇文章，这就是为什么我要准备它的原因:)

这与基准测试没有直接关系，因为通常您会研究最需要的 *** 作并根据需要选择正确的实现，因此这是通过研究要实现的目标进行的一种“理论”基准测试。否则，您只需衡量代码在两个实现上完成全部工作所需的时间，然后进行比较即可。

编辑： 由于您使用稀疏矩阵实现，因此 *** 作的复杂性可能会略有变化（大多数情况会更糟，因为您要以内存换取速度）。

EDIT2： 好的，现在我知道这是Java，它将非常简单：

long before = System.nanoTime();long elapsed = System.nanoTime() - before;

答案以纳秒为单位，并且不能保证准确性，因此请小心使用此设备。进行多次运行的平均值（并检查方差低，丢弃与平均值相差较远的结果）将使您的结果具有连贯性。