space complexity O(n),

time complexity for both union and find , in practice is normally less than 5. So can be treated as O(1) constant time.

https://zh.wikipedia.org/wiki/%E5%B9%B6%E6%9F%A5%E9%9B%86

### 空间复杂度[编辑]

容易看出，不交集森林的空间复杂度是{\displaystyle \mathrm {O} \left(n\right)}。

### 时间复杂度[编辑]

对于同时使用路径压缩和按秩合并优化的不交集森林，每个查询和合并操作的平均时间复杂度仅为{\displaystyle O(\alpha (n))}，{\displaystyle \alpha (n)}是反阿克曼函数。由于阿克曼函数{\displaystyle A}增加极度迅速，所以{\displaystyle \alpha (n)}增长极度缓慢，对于任何在实践中有意义的元素数目{\displaystyle n}，{\displaystyle \alpha (n)}均小于5，因此，也可以粗略地认为，并查集的操作有常数的时间复杂度。