merge sort tree (1) 썸네일형 리스트형 168. Merge Sort Tree 이전에 병합 정렬이라는 정렬 방법을 소개한 적이 있다. 이걸 응용해서 자료구조로 써먹는 방법을 알아본다. 머지 소트 트리(Merge Sort Tree)는 병합 정렬 과정을 세그먼트 트리에 저장한 자료 구조이다. 앞서 병합 정렬의 시간복잡도와 공간복잡도가 $\Theta(n \lg n)$이라고 했는데, 정렬 과정에서 생긴 데이터를 버리지 않고 그대로 저장하면 머지 소트 트리를 만들 수 있다. 즉 $\Theta(n \lg n)$의 시간복잡도로 $\Theta(n \lg n)$의 메모리를 사용하는 머지 소트 트리를 만들 수 있다. $$[6, 3, 5, 7, 1, 4, 2]$$ 이 수열로 머지 소트 트리를 만들어 보자. 구간을 분할하는 부분은 별로 중요하지 않기 때문에 합치고 정렬하는 부분만 트리로 만들면 된다. .. 이전 1 다음
