具有邻接表的恒定时间操作
Constant Time Operations with Adjacency Lists
我正在 Java 中使用邻接列表实现一个图，邻接列表必须使用 space 与边 + 顶点成比例。我的初始程序包含一个长度为 V（顶点数）的数组，每个索引包含一个边的 ArrayList，显示连接到每个顶点的所有边。
现在，我被告知操作 existsEdge(x, y) 必须在 O(1) 时间内 运行。
我想到的方法是访问数组中的索引 x（花费 O(1) 时间）并检查该索引处的列表是否具有 Edge(x,y).
但是，我不确定这个时间复杂度。我知道 ArrayList 在任何特定索引处的长度永远不会超过图中的顶点数，但我不确定这是否被视为常数时间。不管数据量多少，每个list都会有length <= V，所以遍历有明确的上界。
这与 O(1) 相同，还是时间复杂度不同？如果不同，我不确定如何使用 ArrayList 来创建此结构。
您描述的不是 O(1)，而是 O(V)，因为在最坏的情况下，一个顶点可能会连接到所有其他顶点，而 ArrayList 的长度将是 V-1。如果你想要 O(1)，你应该使用 HashSet 而不是 ArrayList。此外，您不需要边 class，您可以简单地存储连接的顶点。
假设顶点 1 连接到 2、4 和 5，那么在数组中的位置 1 处，您将有一个 HashSet (2, 4, 5)。现在，如果您必须检查边 (1, 4) 是否存在，您将转到数组的索引 1（如您所述），然后调用 array[1].contains(4)，这是一个 O(1) 操作。
我正在 Java 中使用邻接列表实现一个图，邻接列表必须使用 space 与边 + 顶点成比例。我的初始程序包含一个长度为 V（顶点数）的数组，每个索引包含一个边的 ArrayList，显示连接到每个顶点的所有边。
现在，我被告知操作 existsEdge(x, y) 必须在 O(1) 时间内 运行。 我想到的方法是访问数组中的索引 x（花费 O(1) 时间）并检查该索引处的列表是否具有 Edge(x,y).
但是，我不确定这个时间复杂度。我知道 ArrayList 在任何特定索引处的长度永远不会超过图中的顶点数，但我不确定这是否被视为常数时间。不管数据量多少，每个list都会有length <= V，所以遍历有明确的上界。
这与 O(1) 相同，还是时间复杂度不同？如果不同，我不确定如何使用 ArrayList 来创建此结构。
您描述的不是 O(1)，而是 O(V)，因为在最坏的情况下，一个顶点可能会连接到所有其他顶点，而 ArrayList 的长度将是 V-1。如果你想要 O(1)，你应该使用 HashSet 而不是 ArrayList。此外，您不需要边 class，您可以简单地存储连接的顶点。
假设顶点 1 连接到 2、4 和 5，那么在数组中的位置 1 处，您将有一个 HashSet (2, 4, 5)。现在，如果您必须检查边 (1, 4) 是否存在，您将转到数组的索引 1（如您所述），然后调用 array[1].contains(4)，这是一个 O(1) 操作。