一个有用的表格，用于处理各种图形实现：
OPERATION EDGE LIST ADJ LIST ADJ MATRIX
degree(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²)添加和删??除顶点的功能，因为您必须重新分配矩阵。
刚刚准备了这篇文章，这就是为什么我要准备它的原因:)
这与基准测试没有直接关系，因为通常您会研究最需要的操作并根据需要选择正确的实现，因此这是通过研究要实现的目标进行的一种“理论”基准测试。否则，您只需衡量代码在两个实现上完成全部工作所需的时间，然后进行比较即可。
由于您使用稀疏矩阵实现，因此操作的复杂性可能会略有变化（大多数情况会更糟，因为您要以内存换取速度）。
好的，现在我知道这是Java，它将非常简单：
long before = System.nanoTime();
/* execution of your algorithm */
long elapsed = System.nanoTime() - before;
答案以纳秒为单位，并且不能保证准确性，因此请小心使用此设备。进行多次运行的平均值（并检查方差低，丢弃与平均值相差较远的结果）将使您的结果具有连贯性。
602392714
清零编程群