以下算法的时间复杂度是多少？
Ant*_*ine 6 algorithm graph time-complexity
我只想确认以下算法的时间复杂度。
编辑：在下面，我们不假定正在使用最佳数据结构。但是，可以随意提出使用此类结构的解决方案（清楚地提到使用了什么数据结构以及它们对复杂性有何有益影响）。
表示法：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）。
有一种算法，(1) 可以被识别为算法 1 的实现，并且 (2) 在时间 O(|E| + |V|) 中运行。
首先，让我们考虑算法1的本质。直到图为空为止，执行以下操作：记录优先级最低的节点的优先级作为该节点的核心编号，并删除该节点。节点的优先级动态定义为（1）其在残差图中的度数和（2）其已删除邻居的核心数的最大值。观察到节点的优先级永远不会增加，因为它的度数永远不会增加，并且优先级较高的邻居不会首先被删除。此外，在每次外循环迭代中，优先级总是恰好减少 1。
数据结构支持足以实现 O(|E| + |V|) 时间很好地分为
从初始图开始（初始化时间 O(|E| + |V|)）的图，支持
- 删除一个节点（O（度+ 1），所有节点的总和为O（|E| + |V|）），
- 获取节点的残差度（O(1)）。
一个优先级队列，从初始度数（初始化时间 O(|V|)）开始，支持
- 弹出最小优先级元素（O(1) 摊销），
- 将元素的优先级降低一 (O(1))，且永远不会小于零。
合适的图实现使用双向链接的邻接表。每条无向边都有两个对应的列表节点，除了源自同一顶点的前一个/后一个节点之外，它们还相互链接。度数可以存储在哈希表中。事实证明我们只需要残差度来实现这个算法，所以不用费心存储残差图。
由于优先级是 0 到 |V| 之间的数字 - 1，桶队列工作得非常好。此实现由双向链表的 |V| 元素向量组成，其中索引 p 处的列表包含优先级 p 的元素。我们还跟踪队列中元素的最小优先级的下限。为了找到最小优先级元素，我们从该边界开始按顺序检查列表。在最坏的情况下，这会花费 O(|V|)，但如果我们在算法增加界限时记入该算法，并在界限减少时借记该算法，我们就得到了一个摊销方案，可以抵消此扫描的可变成本。