图算法时间复杂度问询：O(ELgV)结合E∈o(V²/LgV)的小o分析

问题1：f(n)的时间复杂度分析 #

已知f(n) ∈ O(g(n))，且g(n)的某部分属于o(h(n))，无法直接确定f(n)的时间复杂度，核心原因如下：

• 小o记号o(h(n))定义的是函数增长速度严格慢于h(n)，但如果只是g(n)的某个子项满足这个条件，比如g(n) = g₁(n) + g₂(n)，其中g₁(n) ∈ o(h(n))，但g₂(n)的增长速度可能远快于h(n)（比如g₂(n) = Θ(h(n)²)），此时g(n)的主导增长项是g₂(n)，f(n)的复杂度由g₂(n)决定，和h(n)无关。
• 只有当**整个g(n)都属于o(h(n))**时，才能推导出f(n) ∈ o(h(n))：因为f(n) ∈ O(g(n))意味着f(n)被g(n)的常数倍限制，而g(n)严格慢于h(n)，常数倍不影响小o的严格增长关系，因此f(n)也严格慢于h(n)。

问题2：图算法的时间复杂度推导 #

复杂度推导 #

已知算法时间复杂度为O(E lgV)，且E ∈ o(V²/lgV)，根据小o的乘法性质（若a(n) ∈ o(b(n))，且k(n)为正递增函数，则a(n)*k(n) ∈ o(b(n)*k(n))），代入得：

E * lgV ∈ o( (V²/lgV) * lgV ) = o(V²)

由于O(E lgV)中的所有函数都被E lgV的常数倍限制，而常数倍不改变小o的严格增长关系，因此该算法的整体时间复杂度用小o表示为o(V²)。

问题的意义 #

这个问题完全有意义：

• 原复杂度O(E lgV)是针对任意图的通用描述，但在稀疏图场景（如社交网络、随机稀疏图等）中，E ∈ o(V²/lgV)是典型特征，E远小于V²。
• 推导得到的o(V²)比直接用E ≤ V²得到的O(V²)更精确，能更准确地反映算法在稀疏图下的实际性能增长速度，对于对比稀疏图算法效率、优化算法实现都有实际参考价值。

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