图表表示基准
目前我正在开发一个程序，解决（如果可能的话）任何给定的迷宫尺寸从3X4到26×30。 我使用adj矩阵（稀疏）和adj列表来表示图形。 我想知道如何输出DFS使用一个然后另一个方法找到解决方案所花费的总时间。 以编程方式，我怎么能产生这样的基准？
一个有用的表来解决各种图形实现：
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;
答案是以纳秒为单位，并且无法保证准确性，因此请谨慎使用。 进行多次运行的平均值（并检查方差是否较低，丢弃与平均值相差较远的结果）将使结果保持一致。
假设你有一个合适的方法，这应该是相当简单的。 只需将方法包装在计时器中，并重复多次以获得统计显着性。
--test method with adjacency matrix start = TimeNow() repeat 1000 times DepthFirstSearchWithAdjMatrix() timePerSearch = (TimeNow() - start) / 1000.0 --test method with adjacency list start = TimeNow() repeat 1000 times DepthFirsySearchWithAdjList() timePerOtherSearch = (TimeNow() - start) / 1000.0 if timePerSearch < timePerOtherSearch print "Adj Matrix is better than adj list" else print "Adj Matrix is worse than adj list"