图作为邻接矩阵时间复杂度

Question

我不明白为什么在邻接矩阵中插入一条边需要 O(1) 时间。例如，我们想从顶点 3 到 5 添加一条边，在定向图中我们需要将 graph[2][4] 更改为 1。在定向图中也可以反过来。怎么可能是 O(1)，如果我们至少有一次必须在数组中找到正确的行，那么它已经是 O(|V|)？

Answer 1

在二维数组中，所有操作都被视为 O(1)。

在二维数组中，您不会线性地找到要添加数据的行和列。

这里

  a[i][[j] = k 

是一个 O(1) 操作，因为您可以将数组的位置直接作为索引而不是线性引用。

但是，在 Linkedlist 中，确实必须通过逐行访问所有行/列来查找行/列。