我只想确认下面算法的时间复杂度。
编辑：在下面的内容中，我们不假设使用了最佳的数据结构。然而，可以自由地提出使用这些结构的解决方案（清楚地提到使用什么数据结构以及它们对复杂性有什么有益的影响）。
表示法：n=v，m=e，avg_u neigh表示图中任意给定节点的平均邻居数。
假设：图是未加权、无向的，并且我们在内存中加载了它的邻接列表表示（包含每个顶点的邻居的列表列表）。
以下是我们目前掌握的情况：
第1行：计算度数是o（n），因为它只需要获取邻接列表表示中每个子列表的长度，即执行no（1）操作。
第3行：找到最低值需要检查所有值，即o（n）。由于这是嵌套在while循环中的，while循环访问所有节点一次，因此它变为o（n^2）。
第6-7行：删除顶点v是o（avg_neigh^2），因为我们知道从邻接列表表示中删除v的邻居，从每个邻居的子列表中删除v是o（avg_neigh）。第6-7行嵌套在while循环中，因此它变为o（n*avg\u neigh^2）。
第9行：它是o（1），因为它只需要获取一个列表的长度。它嵌套在for循环和while循环中，因此成为o（n*avg_neigh）。
总复杂度为O（n）+O（n^ 2）+O（n*avgni^ ^ 2）+O（n*avgsi-ney）＝O（n ^ 2）。
注1：如果每个子列表的长度不可用（例如，因为邻接列表无法加载到内存中），则计算第1行中的度数为o（n*avg-neigh），因为每个列表平均具有avg-neigh元素，并且有n个子列表。第9行，总复杂度变为O（n*avgnay^ ^ 2）。
注2：如果图是加权的，我们可以将边权重存储在邻接列表表示中。但是，要获得第1行中的度数，需要对每个子列表求和，如果相邻列表加载到ram中，则现在为o（n*avg-neigh），否则为o（n*avg-neigh^2）。类似地，第9行变为o（n*平均值^2）或o（n*平均值^3）。
最佳答案
有一种算法（1）可识别为算法1和（2）在时间o（e+v）上运行的实现。
首先，让我们考虑算法1的本质。在图为空之前，请执行以下操作：记录优先级最低的节点的优先级作为该节点的核心编号，然后删除该节点。节点的优先级动态地定义为残差图中最大（1）的程度，以及（2）其删除邻居的核心数。请注意，节点的优先级从未增加，因为其阶数从未增加，并且较高优先级的邻居不会首先被删除。而且，在每个外循环迭代中，优先级总是减少恰好一个。
数据结构支持足以实现o（e+v）的时间分割
从初始图（初始化时间o（e+v）开始支持
删除节点（o（度+1），在所有节点上求和为o（e+v）。
得到节点的剩余度（o（1））。
一种优先级队列，从初始度数（初始化时间o（v）开始，支持
弹出最小优先权要素（O（1）摊销）
将元素的优先级降低一（o（1）），且不小于零。
一个合适的图实现使用双链接邻接列表。每个无向边都有两个对应的列表节点，除了源于同一顶点的上一个/下一个节点之外，这些节点彼此链接。学位可以存储在哈希表中。结果证明，我们只需要残差度来实现这个算法，所以不用存储残差图。
因为优先级是介于0和v-1之间的数字，所以abucket queue工作得非常好。此实现由双链表的v元素向量组成，其中索引p处的列表包含优先级p的元素。我们还跟踪队列中元素的最小优先级的下界。为了找到最小优先级元素，我们从这个绑定开始按顺序检查列表。在最坏的情况下，这个成本是o（v），但是如果我们在算法增加界限时将其记入贷方，在界限减少时将其记入借方，我们就得到了一个抵消此扫描的可变成本的摊销方案。