Notice
Recent Posts
«   2021/10   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31
Tags more
관리 메뉴

Complexity of union-find with path-compression, without rank 본문

Problem Solving/분류없음

Complexity of union-find with path-compression, without rank

gumgood 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?

A.

Seidel and Sharir proved in 2005 [1] 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 2020.02.11 2020.01.16 2019.08.30 2019.05.08 2019.04.23