블로그 이사 중입니다 >> gumgood.github.io

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

원문 : https://cs.stackexchange.com/questions/48649

 

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))\).

 

~ (작성 중)

 

0 Comments
댓글쓰기 폼