with with

정렬문제를 해결하기 위해 사용할 수 있는 모든 알고리즘의 복잡도의 한계를 알아보자. 즉, 정렬을 Θ(n)에 끝낼 수 있는지 알아보자. (이 것이 불가능하다는 것을 증명) 정렬을 하는 기본적인 방법은 key값을 통한 비교를 이용한 방법을 사용한다. key값의 비교를 사용하는 알고리즘의 각각의 시간 복잡도의 하한선, lower bound를 알아보고, 각각의 정렬 방법의 한계를 알아보자. - Insertion Sort 삽입 정렬은 key값 하나를 지정하고 뒤로가며 비교하는데, 보다 큰 원소를 만나면 모두 앞으로 한 칸씩 말고 본인이 그 자리에 들어가는 식으로 정렬한다. 시간 복잡도는 다음과 같다. Worst case: n(n-1)/2 = Θ(n^2) Average case: (n+4)(n-1)/4 - ln n..