Computational Complexity Analysis - Sorting problem

정렬문제를 해결하기 위해 사용할 수 있는 모든 알고리즘의 복잡도의 한계를 알아보자.

즉, 정렬을 Θ(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 = Θ(n^2)

 

- Selection sort

선택 정렬은 각 회차에서 제일 작은 값을 key값으로 지정하고,

정렬이 안 된 맨 앞의 원소와 위치를 바꿔가며 정렬한다.

시간 복잡도는 다음과 같다.

• Worst case: Θ(n^2)
• Average case: Θ(n^2)

 

- Exchange sort

Bubble sort와 비슷한 교환 정렬은 정렬되지 않은 곳의 맨 앞을 key값 삼아서, 

그 뒤의 아이템과 비교를 통해 자리를 바꿔나간다.

시간 복잡도는 다음과 같다.

 

• Worst case: Θ(n^2)
• Average case: Θ(n^2)

 

 

위 세 알고리즘은 공통적인 특징이 있다.

바로, 한 번의 비교에서 기껏해야 1개의 정렬되지 않은 쌍이 사라진다는 것이다.

 

한 번의 비교에서 기껏해야 1개의 정렬되지 않은 쌍이 사라지는 알고리즘의 시간 복잡도의 하한선(한계)를 구해보자.

* Worst case

n개의 원소를 정렬해야 한다고 할 때, 각 스탭에서 n-1, n-2, ..., 2, 1번의 교환 작업이 필요할 것이다.

따라서 전체 n(n-1)/2의 교환 작업이 필요하다.

 

* Average case

n개의 원소를 정렬해야 한다고 할 때,

모든 케이스에 대해 정렬되지 않은 쌍의 개수를 구해보자.

모든 케이스를 고려해보면, 평균적으로 [C(n, 2) * n! / 2] / n! 의 교환 작업이 필요하다.

즉, 전체 n(n-1)/4의 교환 작업이 필요하다.

 

그렇기에 한 번의 비교에서 기껏해야 1개의 정렬되지 않은 쌍이 사라지는 알고리즘의 시간 복잡도의

하한선은 n(n-1)/4이고, 이보다 빠르게 정렬하는 방법은 존재하지 않는다.

 

 

참고로 Merge, Quick sort와 같은 알고리즘은 한 번의 비교에서 여러개의 정렬되지 않은 쌍이 사라지는데,

이런 경우에도 비슷한 방법을 적용하면 하한선이 결국에는 Θ(n lg n)으로 귀결된다.

 

 

- Heap sort

<initialize>

 

<insert>

<delete>

heap sort는 heap 구조를 이용해서 정렬하는 방법이다.

heap 구조를 생성하는 과정과,

key를 제거하며 정렬되는 과정, 두 단계로 정렬이 진행되는데,

node 수가 2^d 개수를 갖는 Worst case의 시간 복잡도는 다음과 같다.

 

* heap 구조를 생성하는 과정

<initialize> 하는 과정에서 worst case가 되려면, 모든 노드가 d-1 level로 떨어지는 케이스가 최악일 것이다.

즉, key값을 옮기는 총 횟수는 다음과 같다.

$$ \sum_{j=0}^{d-1}2^j(d-j-1) $$

이를 계산하면 2^d - d - 1 의 값이 나오는데, 이 값은 d level을 제외한 값이다.

따라서 위 값에서 d를 더해준 2^d - 1 = n-1 이 <initialize> 과정의 시간 복잡도이다.

 

* key를 제거하며 정렬되는 과정

<delete> 하는 과정에서 worst case가 되려면, 교체 당하는 작은 key가 root까지 올라갔다가

맨 아래로 떨어지는 케이스가 최악일 것이다.

2^(d-1)개의 key가 (d-1)번 떨어지는 것이다.

이 과정에서는 2^(d-2)개의 key가 (d-2)번 떨어지는 것이다.

 

이 과정이 반복되면 key값을 옮기는 총 횟수는 다음과 같다.

$$ \sum_{j=1}^{d-1}j2^j $$

이를 계산하면 d2^d - 2^(d+1) +2 의 값이 나오고, n으로 바꿔주면

n lg n - 2n - 2가 나오며, 이 값이 <delete> 과정의 시간 복잡도이다.

 

그렇기에 heap sort 알고리즘의 시간 복잡도의 하한선은 n lg n - n - 3이고,

이보다 빠르게 정렬하는 방법은 존재하지 않는다.

 

 

결론

마지막으로 key값 비교를 통한 정렬의 한계, lower bound를 알아보자.

모든 sorting 알고리즘은 Decision tree의 형태로 중간 상태와 결과를 기록할 수 있는데,

같은 input에 대해 같은 output을 내는 deterministic algorithm은

n개의 key를 decision tree를 이용해 sorting시 n!의 leaf node가 생긴다.

또한 worst case의 시간 복잡도는 decision tree의 depth와 같다.

 

이 때,  tree의 depth를 d라고 하고, lead node의 개수를 m이라고 하면 아래와 같은 관계식이 성립하는데,

$$ d \geq \left \lceil lg(m)\right \rceil $$

d가 worst case의 시간 복잡도를 갖는다 했으니,

n개의 key를 decision tree를 이용해 sorting시 아래와 같은 최소 비교 횟수를 해야함을 알 수 있다.

$$ \left \lceil lg(n!)\right \rceil $$

이를 근사하면 아래와 같은 식으로 변형이 가능한데,

$$ \left \lceil n \; lg(n) \; - \; 1.45n \right \rceil $$

이 것이 n개의 서로 다른 key를 비교하여 sorting하는 모든 알고리즘이 갖는 lower bound이다.