能否称Kruskal算法的时间复杂度为Θ(mlogn)而非O(mlogn)？其是否存在下界？

1. 将Kruskal算法的时间复杂度表述为Θ(mlogn)而非O(mlogn)是否合理？ #

在连通图（边数m≥n-1，n为顶点数）的典型场景下，这个表述是合理的：

• Kruskal算法最耗时的步骤是对边排序，基于比较的排序时间复杂度为Θ(mlogm)。当m≥n-1时，logm和logn的量级相同（logm=Θ(logn)），因此Θ(mlogm)等价于Θ(mlogn)。
• 后续的并查集操作耗时为O(mα(n))，其中α(n)是阿克曼函数的反函数，增长速度远慢于logn，不会影响整体的时间复杂度量级。
• 只有当图是极端稀疏的非连通图（m远小于n）时，这个表述才不准确，但这类场景并非算法复杂度讨论的主流情况。如果没有特殊说明，默认针对连通图的话，Θ(mlogn)是严谨的紧界表述。

2. Kruskal算法是否存在时间复杂度下界？ #

在基于比较的计算模型下，Kruskal算法存在明确的时间复杂度下界：

• 算法必须对边进行排序，而基于比较的排序问题的时间复杂度下界是Ω(mlogm)。当m≥n-1时，mlogm的量级不低于mlogn（mlogm=Ω(mlogn)），因此Kruskal算法的时间复杂度下界为Ω(mlogn)。
• 非比较类排序（如基数排序）虽然能突破Ω(mlogm)的下界，但这类排序仅适用于边权有特定结构的场景（比如边权是范围有限的整数），不具备通用性。因此主流讨论中，Kruskal的时间复杂度下界就是Ω(mlogn)，这也解释了为什么常见表述都用O(mlogn)——因为上界和下界量级相同，O(mlogn)既是上界，也可以作为紧界的简化表述。

内容的提问来源于stack exchange，提问作者tonythestark