我只是希望确认下面算法的时间复杂度。
编辑:在接下来的内容中,我们不假设使用最优数据结构。但是,可以自由提出使用这些结构的解决方案(清楚地说明使用了哪些数据结构以及它们对复杂度的有益影响)。
编辑:在接下来的内容中,我们不假设使用最优数据结构。但是,可以自由提出使用这些结构的解决方案(清楚地说明使用了哪些数据结构以及它们对复杂度的有益影响)。
注: 以下内容中,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)。
p
的实现有什么假设吗?例如,它可能是一个max-heap,还是只是一个数组? - conditionalMethod