8

我正在使用邻接矩阵，优先级队列是数据结构。

根据我的计算，复杂度是V^3 log V：

  • While循环：V
  • 检查相邻顶点：V
  • 如果条目已经存在，则检查队列并更新：V log v

但是，我到处都读到复杂性是V^2

请解释。

4

2 回答 2

4

如果您使用斐波那契堆，则提取最小值是O(lg V)摊销成本，更新其中的条目是O(1)摊销的。

如果我们使用这个伪代码

while priorityQueue not empty
    u = priorityQueue.exractMin()
    for each v in u.adjacencies
        if priorityQueue.contains(v) and needsWeightReduction(u, v)
            priorityQueue.updateKeyWeight(u, v)

假设实现对于priorityQueue.contains(v)和都有恒定的时间needsWeightReduction(u, v)。

需要注意的是，您可以稍微更紧地检查邻接关系。虽然外部循环运行V时间，并且检查任何单个节点的邻接是最糟糕的V操作，但您可以使用聚合分析来意识到您永远不会检查超过E邻接（因为只有 E 边）。并且E <= V^2，所以这是一个稍微好一点的界限。

所以，你有外循环 V 次，内循环 E 次。提取最小运行V时间，并更新堆运行E时间中的条目。

  V*lgV + E*1
= O(V lgV + E)

同样，因为 E <= V^2您可以使用这个事实来替代并得到

  O(V lgV + V^2)
= O(V^2)

但在考虑稀疏图时，这是一个更宽松的界限（尽管是正确的）。

于 2012-11-26T00:13:30.163 回答
1

使用基于最小堆的优先级队列，时间复杂度为 O(ElogV)。

正如您所说，外部 while 循环是 O(V)，因为它遍历每个顶点，因为每个顶点都需要添加到 MST 一次。

对于 while 循环中考虑的每个顶点，需要执行以下两个步骤：

  1. 选择下一条边添加到 MST。根据基于最小堆的优先级队列的属性，根元素总是最小的元素。因此，选择下一个边，即成本最低的边，将是对根元素的 O(1) 提取。提取后剩余的值需要以维持优先级队列的方式移动。由于队列表示平衡二叉树，因此在最坏的情况下，这种偏移可能会在 O(logV) 内发生。

  2. 更新优先级队列。与新顶点相关的边可能需要在队列中更新它们的成本，因为我们现在将考虑与新添加的顶点及其邻居之间的边相关的成本（但是，如果它们通过一条边与先前添加的顶点相邻）成本低于新引入的边缘，成本不会更新，因为我们正在寻找最低成本）。这也是 O(logV)，因为在最坏的情况下，一个顶点需要在代表队列的平衡二叉树的整个长度上移动。

步骤 1 发生 V 次，因为它在 while 循环中发生一次，所以总共是 O(VlogV)，步骤 2 在最坏的情况下发生 E 次，其中每条边都连接到当前顶点，因此它们都需要更新，这意味着它是 O(ElogV) 总数。设置是 O(E)，因为它需要将优先级队列中的每个边成本初始化为无穷大。

使用基于最小堆的优先级队列的总时间复杂度 = O(E + VlogV + ElogV) = O(ElogV)

当您阅读复杂度为 O(V^2) 时，您可能正在查看不使用堆的实现。在这种情况下，外部 while 循环仍然是 O(V)。瓶颈在于选择要添加到 MST 的下一个顶点的步骤，即 O(V)，因为您需要检查与每个相邻节点相关的成本以找到最低成本，这在最坏的情况下意味着检查所有其他节点。因此复杂度为 O(V*V) = O(V^2)。

此外，在非常密集的图中，O(ElogV) 变为 O(V^2)，因为在任何图中，最多可以有 E = V^2 个总边。

于 2018-11-30T23:31:57.313 回答