Linear Time Sorting

[Comparison Model] : 비교를 할 때 어떤 연산을 사용할지 제한한다.

• 모든 입력 항목이 무엇인지 정확히 모르기 때문에 black box이다.
• 유일하게 가능한 연산은 비교 연산이다.( <, <=, >, >=)

결국 소요 시간은 비교의 횟수가 된다.

Decision Tree(의사결정 트리)
→어떠한 비교 알고리즘도 비교할 수 있는 모든 경우의 수와 비교 결과 및 최종 결론으로 이루어진 트리로 표현할 수 있다.

Decision Tree

n개의 원소를 기준으로 진행을 하며, 결정에 대한 yes 또는 no의 답변을 가지고 트리의 가지를 쳐 나간다.
여기서 동그라미는 decision을 의미하며 사각형은 결과를 의미한다.

decision tree	algorithm
internal node	binary decision(comparsion)
leaf	found answer
root-to-leaf	algorithm execution
path length	running time
height of tree	worst-case

Decision Tree를 통해 각종 lower bound의 증명이 가능하다.

 

[탐색의 lower bound]

n개의 전처리된 item들이 있고 특정 item을 찾는다고 한다면 worst-case는 Ω(lg n)이다.
(즉, 최소한 lg n만큼의 시간이 소요된다.)

왜냐하면 decision tree는 yes or no로 구성되어 있기 때문이다.(즉, 결정 트리는 이진트리이다.) 트리는 모든 경우의 답을 가지고 있으며 따라서 계산하려는 아이템의 개수가 n개라면 모든 답의 개수가 최소 n개를 가지고 있어야 한다. 따라서 최소 n개의 아이템을 가지고 있는 이진트리의 높이는 최소 lg n이 된다.

 

[정렬의 lower bound]

decision tree를 통해 비교만으로 정렬된 결과를 도출해 낼 수 있다. 여기서 비교는 nlg n만큼 진행된다.
왜냐하면 decision tree는 이진트리이며 단말 노드는 최소한 가능한 답의 개수만큼 있어야 하기 때문이다.(중복이 있다면 당연히 더 많아질 것이다.) 여기서 정렬의 가능한 경우의 수는 n!이다. 

따라서 decision tree의 높이는 lg (n!) 보다 커야 한다. 이는 nlg n과 같다.

이에 대한 증명은 다음과 같다.

log(n!) = log(1) + log(2) + ... + log(n-1) + log(n)
log(1) + log(2) + ... + log(n) <= log(n) + log(n) + ... + log(n) = n*log(n) = Ω(nlg n)

또는 half sum을 이용해 다음과 같이 구할 수도 있다.

log(1) + ... + log(n/2) + ... + log(n) >= log(n/2) + ... + log(n)
                                              = log(n/2) + log(n/2+1) + ... + log(n-1) + log(n)
                                              >= log(n/2) + ... + log(n/2)
                                              = n/2 * log(n/2) = Ω(nlg n)

스털링 근사를 통해서도 증명할 수 있다.

결론적으로 nlg n - O(n) 이 나오기 때문에 Ω(nlg n)이다.

 

[Linear time sorting] - 정수 정렬

• 정렬하려는 n개의 key가 음이 아닌 정수라고 가정한다.
• 각각의 정수는 워드(RAM Machine)에 대응된다. (상수 시간 안에 두 key를 비교할 수 있다.)
• 비교 말고도 다양한 것들을 할 수 있다.
• 크지 않은 k에 대해 정렬을 선형 시간(O(n)) 내에 할 수 있다.

 

Counting Sort(계수 정렬)

1. 모든 항목을 다 센다.
2. 작은 숫자부터 존재하는 갯수만큼 써준다.

k개의 원소가 있다고 가정하면 k크기의 배열을 메모리에 할당한다. 그리고, 해당 숫자에 해당하는 index count를
개수만큼 증가시킨다. 그리고 배열의 앞부터 순서대로 배열의 숫자만큼 적어주면 정렬이 된다.

하지만 여기서 활용하는 정렬은 같은 정수가 있을 때 그 정수끼리 구분이 불가능하다.

결론적으로 Counting Sort에 걸리는 시간은 O(n+k)가 된다. k가 n과 비슷하면 선형 시간이 되지만
k이 커지면 문제가 발생한다.(선형 시간 내에 해결되지 않는다.)

 

Radix Sort(기수 정렬)

Counting Sort를 서브 루틴으로 활용하며, k가 아무리 커져도 선형 시간 내에 동작하도록 한다.

1. 숫자를 10진수가 아니라 b진수로 본다.
2. 최대 k개의 item이 있다면 자릿수 d = (logb k) + 1 이다.
3. 가장 낮은 자리 숫자 순서로 정수를 정렬한다.
4. 그다음 낮은 자리 숫자 순서로 정수를 정렬한다.
5. 위 과정(다음 낮은 자리 숫자로 정수 정렬)을 d번 반복한다.

Radix Sort에서 정렬하는 방법은 자릿수를 기준으로 Counting Sort를 사용한다.
여기서 Counting Sort에 걸리는 시간은 O(n+b)가 된다.

그러므로 전체 시간은 O((n+b)*d) = O((n+b)logb k) 이 된다.

여기서 가장 작은 경우는 b 가 n과 거의 같을 때이다.
따라서 O(nlogn k)와 같은 시간이 되며 만약 이 경우 k가 n^c보다 작다면 O(nc)가 될 수 있다.
즉, 선형 시간 내에 동작할 수 있다.