众所周知,路径压缩并查集的 find 函数是这么写的:
int find(const int x){return x==fa[x]?x:fa[x]=find(fa[x]);}
不结合按秩合并的时间复杂度是 O(nlogn)。
以下是我同学 @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) 的。
求问这种路径压缩的方式的正确时间复杂度是多少,如果不是正确的时间复杂度,是否存在一种构造方式可以卡掉它。