为什么边缘比图理论中的顶点少？
通过分析Kruskal的算法，Kruskal的算法显然被认为是e log e e，因为“对于MST存在，E不能小于V，因此假设它占主导地位”，
但是，最简单的树输入将比边缘更大。 。
存在，E不能小于
V
Upon analyzing Kruskal's Algorithm, Kruskal's Algorithm is apparently considered to be E log E because "for an MST to exist, E can't be smaller than V so assume it dominates"
However, the simplest tree input would have more vertices than edges...
snippet of the lecture slide I was looking at
Can someone tell me why "for an MST to exist, E can't be smaller than V so assume it dominates"
hence run time is ElogE not ElogE + V
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
在这里，“较小”一词应根据计算复杂性或大o来理解。
对于MST，E必须大于或等于V -1。虽然您是正确的，但这意味着E可能小于V，但它将其放在相同的复杂性类别中。
对于具有MST的图形，E可以是O（V）或O（V^2），或者之间的任何内容。
The term "smaller" here should be understood in terms of computational complexity, or big-O.
For an MST to exist, E must be greater than or equal to V - 1. While you are right that this means E can be less than V, it puts it in the same complexity class.
For graphs that have an MST, E can be O(V), or O(V^2), or anything in between.