[알고리즘]정렬의 하한

알고리즘에서 하한이란, 해당 알고리즘이 도달할 수 있는 최대 성능 이자 한계를 말합니다. 즉 해당 알고리즘을 계속 연구해서 성능을 개선한다고 해도, 하한보다 성능이 좋아질수는 없습니다. 정렬의 하한에 대해 알아봅시다. 일단 정렬은 크게 비교정렬Comparison Sort과 비비교정렬Non-comparison Sort 2가지로 분류가 가능합니다. 비교 정렬이란, 사용자가 정의한 조건에 따라 값을 비교하면서 하는 정렬을 의미합니다. 따라서 데이터에 의존적이지 않고 정렬이 가능합니다. 앞에서 배웠던 삽입정렬,합병정렬,힙정렬이 이에 해당 됩니다. 비비교정렬이란, 데이터에 의존하는 정렬을 말합니다. 데이터에 의존하기 때문에 적용할 수 있는 범위가 제한됩니다. 앞에서 배웠던 계수정렬이 이에 해당 됩니다. 비비교정렬의 경우 데이터에 의존하므로 하한 자체가 의미가 없습니다. 비교정렬의 경우 하한의 경우는 아래와 같은 방식으로 유추할수 있습니다. 데이터 3개를 정렬시키는 과정을 생각해 봅시다. 각각...

원문링크 : [알고리즘]정렬의 하한