考虑一个具有n个顶点和m条边的连通无向图，使用普里姆算法构造最小生成树的时间复杂度主要取决于什么？

答案解析

普里姆算法的时间复杂度主要取决于如何实现最小权值边的查找。如果使用邻接矩阵存储图，时间复杂度为O(n^2)，主要取决于顶点数量n。如果使用邻接表和优先队列（如二叉堆）来优化查找过程，时间复杂度可以降低到O(m log n)，这时时间复杂度和顶点数量n以及边的数量m都有关系。因此，选项C正确，它涵盖了不同实现方式下的时间复杂度依赖因素。
正确答案：C
随机推荐

以下哪个事件标志着帝国主义列强对中国的侵略进一步加深？

在Java程序中，若存在以下代码片段 `final int NUMBER = 10; String s1 = "abc"; String s2 = new String("abc");`，关于常量和字符串的说法，下列描述正确的是：

Which of the following verbs best describes a sudden, brief shock caused by an unexpected event?

某连续随机变量X的概率密度函数为f(x)，已知在区间[2, 4]上，f(x) = 0.25。现在我们定义一个新的随机变量Y = 2X，那么新变量Y的概率密度函数在区间[4,8]上的值（高度）为多少？

Natasha如何说服George接受中国的某些习惯？
开始刷题