문제를 푸는 알고리즘에 도전하는 방식은 두 가지가 있다.
- try to develop a more efficient algorithm for the problem
- try to prove that a more efficient algorithm is not possible
즉 알고리즘을 개선하던가, 아니면 더 효율적인 알고리즘은 만들 수 없다고 증명하던가 둘 중에 하나이다.
만약 더 효율적인 알고리즘을 만들 수 없다고 증명을 하면, 더 이상 알고리즘을 개선할 필요가 없다.
참고로 key의 comparison을 이용한 sorting algorithm은 nlgn보다 줄일 수 없다고 증명되었다.
1. Computational Complexity (계산 복잡도)
지금까지는 알고리즘의 복잡도를 계산했지만, 이 글에서는 문제 자체의 계산 복잡도에 대해 알아볼 것이다.
Computational Complexity는 주어진 문제를 풀 수 있는 모든 알고리즘을 연구하는 것이다.
이때 계산 복잡도 분석은 모든 알고리즘의 효율성의 lower bound를 결정한다.
예를 들어서 통상적으로 생각하는 행렬 곱셈(3-for loop)은 시간 복잡도가 n^3임을 알았다.
하지만 행렬 곱셈의 문제의 시간 복잡도가 \(\theta(n^3)\)라는 뜻은 아니다.
실제로 행렬 곱셈의 시간 복잡도는 \(\theta(n^2)\)라고 밝혀졌다.
따라서 행렬 곱셈 문제를 푸는 하한(lower bound)는 \(\Omega(n^2)\)인 것이다.
하지만 이는 곧 \(\theta(n^2)\)인 알고리즘을 찾을 수 있음을 보장하는 것이 아니다.
실제로 지금까지 알려진 최고의 알고리즘은 \(\theta(n^{2.38})\)이다.
아마 언젠가는 \(\theta(n^{2.38})\)보다 더 좋은 알고리즘을 발견하던가, 혹은 \(\Omega(n^2)\)보다 더 낮은 하한이 있음을 증명하게 될 수도 있다.
일반적으로 어떤 문제가 주어지만 해당 문제의 lower bound인 \(\Omega(f(n))\)을 구하고, 그 문제를 푸는 \(\theta(f(n))\) 알고리즘을 개발한다.
즉 문제의 하한 시간 복잡도를 구한 뒤, 최대한 문제의 시간 복잡도에 근접한 알고리즘을 개발하는 것이 일반적인 절차인 것이다.
일단 이 일이 끝나면 상수 시간 복잡도로 개선하는 것 외에는 알고리즘의 성능을 향상 시킬 수 없다.
2. The Sorting Problem
정렬 문제를 가지고 계산 복잡도를 소개할 예정이다.
이 문제를 선택한 이유는 정렬에 대한 알고리즘이 꽤 많이 발견되었고, 정렬 문제의 시간 복잡도의 하한만큼 좋은 알고리즘이 존재하는 몇 되지 않은 문제 중 하나이다.
실제로 정렬 문제의 lower bound는 \(\Omega(n lgn)\)이고, \(\theta(n lgn)\)인 알고리즘이 여럿 있다.
일단 Sorting Problem에서 원소를 확인하는 것부터가 n이다. 즉 Sorting Problem은 기본적으로 \(\Omega(n)\)인 셈이다.
key를 비교하여 정렬하는 정렬의 lower bound는 \(\Omega(n lgn)\)입니다.
대표적인 예시로 MergeSort, QuickSort, HeapSort가 있습니다.
하지만 분류를 통한 정렬의 lower bound는 \(\Omega(n)\)이 됩니다.
예시로 Radix Sort(Bucket Sort)가 있습니다.
3. The Searching Problem
검색 문제에서 오로지 key의 비교를 가지고 검색할 때의 lower bound에 대해 알아보겠습니다.
만약에 Tree에서 검색을 한다면
- Binary Search Tree
- \(\Omega(lgn)\), \(O(n)\)
- AVL Trees, Red-Black trees : Balanced Search Tree
- \(O(lgn)\)
- B-Trees, B+-Trees
만약 Hash Tables에서 찾는다면 이는 O(1)이 됩니다.
감사합니다.
다음 글에는 Selection Problem에서의 Adversary Argument에 대해서 글을 쓰겠습니다.
지적 환영합니다.