algorithm - proving upper bound complexity for prim's algorithm

Question

I would like to know how can you prove an upper bound on the time complexity of Prim's algorithm. I know that the time complexity of the Prim's algorithm is O(|E| log |V|),where E is the edge and V is the vertex, but what does it mean by the upper bound on the time complexity?

Answer 1

但是时间复杂度的上限是什么意思？

您的问题通常是关于任何算法的上限。上限限制了最坏的情况，例如 f(x) 可以走多远。

用大 O 表示法对函数的描述通常只提供函数增长率的上限。算法的上限用于指示增长的上限或最高，以指示增长的上限或最高。

这意味着给定算法在给定输入集的情况下不能比这个复杂度更差。

因此，对图使用二进制堆和邻接以及按权重对边进行排序，总时间复杂度为O(|E| log |V|).

因此，f(x) = O(|E| log |V|)。

当用 Big-O 表示法表示时，它在此函数之下。