Union Find complexity

By | April 27, 2021
0 Comment
Share the joy
  •  
  •  
  •  
  •  
  •  
  •  

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，因此，也可以粗略地认为，并查集的操作有常数的时间复杂度。