log*n 검색 결과
1 개의 검색 결과가 있습니다.
알고리즘

Union-Find의 시간복잡도

Union-Find를 구현하는 방식에는 두 가지가 있다. 첫 번째는 linked list를 활용하여 구현하는 방식이고, 두 번째 방식은 우리가 일반적으로 알고 있는, Tree를 사용해서 구현하는 방식이다. 각각에 대하여 시간복잡도가 다르기 때문에 두 경우로 나누어서 분석해보겠다. 모든 경우에 대해서 총 m개의 연산 (make, find, union)이 가능하고, make-set의 개수 (=원소의 개수)는 n개라고 가정하에 시간복잡도를 계산해보겠다. 1. Linked List를 활용하는 경우 : O(m+ nlogn) 이 경우에는 시간복잡도가 O(m +nlogn)이라고 알려져있다. 직관적으로 설명한다면 linked list의 경우 길이가 짧은 linked list를 길이가 긴 linked list에 붙이는 ..

2021. 4. 20. 01:06