图表表示基准

Question

目前我正在开发一个程序,解决(如果可能的话)任何给定的尺寸从3X4到26x30的迷宫.我使用adj矩阵(稀疏)和adj列表来表示图形.我想知道如何输出DFS使用一个然后另一个方法找到解决方案所花费的总时间.以编程方式,我怎么能产生这样的基准？

Answer 1

一个有用的表来解决各种图形实现:

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²)添加和删​​除顶点的原因,因为你必须重新分配矩阵.

刚准备好这篇文章,为什么我准备好了:)

这与基准测试没有直接关系,因为通常您会研究您最需要的操作,并根据您的需求选择正确的实现,因此通过研究您要实施的内容,这是一种"理论"基准.否则,您只需测量代码完成两个实现的整个工作所需的时间并进行比较.

编辑:因为你使用稀疏矩阵实现,操作的复杂性可能会略有变化(大多数情况会变得更糟,因为你为了速度而交换内存).

EDIT2:好的,既然我知道这是Java,那将很简单:

long before = System.nanoTime();

/* execution of your algorithm */

long elapsed = System.nanoTime() - before;

答案是以纳秒为单位,并且无法保证准确性,因此请谨慎使用.进行多次运行的平均值(并检查方差是否较低,丢弃与平均值相差较远的结果)将使结果保持一致.