在图的邻接矩阵实现中查找两个给定顶点相邻的最坏情况运行时间是多少
在图的邻接矩阵实现中查找两个给定顶点相邻的最坏情况运行时间是多少？这不是 O(1) 因为我知道矩阵中这些顶点的索引，以便我可以在恒定时间内选择值吗？我在书上读到它是O(n^2)。请有人解释一下如何实现这一措施。
谢谢
What is the worst-case running time for finding two given vertices are adjacent in Adjacency matrix implmentation of a graph? Is that not O(1) as I know the indices of those vertices in the matrix so that I can pick the value in constant time? I read it as O(n^2) in a book. Someone please explain it how to get to this measure.
Thanks
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
邻接矩阵占用 O(n^2) 内存，这可能是您感到困惑的地方。但是，给定两个顶点的查找是 O(1)，这就是邻接矩阵的优点。
An adjacency matrix occupies O(n^2) memory, which may be where you're confused. But yes lookup given two vertices is O(1), that's the advantage of an adjacency matrix.
是的。由于您所陈述的原因，它是 O(1) 。
yes. it is O(1) for the reasons stated by you.