[주의] 이번 주제는 좀 더 수학적인 증명이 가미되어 있습니다.
이번 시간의 주제는 과연 정렬 알고리즘의 Worst Case 시간 복잡도 (Time Complexity) 의 Lower Bound 에 대한 수학적 증명입니다. 이 때, 이번 주제에서 정렬 알고리즘의 경우 Comparison Model, 즉 "임의의 배열 A 내에서 임의의 두 Element 들을 선택해 상수 시간 (Constant Time) 내에 두 element 값의 비교 (Comparsion) 를 통해 한 쪽이 다른 element 에 비해 작거나 크다는걸 결정할 수 있다" 를 전제하고 있습니다.
조금 더 디테일한 전제조건들은 다음과 같습니다.
1. 서로 다른 두 원소들간의 상대적인 순서를 값의 비교를 통해 결정한다
2. 서로 다른 임의의 두 원소에 대해서 값의 크고 작음을 상수 시간 [O(1)] 에 결정할 수 있다
3. 서로 다른 임의의 두 원소에 대해 상수 시간안에 두 원소의 위치를 교환할 수 있다 (Swap)
자 그러면 본론으로 들어가봅시다. 위의 전제조건을 사용하는 정렬 알고리즘이라면 하는 동작은 굉장히 단순합니다. 즉, 매 차례마다 특정한 방법으로 두 element 를 선택해서 값을 비교한 뒤, 이 두 원소들간의 순서를 설정하는거죠.
예를 들어, A = [3, 7, 2, 4] 의 배열이 있다 가정할 때, 어떤 방법으로 비교할 두 원소 7 과 2를 선택한 경우, 이 두 원소의 상대적인 순서에 대해 2가지 결정을 할 수 있습니다. 7 2 순으로 나열하거나 혹은 2 7 순서로 나열하는거죠. 다시 말해, A 내의 임의의 두 원소 (element) a, b 에 대해 매번 정확히 2가지의 경우의 수가 주어집니다: a b 혹은 b a 순으로 정렬하는거죠. 이 때, 이 경우의 수를 가지고 내릴 수 있는 의사 결정을 트리 (Tree) 형태로 표현할 수 있고, 이를 Decision Tree 라고 합니다.
이 때, 위의 트리가 이진 트리 (Binary Tree) 형태로 나타내어지고, 각 leaf node 에서 배열 전체의 모든 원소에 대해 서로가 서로에 대한 상대적인 순서가 결정되므로, 이 순서를 이용해 각 원소의 배열 내에서의 위치를 결정할 수 있게됩니다. 또, 궁극적으로 이 주제를 통해 도출하려고 하는 값은 Worst Case 의 시간 복잡도이므로 위의 방법을 통해 비교를 게속할 때, 최악의 경우 n 개의 원소를 (이때 n은 배열의 크기) 순서대로 나열할 수 있는 모든 경우의 수를 구해야 하고, 이는 순열 (Permutation) 의 정의와 일치합니다. 따라서 n 개의 원소를 순서대로 나열하는 방법은 n x (n-1) x (n-2) x ... x 1 = n! 이 됩니다. 즉, 이 이진 트리의 leaf node 의 갯수는 n! 이 되고, 최종적으로 구하고자 하는 Worst Case 의 시간 복잡도의 경우, 이 이진 트리에서의 제일 긴 경로 (Path) 의 길이와 같다고 생각할 수 있습니다. 이는 그래프 이론에서의 트리의 높이 (Height) 를 의미하고, 위 트리에서는 \( \log_{2} n! \) 이 됩니다. 이를 로그의 성질을 이용해 전개해보면, (또는 Stirling's approximation 을 이용해서도 도출할 수 있습니다.)
$$ \log_{2}n + \log_{2}(n-1) + \log_{2}(n-2) + \cdots + \log_{2}1 \leq n\log_{2}n = O(n\log n) $$
즉, Comparison Model 에서 임의의 정렬 (Sorting) 알고리즘에 대해 Worst Case 시간 복잡도 (Time Complexity) 는 Big-O 표기법으로 나타내었을 때 \( O(n\log n) \) 이고, 이는 어떤 알고리즘이던지 Worst Case 에서 만족해야 하는 Lower Bound 를 나타내므로 Big-Omega 표기법을 이용해 \( \Omega(n\log n) \) 로 나타낼 수 있습니다. (점근적 분석법에 대한 자세한 내용은 여기를 참고해주세요.)
Comparsion Model 에서의 Worst Case 시간 복잡도의 Lower Bound
위 Decision Tree 의 Height 와 같은 이유는 이 트리에서 매 경로 (Path) 하나하나가 최종적인 정렬 순서 하나에 대응되기 때문입니다. 예제의 경우 a[0] < a[1] < ... < a[n-1] 을 사용하였는데, 이 때 이 순서를 도출하기 위해서는 첫 시작지점 (root 노드) 에서 부터 각 레벨 마다 두 경우의 수 중 하나를 선택해서 의사 결정을 해나가야 하고, 이 과정을 계속해서 최종 목적지인 어떤 leaf node 에 도달하게 되었을 때, 이 의사 결정에 소요된 시간, 즉 시간 복잡도는 root 에서 해당 leaf 까지의 경로의 길이와 같습니다. 그리고 결론적으로 Worst Case 를 구하는 것이므로 이 트리 내에서의 모든 경로들 중 제일 긴 경로를 찾아야하고, 위의 모든 전제 조건들이 비교를 중복해서 하는 경우의 수를 제외하는 최상의 시나리오를 가정한 것이기 때문에 Comparsion Model 에서 어떤 정렬 알고리즘이던지 항상 위에서 도출한 시간 복잡도와 같거나 혹은 더 큰 양상으로 증가해야 합니다.
트리의 높이 구하기
위 이진 트리에서 매 시행마다 노드의 갯수가 2배씩 증가하고, k 번의 시행 후의 최종적인 leaf node 의 갯수를 \( n! \) 개라고 했을 때, 이를 수식으로는 \( 2^k = n! \) 라고 나타낼 수 있습니다. 이 때 k 값을 구하기 위해 양 변에 2 를 밑으로 하는 로그를 취해주면, \( k = \log_{2} n! \) 이 됩니다.
댓글