사용자 도구

사이트 도구


ps:disjoint_set

Disjoint Set

  • 웬만하면 한글 번역된 이름을 먼저 쓰고 싶었는데, 이거는 사용 빈도가 압도적인 번역이 있는 것도 아니고, 번역된 이름들도 다 마음에 들지 않는다. 서로소 집합, 분리 집합 다 어색하고, 그냥 디스조인트 셋 또는 유니온파인드 셋 이렇게 쓰는게 사용 빈도가 더 많아 보인다..
  • 설명은 위키를 참고하자.
  • find 연산의 amortized 시간 복잡도는
    • naive한 구현으로는 최악의 경우에는 find 연산에 O(n)이 걸린다
    • path compression 이나 union-by-rank/size 중 하나를 구현하면 연산이 O(logn) 수준으로 빨라진다
    • path compression 과 union-by-rank/size 를 모두 구현하면 연산량이 O(α(n))이 되어 상수로 간주할수 있을 정도가 된다.
  • 실제 구현은 path compression 과 union-by-size를 적용해서 구현했다
    • union-by-rank와 union-by-size 어느쪽이든 속도향상을 위해서는 상관 없지만, size를 알고 있는 것이 활용도가 더 높아서 이쪽으로 구현했다.
    • 명시적으로 make_set함수를 제공해서 시작할때 모든 원소들에 대해서 set을 전부 생성하도록 하는 대신에, make없이도 그냥 아이템에 대해서 find연산을 사용하면, 그 아이템에 대해 처음 find가 호출되는 경우 그 아이템에 대한 set을 생성하도록 처리했다.
      • 실용적이고 효율적이다.

활용

토론

댓글을 입력하세요:
L U W B Y
 
ps/disjoint_set.txt · 마지막으로 수정됨: 2021/02/21 15:44 저자 teferi