Complexity of union-find with path-compression, without rank - Computer Science Stack Exchange
여기 보니까 nlogn 만큼 더걸리는것 같은데
랭크 안쓰면 시간초과 걸리는 문제도 있나?
[일반] 유니온 파인드 경로압축만 쓰면 터지는 문제 있음?
익명(211.185)
2024-01-04 17:38
추천 0
댓글 6
다른 게시글
-
백준 대회 참가가 재밌네 [4][일반] 익명(112.214) | 24.01.04추천 1
-
아레나 파티 한자리 빌 예정 [5][일반] 익명(61.40) | 24.01.04추천 1
-
매일 풀었더니 씹덕 배경도 주네 ㄷㄷ [4][일반] 익명(210.94) | 24.01.04추천 25
-
솔브닥 아레나 레이팅 변화 그래프로 그려주면 좋겠다 [1][일반] 노는게제일..(aig0016) | 24.01.04추천 2
-
블로그가 개병신들 많음 [6][일반] 익명(223.62) | 24.01.04추천 11
-
계산문제를 풀어야 꺼지는 알람 있잖아 [8][일반] 익명(218.145) | 24.01.04추천 5
-
백준 행성 터널 질문.. [5][일반] 익명(211.36) | 24.01.04추천 0
-
자바로 백준 하다가 질문할 것이 있어 글을 쓴다.. [11][질문] 누비맨(221.152) | 24.01.04추천 0
-
나만 dp가 제일 어려운 것 같냐.... [6][일반] 익명(119.193) | 24.01.04추천 1
-
바킹독에 나오는 알고리즘들 다 기본적으로 알고 있어야하는 알고리즘들이냐? [4][일반] 익명(112.214) | 24.01.04추천 0
못봤음
O(n)이 정해인 문제에 O(nlogn) 자르는게 쉬운일도 아닐꺼고...
유파 undo할라면 path-compression의 amortized복잡도가 오히려 방해되서 rank만 쓴다고 함
보통 랭크 넣어서 하면 더 느리던데
https://cologne.tistory.com/66