含最近邻查找与剪枝步骤的层次算法时间复杂度咨询

先统一约定分析用到的基础变量：

• 输入图的总节点数记为n
• 输入图的总边数记为m
• 拉普拉斯矩阵的Moore-Penrose逆矩阵如果未预计算，单独统计其计算开销

1. 最近邻获取步骤复杂度 #

• 单轮邻居遍历开销：每个节点仅遍历自身直接邻居计算距离，单节点遍历量等于自身节点度，全图所有节点完成一轮邻居遍历的总开销为所有节点度之和，也就是O(m)（无向图节点度总和为边数的2倍，常数项不影响复杂度统计）。距离公式中用到的节点总度、拉普拉斯伪逆对应元素如果提前预存，单次距离计算的开销为O(1)，不会额外抬升这部分的复杂度。
• 节点链构建开销：最近邻链从任意节点出发逐次找最近邻延伸，直到找到一对互为最近邻的节点（即描述中提到的两个簇代表节点）就终止当前链的构建，整个过程每个节点最多被访问1次，不会出现重复遍历，总开销为O(n)。
• 额外预计算开销：如果算法运行前没有提前计算拉普拉斯矩阵的Moore-Penrose逆矩阵，这部分的通用计算开销为O(n³)，是整个步骤的开销瓶颈。

2. 节点剪枝步骤复杂度 #

• 深度计算开销：每个簇生成后，计算簇内节点到两个代表节点的深度，不管用BFS还是DFS遍历，单簇的遍历开销等于簇内节点数加簇内边数。所有簇的遍历过程累加后恰好覆盖全图所有节点和边，总开销为O(m + n)。
• 剪枝判断开销：每个节点仅需要做1次阈值比较，符合条件就划分为单成员簇，单节点判断开销为O(1)，总开销为O(n)，占比极低可以忽略。

整体复杂度结论 #

未预计算拉普拉斯矩阵Moore-Penrose逆矩阵的场景下，算法整体复杂度由矩阵伪逆计算主导，为O(n³)；
提前预计算好伪逆矩阵的场景下，算法运行时的整体复杂度为线性于图规模的O(m + n)，在稀疏图（边数m和节点数n为同量级）场景下等价于O(n)，执行效率很高。

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