验证prim算法的上界复杂度

Question

我想知道如何证明Prim算法的时间复杂度的上界。我知道Prim算法的时间复杂度是O（| E | log | V |），其中E是边，V是顶点，但它是什么意思的时间复杂度的上限呢？

Answer 1

但是这是什么意思的时间复杂性的上限呢？

你的问题一般是关于任何算法的上限。 上限限制了最差的情况，比如f（x）“远”可以走多远。

功能描述的大O符号通常只提供了函数增长率的上限。算法的上限用于指示上限或最高增长以指示上限或最高增长率。

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

因此，使用图的二进制堆和邻接关系并按重量排序边，总时间复杂度为O(|E| log |V|)。因此，f(x) = O(|E| log |V|)。

当用Big-O符号表示时，它被限制在该函数下面。