CS/자료구조
[자료구조 및 프로그래밍] 17. 정렬의 최소 시간 복잡도
정렬의 종류별 알고리즘에 대해 정리할 때, 기수 정렬의 시간복잡도는 O(N)이 나왔었다. 그런데 일반적으로 정렬의 시간 복잡도는 O(N log N) 으로 알려져있다. 어떻게 기수 정렬은 O(N) 시간에 정렬을 할 수 있었을까? 그리고 왜 일반적으로 정렬의 시간 복잡도는 O(N log N) 으로 알려져 있는 걸까? 한번 O(n log n) 시간으로 고정되어있는 merge sort 의 comparison 과정을 tree로 표현해보자. a, b, c, d 라는 4개의 데이터에 대해 merge sort 를 수행하면, 반씩 쪼개다가 merge 하는 과정에서 비교를 수행한다. 이때 비교를 통해 정렬을 수행하는 모든 경우의 수를 comparison tree 로 그려보자. 제일 먼저 비교가 일어나는 부분은 a, b 이..
