removeVertex时间复杂度：为何是O(E)而非O(E1*E2)？

我的理解 #

我认为removeVertex的时间复杂度应为O(E1*E2)，其中：

• E1代表待删除顶点（记为V）的边数
• E2代表E1中某条边对应的顶点（邻接表中的顶点）的边数

遍历E1所有元素的时间复杂度为O(E1)，调用removeEdge对E1中每个元素的时间复杂度为O(E2)。

疑问 #

1. 请问该表述是否正确？我是否存在理解误区？
2. 若我的理解正确，为何removeVertex的时间复杂度被认为是O(E)（线性时间）而非O(E1*E2)？

代码实现 #

removeEdge(vertex1, vertex2){
   this.adjacencyList[vertex2] = this.adjacencyList[vertex2].filter(v => v !== vertex1)
}

removeVertex(vertex){
   while(this.adjacencyList[vertex].length){
      const adjacentVertex = this.adjacencyList[vertex].pop()
      this.removeEdge(vertex, adjacentVertex)
   }
}

补充说明 #

• 预期时间复杂度：O(E1*E2)
• 公认时间复杂度：O(E)
• 实现细节：使用哈希表作为邻接表

解答（@harold） #

E1*E2 ≤ E（E为总边数），因此最坏情况下时间复杂度应为O(E)。

内容的提问来源于stack exchange，提问作者Kartik Saini