비교정렬 시간 성능의 하한(lower bound): O(nlogn)

안녕하세욥! 오늘은 비교 기반의 정렬 알고리즘(Comparison-based Sorting) 시간 성능의 하한(lower bound)에 대해 알아보겠습니다!!

 

비교 기반의 정렬 알고리즘(Comparison-based Sorting)에는 여러 종류가 있는데욥! 

• 버블 정렬 (Bubble Sort): 인접한 두 요소를 비교하며 정렬
• 선택 정렬 (Selection Sort): 최솟값 또는 최댓값을 찾아가며 정렬
• 삽입 정렬 (Insertion Sort): 정렬된 부분과 비교하며 새 요소를 삽입
• 합병 정렬 (Merge Sort): 배열을 분할한 후 병합하면서 정렬
• 퀵 정렬 (Quick Sort): 피벗을 기준으로 요소를 나눈 후 재귀적으로 정렬
• 힙 정렬 (Heap Sort): 최대 힙, 최소 힙을 이용하여 정렬

정렬 알고리즘	최선 시간 복잡도	최악 시간 복잡도	평균 시간 복잡도
버블 정렬	O(n)	O(n²)	O(n²)
선택 정렬	O(n²)	O(n²)	O(n²)
삽입 정렬	O(n)	O(n²)	O(n²)
합병 정렬	O(nlogn)	O(nlogn)	O(nlogn)
퀵 정렬	O(nlogn)	O(n²)	O(nlogn)
힙 정렬	O(nlogn)	O(nlogn)	O(nlogn)

 

이렇듯 다양한 비교기반 정렬 알고리즘이 있는데요 비교기반 정렬 알고리즘의 최악(worst case)의 시간복잡도는 아무리 빨라도 O(nlogn)으로 나타나는 것을 확인할 수 있는데욥!

 

그렇다면 비교기반 정렬 알고리즘에서 더 효율이 좋은,  최악(worst case)이 O(nlogn)보다 빠른 알고리즘은 없을까요?

 

결론적으로 말하자면 없습니다!!

즉, 비교기반 정렬 알고리즘의 최악(worst case)은 아무리 빨라도O(nlogn)인 것을 확인할 수 있습니다! 더 이상의 개선 여지가 없다는 것이죠(optimality)

 

이를 증명해 보겠습니다

Decsion Tree를 이용하여 비교 횟수(h)와 정렬된 결과의 수(L)를 비교하여 결과를 도출할 수 있습니다!

 

n = 정렬할 데이터의 개수

h = 정렬시 비교 횟수

L = 서로다른 정렬된 결과의 수

 

조금 더 디테일한 증명을 하면

 

결론적으로 비교 정렬 알고리즘에서 최악의 시간복잡도 O(nlogn)보다 빠른 알고리즘은 없는 것을 확인할 수 있습니다!

더 빠른 알고리즘을 만들어보려고 머리꽁꽁 싸매고 고민할 필요 없겠죠?!? ㅎㅎ 

 

# reference

컴퓨터 알고리즘. (2006). 대한민국: 도서출판 홍릉(홍릉과학출판사).

Baase, S., Van Gelder, A. (1999). Computer Algorithms: Introduction to Design and Analysis, 3rd Edition. 인도: Addison-Wesley.