블로그 이사 중입니다 >> gumgood.github.io
Complexity of union-find with path-compression, without rank 본문
Complexity of union-find with path-compression, without rankgumgood 2020. 2. 11. 11:27
Q. Complexity of union-find with path-compression, without rank
Wikipeda says union by rank without path compression gives an amortized time complexity of \(O(\log n)\), and that both union by rank and path compression gives ans amortized time complexity of \(O(\alpha(n))\) (where \(\alpha\) is the inverse of Ackerman funcion). However, it does not mention the running time of path compression without union rank, which is what I usually implement myself.
What's the amortized time complexity of union-find the path-compression optimization, but without the union by rank optimization?
Seidel and Sharir proved in 2005  that using path compression with arbitrary linking rounghly on \(m\) operations has a complexity of roughly \(O((m+n)\log(n))\).
~ (작성 중)
'Problem Solving > 분류없음' 카테고리의 다른 글
|Efficient program to print all prime factors of a given number (0)||2020.02.11|
|Complexity of union-find with path-compression, without rank (0)||2020.02.11|
|[Upsolving] NWERC 2017 (0)||2020.01.16|
|Mapping a permutation to an integer (0)||2019.08.30|
|Algorithm Gym :: Data structures (0)||2019.05.08|
|Segment Tree (+ Lazy Propagation) 코드 최적화 (2)||2019.04.23|