비교기반 정렬
비교기반 정렬이 무엇인가에 대한 설명은 --에 있다
비교기반 정렬의 시간 복잡도의 하한은 \(n log(n)\) 이라고 알려져 있다.
조금 더 정확하게 표현은 다음과 같은 구절을 보면 된다.
Can we say that it is impossible to sort faster than Ω(n lg n) in the worst case? If we could, then this would be what it’s called a lower bound.
비교기반 정렬은 가장 Worst Case에 대해서도(그러니까 모든 Case의 정렬 형태에 대해) 필요한 시간 복잡도가 \(nlog(n)\) 정도라는 것으로 이보다 더 적은 방법이 없다는 것이다. 여담으로 시간 복잡도의 상한은 \(n^2\) 이다
따라서 비교기반 정렬을 사용했다면 그 알고리즘의 시간 복잡도는 \( n^2\) ~ \(nlog(n) \) 을 가진다는 것을 예상 할 수 있다.
비교 정렬 기반 정렬 알고리즘의 시간 복잡도의 하한 \(nlog(n)\) 에 대한 증명은 책 Introduction to algorithm 에 소개되어있는 decision tree 방법을 이용한 방법이 제일 유명하다 (wiki에서도 이 방법을 소개하고 있음)
Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009) [1990]. Introduction to Algorithms (3rd ed.). MIT Press and McGraw-Hill. pp. 191–193. ISBN 0-262-03384-4
정렬이 가능한 배열 \(a_1, a_2 ,a_3\) 가 있다고하자
총 가능한 순열은 $3!$ 중에 정렬을 마치면 하나의 배열로 $a_2, a_1, a_3$ 가 되든 $a_3, a_2, a_1$이 되든 할 것이다.
이를 확장하면 $n$ 개의 원소가 있다면 $n!$ 의 가능한 순열이 존재하며 이 중 단하나의 순서가 정렬이 된 배열이라고 하자
비교기반 정렬과 Decision Tree
비교기반 정렬은 두개의 원소들의 크기를 비교한다. 이러한 비교정렬의 과정들은 Decision Tree로 대응시킬수 있다.
비교 기반 정렬을 사용한다면 이전 상태의 정보를 가지고 있는 채로 어떤 두 원소를 비교하고(어떤 원소 두개를 비교하느냐가 알고리즘의 핵심이다) 비교 결과를 가지고 이후 상태(비교 결과에 따라 두가지 상태로 나뉘게됨)로 가게된다.
아래의 예시를 보며 생각해보자
이전 상태의 정보들을 가지고 있는 상태로 ( $a_i < a_j$ ) 두 원소의 크기를 비교한다면 결과는 2가지만 나올수 있다. 이러한 성질은 Decision Tree중에 2개의 leaf Node를 갖는 Decision Tree와 대응이 될 수 있다.
또한 이후 상태는 비교 결과의 정보를 가지고 있고 이전 상태보다 더 많은 정보를 가진채로 존재하게 된다.
그렇기 때문에 이후 상태는 이전 상태보다 하나더 많은 정보를 가지고 있기 때문에 이후 상태는 정렬에 충분한 정보를 가지고 있을 수 있으며 그 경우 정렬 상태가 완벽하게되고 알고리즘이 멈추게 된다. 이는 Decision Tree로 따지면 Terminal Node가 존재한다는 걸로 대응된다.
(이런식으로 대응하는 Tree에 Terminal Node가 무조건 존재할까? )
여태까지 Decision Tree와 비교기반 정렬 알고리즘의 대응관계를 살펴보았음으로 이제부터 비교기반 정렬을 Decision Tree과 혼용해서 쓰겠다.
다음은 원소 3개에 대해서 비교정렬 알고리즘중에서 어떤 것을 적용한것이다.
Tree를 적용하면서 Node를 내려가다가 정보가 충분해지면 END하게 (Terminal Node가 발생)되며 그 이후로 leaf Node는 없게 된다.
옆과 같이 3개의 원소 , $3!=6$개의 가능한 배열을 Decision Tree로 정렬을 하게될때에는 Depth가 3이면 충분했다.
따라서 3개의 원소의 경우 최대 3번의 비교를 진행하면 되는 것을 알 수 있고
이는 $3log3=3.295837..$ 정도이다. 우리가 주장하는 바에 따르면 이보다 적은 수로 정렬을 시키는 비교 기반 정렬 방법은 없다.
이는 Decision Tree의 Depth 는 정보가 충분하여 Terminal Node가 되어 leaf node가 없는 Case를 포함해서
깊이 $d$가 늘어 날때마다 leaf node수는 $2^d$ 만큼 늘어나게 된다. (특히 2개의 leaf node를 갖는 Decision 이므로)
그러면 $n!$개의 가능한 배열있고 이를 Decision Tree(=비교기반정렬)로 판정하려면 판정에 필요한 최대 깊이 $d$ 는 몇일까?
증명
깊이를 $d$는 결국 정렬에 필요한 연산 횟수이며 주어진 $n$에 대해서 최소한 적어도 $2^d \geq n!$ 만큼은 필요하다라는것을 알 수 있다.
따라서 $d$의 하한은 $log_2(n!)$가 되고 $log_2(n!)$의 시간 복잡도를 알면된다.
$\log(n!)$의 시간 복잡도를 Sandwich 증명으로 증명할 예정이다
$\log(n!)$의 상한과 하한이 모두 $O(n\log(n))$ 임을 보이자
$2^d \geq n!$
$ = \log_2(n!)$
\( = \log_2(n(n-1)(n-2)\dots (3)(2)) \)
$ = \sum_{k=2}^n \log_2 k$
$ = \sum_{k=2}^{n/2} \log_2 k + \sum_{k=2}^n \log_2 k$
하한부터 구하면
$ = \sum_{k=2}^{\frac{n}{2}-1} \log k + \sum_{k=\frac{n}{2}}^n \log k$
$ \geq 0 + \sum_{k=\frac{n}{2}}^n \log k $
$ \geq 0 + \sum_{k=\frac{n}{2}}^n \log \frac{n}{2}$
$ = \frac{n}{2} \log \frac{n}{2} $ ~ $O(n\log n)$
$ \log n! \geq O(n\log n)$
상한은
$ n^n \geq n!$ 이 성립함으로
$ n\log n \geq \log(n!)$ 이 성립하고
$ O(n\log n) \geq \log n!$
이 성립함으로 $\log(n!)$~$O(n\log n) $ 이다