边权为1~|V|或1~常数W时Kruskal与Prim算法的差异疑问

首先要明确算法复杂度分析语境下两个设定的本质不同：

• 边权上限为常数W：这里的W是和输入规模（图的顶点数|V|、边数|E|）完全解耦的固定值，不管输入的图是只有10个顶点的小图，还是有100万个顶点的超大规模图，W的取值都不会发生变化，所有和W相关的运算开销都可以归为常数项，在计算渐进复杂度时可以被忽略。
• 边权上限为|V|：这里的上限是输入规模的直接函数，会随着输入图的规模增大同步线性增长，相关开销不能归为常数项，必须作为变量纳入复杂度计算。

分开提问的原因 #

两个场景下，两种算法能达到的渐进复杂度量级、适配的优化策略都有明显差异，典型的差异点包括：

1. 排序环节的复杂度差异：以Kruskal算法用到的排序步骤为例：
   • 边权范围1~W时，不管用计数排序还是基数排序，时间复杂度都是O(E)：计数排序的O(E+W)可以直接消去常数W项，基数排序的轮次也因为权值范围固定为常数而归为常数开销。
   • 边权范围1~|V|时，排序环节的复杂度为O(E + V)，如果用基数排序则会额外引入O(log |V|)的轮次开销，对应的权值范围相关项不能被省略。
2. 优先队列/桶结构的开销差异：以Prim算法用到的最小权值查询逻辑为例：
   • 边权范围1~W时，直接用数组桶存储对应权值的节点，每次查询最小权值遍历W个桶的开销是常数，整体查询的摊销时间为O(1)。
   • 边权范围1~|V|时，桶的数量随输入规模增长，必须额外维护当前最小权值的指针才能把查询开销压到摊销O(1)，优化逻辑更复杂，对应的开销项也不能归为常数。

分析思路不同的核心原因 #

• 针对常数W的场景，优化时完全不需要考虑权值上限增长带来的额外开销，所有和W相关的操作都可以视为固定开销，只需要评估和输入规模E、V相关的项即可。
• 针对边权上限为|V|的场景，优化时必须考虑权值上限和输入规模绑定的特性，不能假设权值相关的操作是常数开销，需要把权值范围对应的变量项纳入整体复杂度计算。

注：如果抛开渐近复杂度分析的语境，只看具体小图的实际运行耗时，两个设定确实可能没有明显差异，但算法题的性能优化分析默认都是基于渐近复杂度的框架，所以两个设定的边界非常清晰。

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