Algorithm] 비교 정렬의 하한

항상 고민하던 게 있다.

비교 정렬의 하한이 nlogn이며 이보다 더 좋은 정렬 알고리즘은 없다는 이야기를 들었다.

도대체 왜 그런 것인지, 어째서 그런 것인지에 대해서 잘 모르고 넘어갔다.

주어진 문제에 대해서 시간 복잡도의 하한이라는 것은

어떤 문제도 이 하한보다 빠르게 구할 수 없다는 것을 의미하는데,

이 하한이 알고리즘에 대한 시간 복잡도가 아니라

이 문제의 고유 특성으로 인해서 과거부터 지금까지, 혹은 미래에 만들어진

어떤 효율적인 알고리즘이더라도 적어도 하한의 시간복잡도 만큼 걸린다는 것을 의미한다.

 

n개의 숫자가 저장된 배열이 있다고 하자.

여기서 최솟값을 찾는 문제의 하한은 최소한 n-1회의 비교가 필요하므로 n-1이다.

이런 식으로 n개의 수를 비교 정렬할 때 필요한 최소 비교 횟수가 어떻게 되는지 생각을 해보면 답이 나올 것이다.

일단, 3개의 수 x, y, z에 대해서 비교 정렬을 실시한다고 할 때 모든 경우를 살펴보자.

이러한 식으로 결과가 leaf에 저장된 형태를 결정 트리(Decision Tree)라고 하는데, 비교 정렬의 결정트리는 다음과 같은 특징을 가지고 있다.

1. 이진트리

2. leaf의 수 : n!

3. 불필요한 내부 노드는 없음.

내부 노드 비교가 참인 경우와 거짓인 경우의 자식 노드를 가지는 트리로 이진트리이며,

leaf의 수가 n!인 것은 서로 다른 n개의 숫자가 정렬되는 모든 경우의 수가 n!이기 때문이다.

중복 비교 가능성이 존재하긴 하나,

최소한 정렬 결과를 얻기 위해 반드시 필요하다는 점에서 과감히 제거할 순 없다.

최소한 3개의 숫자를 비교 정렬하기 위해서 요구하는 비교 횟수는 3번으로,

결정 트리의 높이와 동일하다는 뜻으로,

n개의 서로 다른 숫자를 비교 정렬하는 결정 트리 높이가 비교정렬의 하한이 됨을 뜻한다.

결국 n!개의 이파리가 있는 이진트리의 최소 높이는 log(n!)이고,

n!은 근사적으로 n^n(정확히는 (n/2)^(n/2)이다.)이기 때문에,

O(log(n!))=O(nlogn)이 되며, 이것이 비교 정렬의 하한이 된다.

결정 트리를 바탕으로 이보다 더 효율적인 시간 복잡도를 가진

비교 정렬 알고리즘이 존재하지 않는다는 것을 증명할 수 있다.