路径压缩并查集 find 函数的复杂度
  • 板块学术版
  • 楼主cjh20090318
  • 当前回复13
  • 已保存回复13
  • 发布时间2025/2/6 16:49
  • 上次更新2025/2/6 20:18:12
查看原帖
路径压缩并查集 find 函数的复杂度
577880
cjh20090318楼主2025/2/6 16:49

众所周知,路径压缩并查集的 find 函数是这么写的:

int find(const int x){return x==fa[x]?x:fa[x]=find(fa[x]);}

不结合按秩合并的时间复杂度是 O(nlogn)O(n \log n)

以下是我同学 @Cczzyy20150005 使用的并查集 find 函数:

int getf(int x){while(F[x]^x)x=F[x]=F[F[x]]=F[F[F[x]]]=F[F[F[F[x]]]];return x;}

这个 find 函数会把路径上每四个点路径压缩到一个点上,但是并不会压缩到同一个根节点上。

在不结合按秩合并的情况下,他本人感性理解给出的时间复杂度是 O(nlog4n)O(n \log_4 n) 的。

求问这种路径压缩的方式的正确时间复杂度是多少,如果不是正确的时间复杂度,是否存在一种构造方式可以卡掉它。

2025/2/6 16:49
加载中...