我的算法课正在讨论 Prim 算法作为一种寻找加权图的最小生成树的方法。我们的教授让我们试着想一个图的例子,Prim 的算法需要 N^2 时间来解决(N = 顶点数)。类没有人能凭空想到一个,所以我问你。我很确定 Prim 算法 = O(N^2),所以这将是该算法的最坏情况。
Prim 算法需要 N^2 时间求解的图的一个很好的例子是什么?
最佳答案
如果我正确理解你的问题,那么这个例子是微不足道的。
如果图是完整的,则有 O(N^2)
条边,因此仅读取图就是 O(N^2)
。
关于algorithm - Prim 算法的最坏情况图,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/43529017/