证明 prim 算法的上限复杂度

Question

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

Answer 1

但是时间复杂度的上界是什么意思呢?

你的问题一般是关于任何算法的上界。上限限制了最坏的情况，比如f(x)可以向上走多远。

用大0符号描述函数通常只提供函数增长率的上界。算法的上界用于表示算法的上增长率或最高增长率。

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

因此，对图使用二叉堆和邻接，并对边进行权值排序，总时间复杂度为O(|E| log |V|)。

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

当用大0表示法表示时，