시간복잡도 검색 결과
2 개의 검색 결과가 있습니다.
알고리즘

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
알고리즘

Red-Black Tree 속성/검색/삽입/삭제

이진트리 중 Binary Search Tree인 경우에는 한쪽에만 노드들이 치우쳐 있어 균형잡힌 트리가 만들어지지 않을 수 있다. 그렇다면 탐색을 하기 위한 시간이 늘어나게 되는 단점이 있는데, 이를 보완하여 균형잡힌 트리를 만들고자 만들어진 자료구조가 Red-Black Tree라는 것이다. Red-Black Tree는 각 노드의 색깔을 red, black 중에 선택하여, 주어진 조건을 만족시켰을 때 성립하는 Tree이다. Red-Black Tree의 성립조건은 다음과 같다. 루트 노드는 언제나 Black이다. Leaf 노드 (말단 노드) 또한 언제나 Black이다. 만약 노드가 Red라면, 그 노드의 자식들은 언제나 Black이다. 즉, red node가 연속으로 올 수 없다. 루트에서 말단 노드까지의..

2021. 4. 17. 13:55