以下算法的时间复杂度是什么？

Question

我只是希望确认下面算法的时间复杂度。

编辑：在接下来的内容中，我们不假设使用最优数据结构。但是，可以自由提出使用这些结构的解决方案（清楚地说明使用了哪些数据结构以及它们对复杂度的有益影响）。

注: 以下内容中，n=|V|，m=|E|，avg_neigh表示图中任何给定节点的平均邻居数。

假设: 图是无权、无向的，并且我们已经将其邻接列表表示加载到内存中（一个包含每个顶点邻居的列表的列表）。

目前为止我们有：

第1行: 计算度数是O(n)，因为它只涉及获取邻接列表表示中每个子列表的长度，即执行n个O(1)操作。

第3行: 找到最小值需要检查所有值，这是O(n)。由于这是嵌套在遍历所有节点一次的while循环中的，因此它变成了O(n^2)。

第6-7行: 删除顶点v是O(avg_neigh^2)，因为我们从邻接列表表示中知道v的邻居，并且从每个邻居的子列表中删除v是O(avg_neigh)。第6-7行嵌套在while循环中，因此它变成了O(n * avg_neigh^2)。

第9行: 它是O(1)，因为它只涉及获取一个列表的长度。它嵌套在for循环和while循环中，因此变成了O(n * avg_neigh)。 总结: 总复杂度为O(n) + O(n^2) + O(n * avg_neigh^2) + O(n * avg_neigh) = O(n^2)。 注1: 如果每个子列表的长度不可用（例如，因为邻接表无法加载到内存中），则在第1行计算度数的复杂度为O(n * avg_neigh)，因为每个列表平均具有avg_neigh个元素，并且有n个子列表。而在第9行，总复杂度变为O(n * avg_neigh^2)。 注2: 如果图形带权，则可以将边权重存储在邻接表表示中。但是，在第1行获取度数需要对每个子列表求和，如果邻接表加载到RAM中，则现在为O(n * avg_neigh)，否则为O(n * avg_neigh^2)。同样，第9行变为O(n * avg_neigh^2)或O(n * avg_neigh^3)。

- Antoine

---

p 的实现有什么假设吗？例如，它可能是一个max-heap，还是只是一个数组？ - conditionalMethod

为什么在摘要中你得出结论：这些类元素的总和是O(n^2)？在最坏情况下，avg_neigh不是接近于n吗？因此，O(n*avg_neigh^2)类与O(n^3)类相同，对吗？ - conditionalMethod

你提出了很好的观点，谢谢。我原本假设p是一个简单的字典，但实际上其他一些数据结构可能更有效率。在最坏情况下，我完全同意我们接近O(n^3)。 - Antoine

正如@conditionalMethod所指出的那样，运行时间取决于选择哪些数据结构。仔细的选择可以得到一个O(|V| + |E|)时间复杂度的算法。 - David Eisenstat

@DavidEisenstat 我已经编辑了我的问题以反映这一点。您能否花时间编写一个答案，解释一下您如何得出O（|V| + |E|）？ - Antoine

Answer 1

有一种算法，它（1）可以识别为算法1的实现，并且（2）运行时间为O（|E| + |V|）。

首先，让我们考虑Algorithm 1的本质。直到图形为空为止，执行以下操作：将具有最低优先级的节点的优先级记录为该节点的核心数，并删除该节点。节点的优先级被动态定义为在剩余图中其度数和已删除邻居的核心数之间的最大值。请注意，节点的优先级从不增加，因为其度数从不增加，并且更高优先级的邻居不会首先被删除。此外，每个外循环迭代中的优先级都恰好降低一个。

足以实现O（|E| + |V|）时间的数据结构可分为以下部分：

1. 从初始图开始（初始化时间为O（|E| + |V|）），支持以下功能的图形： - 删除节点（O（度数+1），总和为O（|E| + |V|）） - 获取节点的残余度数（O（1））。 2. 从初始度数开始（初始化时间为O（|V|）），支持以下功能的优先队列： - 弹出最小优先元素（摊销成本为O（1）） - 减少元素的优先级1（O（1）），但不小于零。

适当的图实现使用双向链接邻接列表。每个无向边具有两个对应的列表节点，它们除了来自同一顶点的前一个/下一个节点之外，还互相链接。度可以存储在哈希表中。事实证明我们只需要残余度数来实现此算法，因此不必担心存储残余图。

由于优先级是介于0和|V|-1之间的数字，因此桶队列非常适合。该实现包括一个|V|元素的双向链接列表向量，在索引p处的列表包含优先级为p的元素。我们还跟踪队列中元素最小优先级的下限。要查找最小优先级元素，我们从该下限开始按顺序检查列表。在最坏情况下，这将花费O（|V|），但如果我们每当算法增加界限时就信用它，每当界限减小时就借记它，我们将获得一种摊销方案，以抵消此扫描的可变成本。

- David Eisenstat

Answer 2

如果选择一种数据结构来支持高效查找最小值和高效删除（例如自平衡二叉树或最小堆），那么可以在O（|E|log |V|）的时间内完成。

第一行中创建数据结构的时间复杂度为O(|V|)或O(|V|log|V|)。

循环正好遍历每个节点v在V中一次。

对于每个这样的节点，需要查看最小值，并调整数据结构，以便在下一次迭代中高效地查看下一个最小值。对此需要O(log|V|)（否则，可以在o(nlogn)中进行堆排序 - 注意此处小o符号）。

使用高效的集合实现（例如哈希表），可以在O(|neighbors|)内获得neighbors，并从V和E中删除项目。由于每个边和节点都恰好选择一次此步骤，因此它在所有迭代中总和为O(|V| + |E|)。

再次循环neighbors，由于每条边在此处仅计算一次，因此总和为O(|E|)。

然而，在此循环中，您可能需要更新p，而这样的更新成本为O(log|V|)，因此总和为O(|E|log|V|)。

这句话的意思是：“这个算法的时间复杂度为 O(|V|log|V| + |E|log|V|)。假设图不是非常稀疏（即 |E| 是 Omega(|V|)），则时间复杂度为 O(|E|log|V|)。”

- amit

---

能否解释一下给我点踩的原因？ - Antoine