Daily Archives: April 27, 2021

Union Find complexity

space complexity O(n),

time complexity for both union and find O(\alpha (n)), in practice O(\alpha (n)) 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 \mathrm {O} \left(n\right)}。

时间复杂度[编辑]

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