오늘은 계산 복잡도 이론에 대해 잠깐 알아보겠다.
어떤 문제를 푸는 데에는 어떠한 알고리즘이 필요하다. 어떤 문제는 풀기 쉽고, 어떤 문제들은 풀기 어렵다. 예를 들어서. 어떤 숫자의 리스트를 정렬하는 것은 쉬운 문제이다. 이미 알려진 알고리즘도 굉장히 많다. 선택 정렬, 삽입 정렬, 거품 정렬 등등.... 그리고 시간 복잡도도 정렬에 따라 O(n^2) 아니면 O(nlogn)임을 알 수 있다.
반면 가장 효율적으로 대학 수업들을 서로 강의실과 시간이 겹치지 않게 모두 정렬하는 것은 어려운 문제이다. 고려해야 할 시간과 강의실도 있고, 무엇보다 그 수업들이 겹치지 않도록 해야 한다.
하지만, 알고리즘을 생각해 낸다고 해서 그 알고리즘이 가장 효율적인 것은 아니다. 예를 들어, 어떤 두 자연수가 서로소인지를 판단하는 문제를 살펴보자. 단순이 생각하면, 두 숫자의 약수를 다 찾아내서 일일히 확인해 볼 수 있다. 하지만 이것은 자연수의 약수들이 많아지면 굉장히 비효율적일 것이다.
하지만 더 쉬운 방법이 있다. 바로 유클리드의 알고리즘을 사용하는 것이다. 자세한 내용은 다음과 같다.
유클리드의 알고리즘
1. x, y를 두 자연수라고 할 때, 다음 2-3번을 y가 0이 될 때까지 반복한다.
2. x 를 x mod y로 치환한다.
3. x와 y의 값을 바꾼다.
4. x가 1이면, 서로소이고, 그렇지 않으면 서로소가 아니다.
이런 식으로 알고리즘을 짜면, 약수를 찾아내서 일일히 확인해 보는 것보다 훨씬 시간을 절약할 수 있다. 따라서, 두 자연수가 서로소인지 판별하는 문제는 우리가 생각하는 것보다 간단한 알고리즘으로 해결될 수 있다.
이렇듯 알고리즘을 찾는다고 해서 그것이 가장 효율적인 알고리즘은 아니다. 계산 복잡도 이론은 어떠한 문제를 푸는 알고리즘을 시간 복잡도(time complexity)에 분류하는 방법을 연구한다. 앞으로 차근차근 문제들의 분류에 대해서 알아볼 것이다. 계산 복잡도 이론과 관련된 유명한(아마?) 문제는 P vs NP 문제이다. 간단히 말해서 P 가 NP의 진부분집합이냐 아니냐의 문제인데, 이것도 차근차근 살펴보겠다. 참고로 이 문제는 상금 100만 달러가 걸린 밀레니엄 난제 중의 하나이다.