백준 풀이

알고리즘

---

Time complexity

---

Comparison Sorting Algorithm

비교를 통해 정렬하는 알고리즘의 통칭

버블정렬, 선택정렬, 삽입정렬, 병합 정렬, 퀵 정렬 등

한계점

비교를 통한 정렬을 구현하는 과정에서 시간복잡도는 O(nlogn)을 넘을 수 없다는 점이 증명되었다.

의사 결정 트리를 활용해보자.

https://mathcenter.oxford.emory.edu/site/cs171/decisionTree/

우리가 정렬을 구현할 때 모든 원소를 하나하나 비교하게 된다면 N!의 시간을 소요하게 된다.

의사 결정 트리에서 높이=h(의사결정 횟수) 라고 생각하면 리프 노드의 개수는 최대 2^h개 이다.

즉 최소한 2^h >= N!이 만족해야만 모든 경우에서의 정렬 결과를 도출해낼 수 있다고 생각할 수 있다.

양변에 밑이 2인 로그를 취하면 h >= logN!로 표현할 수 있으며
logN! 은 스털링 근사를 통해 nlogn으로 표현될 수 있다.

즉 비교를 통한 정렬 알고리즘은 최소한 nlogn회 의사결정을 통해 수행되어야 한다는 뜻이므로 최악의 경우 걸리는 시간을 나타내는 빅-오 표기법으로는 O(nlogn) 보다 빠를 수 없다는 것이다.