계산 복잡도 이론

계산 복잡도 이론은 계산 문제를 푸는 알고리즘을 복잡도에 따라 분류하여 문제의 모임인 복잡도 종류를 구성하는 방법을 연구한다. 알고리즘이 실행될 때 소모하는 자원의 양을 수량화하여 문제의 본질적인 어려움을 파악하는 것이 핵심이다. 이는 실제 컴퓨터의 성능과는 독립적으로, 수학적으로 정의된 계산 모델을 통해 평가된다.

알고리즘의 복잡도를 측정하는 가장 일반적인 기준은 시간과 공간이다.

• 시간 복잡도(Time Complexity): 문제를 해결하기 위해 필요한 기본 연산의 횟수를 의미한다. 보통 입력의 크기에 따른 함수로 나타낸다.
• 공간 복잡도(Space Complexity): 문제를 해결하는 과정에서 필요한 메모리 저장소의 양을 의미한다.

이 외에도 병렬 컴퓨팅에서의 프로세서 수, 통신 복잡도에서의 통신량, 회선 복잡도에서의 게이트 수 등이 자원의 척도로 사용될 수 있다.

알고리즘의 수행 능력을 평가하기 위해 튜링 기계와 같은 정량화된 계산 모델을 사용한다. 복잡도 이론은 이러한 수학적 모델을 도입하여 시간과 저장 공간 같은 자원의 양을 공식화한다. 문제의 복잡도는 해당 문제를 해결할 수 있는 모든 알고리즘 중 최선의 알고리즘이 가지는 복잡도로 정의된다.

복잡도 이론에서 '문제'는 관련 질문들의 전체 집합을 의미하며, 각 질문은 유한한 길이의 문자열로 표현된다. 특정 질문 하나를 '인스턴스(Instance)'라고 부른다. 예를 들어, '정수의 소인수를 구하라'는 것은 하나의 문제이며, '15의 소인수를 구하라'는 것은 그 문제의 구체적인 인스턴스이다.

계산 복잡도 이론은 인접한 컴퓨터 과학 분야와 다음과 같은 차이점이 있다.

• 계산 가능성 이론(Computability Theory): 자원의 양과 무관하게 어떤 문제를 컴퓨터로 풀 수 있는지 없는지를 다룬다. 반면 복잡도 이론은 풀 수 있는 문제 중 얼마나 많은 자원이 필요한지를 다룬다.
• 알고리즘 분석(Algorithm Analysis): 명시적으로 주어진 특정 알고리즘의 효율성을 연구한다. 반면 계산 복잡도 이론은 문제 자체를 해결하기 위한 최선의 복잡도와 문제 간의 분류를 연구한다.