계산 복잡도

컴퓨터 과학에서 알고리즘의 계산 복잡도(計算複雜度, computational complexity) 또는 단순히 복잡도(complexity)는 알고리즘을 실행하는 데 필요한 자원의 양이다. 특히 계산 시간(일반적으로 필요한 기본 연산의 수로 측정)과 메모리 저장소 요구 사항에 중점을 둔다. 문제의 복잡도는 문제를 해결할 수 있는 최선의 알고리즘의 복잡도를 의미한다.

명시적으로 주어진 알고리즘의 복잡도를 연구하는 것을 알고리즘 분석이라고 하고, 문제의 복잡도를 연구하는 것을 계산 복잡도 이론이라고 한다. 알고리즘의 복잡도는 항상 이 알고리즘이 해결하는 문제의 복잡도의 상한선이므로 두 영역은 서로 밀접한 관련이 있다. 또한 효율적인 알고리즘을 설계하기 위해서는 특정 알고리즘의 복잡도와 해결하고자 하는 문제의 복잡도를 비교하는 것이 기본이 된다. 대부분의 경우 문제의 복잡도에 대해 알려진 유일한 내용이 가장 효율적인 알고리즘의 복잡도보다 낮다는 것 뿐이다. 따라서 알고리즘 분석과 복잡도 이론 사이에는 많은 부분이 겹친다.

알고리즘을 실행하는 데 필요한 자원의 양은 일반적으로 입력의 크기에 따라 달라지기 때문에 복잡도는 일반적으로 $n \to f (n)$ 함수로 표현되며, 여기서 $n$ 은 입력의 크기이고 $f (n)$ 은 최악 복잡도( $n$ 크기의 모든 입력에 대해 필요한 자원의 최대값)이거나 평균 복잡도( $n$ 크기의 모든 입력에 대한 자원의 평균값)이다. 시간 복잡도는 일반적으로 크기 $n$ 의 입력에 필요한 기본 연산의 수로 표현되며, 기본 연산은 주어진 컴퓨터에서는 일정한 시간이 걸리고 다른 컴퓨터에서 실행할 때는 상수배만큼만 변한다고 가정한다. 공간 복잡도는 일반적으로 $n$ 크기의 입력에 대해 알고리즘이 필요로 하는 메모리 양으로 표현된다.

자원

시간

가장 일반적으로 고려되는 자원은 시간이다. "복잡도"라는 용어가 한정 없이 사용될 때, 이는 일반적으로 시간 복잡도를 의미한다.

일반적인 시간 단위(초, 분 등)는 특정 컴퓨터의 선택과 기술의 진화에 너무 많이 의존하기 때문에 복잡도 이론에서는 사용되지 않는다. 예를 들어, 오늘날의 컴퓨터는 1960년대의 컴퓨터보다 훨씬 빠르게 알고리즘을 실행할 수 있다. 그러나 이는 알고리즘의 본질적인 특징이 아니라 컴퓨터 하드웨어의 기술적 발전의 결과이다. 복잡도 이론은 알고리즘의 본질적인 시간 요구 사항, 즉 알고리즘이 모든 컴퓨터에 적용할 기본적인 시간 제약을 정량화하고자 한다. 이는 계산 중에 실행되는 기본 연산의 수를 계산하여 얻을 수 있다. 이러한 연산은 주어진 컴퓨터에서 일정한 시간(즉, 입력의 크기에 영향을 받지 않음)이 걸리는 것으로 가정하며, 흔히 단계(step)라고 한다.

비트 복잡도

공식적으로 비트 복잡도(bit complexity)는 알고리즘을 실행하는 데 필요한 비트에 대한 연산 횟수를 나타낸다. 대부분의 계산 모형에서 비트 복잡도는 시간 복잡도와 상수배로 같다. 컴퓨터에서는 필요한 기계어 연산 횟수도 비트 복잡도에 비례한다. 따라서 현실적인 계산 모형에서 시간 복잡도와 비트 복잡도는 동일하다.

공간

또 다른 중요한 자원은 알고리즘을 실행하는 데 필요한 컴퓨터 메모리 크기이다.

통신

여러 상대방과 서로 상호 작용하며 실행하는 분산 알고리즘의 경우 가장 관심 있는 자원은 통신 복잡도이다. 이는 실행에 필요한 통신의 양이다.

기타

산술 연산 횟수는 일반적으로 고려되는 또 다른 자원이다. 이 경우 산술 복잡도라고도 한다. 계산 중에 발생하는 숫자의 이진 표현 크기에 대한 상한을 알고 있다면 시간 복잡도는 일반적으로 산술 복잡도에 상수 인자를 곱한 값이 된다.

많은 알고리즘에서 계산 중에 사용되는 정수의 크기는 제한이 없으며, 산술 연산에 일정한 시간이 걸린다고 가정하는 것은 현실적이지 않다. 따라서 이러한 맥락에서 일반적으로 비트 복잡도라고 하는 시간 복잡도는 산술 복잡도보다 훨씬 더 클 수 있다. 예를 들어, $n \times n$ 정수 행렬의 행렬식 계산의 산술 복잡도는 일반적인 알고리즘(가우스 소거법)의 경우 $O(n^{3})$ 이다. 동일한 알고리즘의 비트 복잡도는 계산 과정에서 계수의 크기가 기하급수적으로 증가할 수 있기 때문에 $n$ 에 대해 지수적이다. 반면 이러한 알고리즘이 다중 모듈러 산술과 결합되면, 비트 복잡도는 $O ~ (n 4)$ 로 감소될 수 있다.

정렬과 검색에서 일반적으로 고려되는 자원은 항목 비교의 횟수이다. 이는 일반적으로 데이터가 적절하게 구성되어 있다면 시간 복잡도를 측정하는 좋은 방법이다.

입력 크기의 함수로서의 복잡도

가능한 모든 입력에 대해 알고리즘의 단계 수를 세는 것은 불가능하다. 일반적으로 복잡도는 입력의 크기에 따라 증가하므로 복잡도는 입력의 크기 $n$ (비트 단위)의 함수로 표현되며, 따라서 복잡도는 $n$ 의 함수가 된다. 그러나 같은 크기의 입력이라도 알고리즘의 복잡도는 크게 달라질 수 있다. 따라서 일반적으로 몇 가지 복잡도 함수가 사용된다.

최악 복잡도는 크기 $n$ 의 모든 입력에 대한 복잡도의 최대값이며, 평균 복잡도는 크기 $n$ 의 모든 입력에 대한 복잡도의 평균이다. 일반적으로 따로 꾸며주는 말 없이 "복잡도"라고만 사용할 경우는 경우 최악 시간 복잡도를 말한다.

점근적 복잡도

최악의 경우와 평균적인 경우의 복잡도를 정확하게 계산하는 것은 일반적으로 어렵다. 또한 컴퓨터나 계산 모형을 변경하면 복잡도가 다소 달라지기 때문에 이러한 정확한 값은 실제 적용에 거의 도움이 되지 않는다. 또한, 작은 $n$ 값에서는 자원 사용량이 중요하지 않기 때문에 일반적으로 낮은 복잡도보다 구현의 용이성이 더 중요하다.

이러한 이유로 일반적으로 큰 $n$ 에 대한 복잡도의 양상, 즉 $n$ 이 무한대로 갈 때의 점근 동작에 초점을 맞춘다. 따라서 복잡도는 일반적으로 대문자 O 표기법을 사용하여 표현한다.

예를 들어, 정수 곱셈의 일반적인 알고리즘은 복잡도가 $O(n^{2}),$ 인데, 이 것은 상수 $c_{u}$ 가 있어 최대 $n$ 자리의 두 정수를 곱하는 데 $c_{u}n^{2}$ 보다 작은 시간이 걸린다는 것을 의미한다. 이 경계는 최악의 복잡도와 편균 복잡도가 $\Omega (n^{2})$ 으로 날카로운ㄷ, 이는 상수 $c_{l}$ 이 있어 복잡도가 $c_{l}n^{2}$ 보다 크다는 뜻이다. 복잡도에는 기수를 적지 않는데, 기수가 바뀌더라도 $c_{u}$ 와 $c_{l}$ 상수만 변경되기 때문이다.

계산 모형

복잡도 평가는 단위 시간에 수행되는 기본 연산을 정의하는 계산 모형의 선택에 따라 달라진다. 계산 모형이 명시적으로 지정되지 않은 경우 일반적으로 다중테이프 튜림 기계를 의미한다.

결정적 모형

결정적 계산 모형은 기계의 연속적인 상태와 수행될 연산이 이전 상태에 의해 완전히 결정되는 계산 형이다. 역사적으로 최초의 결정적 모형은 재귀 함수, 람다 대수, 튜링 기계였다. 랜덤 접근 기계(RAM 기계) 모형도 실제 컴퓨터에 더 가까운 것으로 널리 사용되고 있다.

계산 모형이 지정되지 않은 경우 일반적으로 다중테이프 튜링 기계로 가정한다. 대부분의 알고리즘의 경우 시간 복잡도는 다중 테이프 튜링 기계에서 RAM 기계와 동일하지만, 이러한 동등성을 얻기 위해 데이터가 메모리에 저장되는 방식에 약간의 주의가 필요할 수 있다.

비결정적 계산 모형

비결정적 튜링 기계 같은 비결정적 계산 모형에서는 계산의 일부 단계에서 몇 가지 선택이 수행될 수 있다. 복잡도 이론에서는 가능한 모든 선택을 동시에 고려하며, 비결정적 시간 복잡도는 최선의 선택이 항상 수행될 때 필요한 시간이다. 즉, 필요에 따라 많은 (동일한) 프로세서에서 동시에 계산이 수행된다고 가정하고, 비결정적 계산 시간은 계산을 완료한 첫 번째 프로세서가 사용한 시간이라 간주한다.

이러한 계산 모횽은 아직 현실적이지 않더라도 이론적으로 중요한데, 주로 "다항 시간"과 "비결정적 다항 시간"을 최소 상한으로 삼아 형성되는 복잡도 클래스의 정체성에 의문을 제기하는 P = NP 문제와 관련이 있다. 결정적 컴퓨터에서 NP 알고리즘을 시뮬레이션하는 데는 일반적으로 "지수 시간"이 걸린다. 비결정적 컴퓨터에서 다항 시간 내에 풀 수 있는 문제라면 복잡도 클래스 NP에 속하는 문제이다. 대략적으로 말해서 NP에 속하고 다른 어떤 NP 문제보다 쉽지 않은 경우, 그 문제는 NP-완전 문제라 한다. 배낭 문제, 외판원 문제, 충족 가능성 문제와 같은 많은 조합론 문제가 NP 완전 문제이다. 이러한 모든 문제에 대해 가장 잘 알려진 알고리즘은 기하급수적인 복잡도를 가지고 있다. 이러한 문제 중 하나라도 결정적 기계에서 다항 시간 내에 풀 수 있다면 모든 NP 문제도 다항식 시간 내에 풀 수 있으며, P = NP가 될 것이다. 2017년 현재 일반적으로 P ≠ NP라고 추측되는데, 이는 최악의 경우의 NP 문제는 본질적으로 풀기 어렵다는, 즉 입력의 길이가 길어질수록 합리적인 시간 범위(수십 년!)보다 오래 걸릴 것이라고 일반적으로 추측된다.

병렬 및 분산 컴퓨팅

병렬 및 분산 컴퓨팅은 동시에 작동하는 여러 프로세서에서 연산을 분할하여 구성된다. 두 모형의 차이점은 주로 프로세서 간의 정보 전송 방식에 있습니다. 일반적으로 병렬 컴퓨팅에서는 프로세서 간의 데이터 전송이 매우 빠른 반면, 분산 컴퓨팅에서는 데이터 전송이 네트워크를 통해 이루어지므로 훨씬 느리다.

$N$ 개의 프로세서에서 계산하는 데 필요한 시간은 적어도 단일 프로세서에서 필요한 시간의 $N$ 배이다. 실제로 일부 하위 작업은 병렬화가 불가능하고 일부 프로세서는 다른 프로세서의 결과를 기다려야 할 수도 있기 때문에 이론적으로 이 최적 한계에 도달할 수 없다.

따라서 주된 복잡도 문제는 계산 시간과 프로세서 수의 곱이 단일 프로세서에서 동일한 계산에 필요한 시간에 최대한 가까워지도록 알고리즘을 설계하는 것이다.

양자 컴퓨팅

양자 컴퓨터는 양자역학에 기반한 계산 모형을 가진 컴퓨터이다. 처치-튜링 논제가 양자 컴퓨터에도 적용된다. 즉, 양자 컴퓨터로 풀 수 있는 모든 문제는 튜링 기계로도 해결할 수 있다. 그러나 일부 문제는 이론적으로 고전적인 컴퓨터가 아닌 양자 컴퓨터를 사용하면 훨씬 더 낮은 시간 복잡도로 해결할 수 있다. 현재로서는 효율적인 양자 컴퓨터를 구축하는 방법을 모르기 때문에 이는 순전히 이론에 불과하다.

양자 복잡도 이론은 양자 컴퓨터를 사용해 풀 수 있는 문제의 복잡도 등급을 연구하기 위해 개발되었다. 양자 복잡도 이론은 양자 컴퓨터를 이용한 공격에 저항하는 암호화 프로토콜을 설계하는 양자 후 암호에 사용된다.

문제 복잡도 (하한값)

문제의 복잡도는 알려지지 않은 알고리즘을 포함하여 문제를 해결할 수 있는 알고리즘의 복잡도의 하한값이다. 따라서 문제의 복잡도는 문제를 해결하는 알고리즘의 복잡도보다 크지 않다.

따라서 대문자 O 표기법으로 표현되는 알고리즘의 모든 복잡도는 해당 문제의 복잡도에 대한 상한이 된다.

반면에 일반적으로 문제 복잡도의 하한을 구하기는 어렵고, 그러한 하한을 구하는 방법도 거의 없다.

대부분의 문제를 해결하려면 모든 입력 데이터를 읽어야 하는데, 일반적으로 데이터 크기에 비례하는 시간이 필요하다. 따라서 이러한 문제의 복잡도는 적어도 선형 시간, 즉 빅 오메가 표기법으로 적으면 $\Omega (n)$ 가 된다.

일반적으로 계산대수학 및 계산대수기하학에서 일부 문제의 해는 매우 클 수 있다. 이러한 경우 출력을 작성해야 하므로 복잡도는 출력의 최대 크기에 의해 하한이 정해진다. 예를 들어, $d$ 차 $n$ 원 다항식은 해의 수가 유한하다면 (베조 정리에 따라) 최대 $d^{n}$ 개의 복소해를 가질 수 있다. 이러한 해를 출력해야 하므로, 이 문제의 복잡도는 $\Omega (d^{n})$ 가 된다. 이 문제의 경우, 복잡도 $d^{O(n)}$ 인 알고리즘이 알려져 있으므로, 점근적으로 준최적이라고 간주할 수 있다.

정렬 알고리즘에서 필요로 하는 비교 횟수는 비선형 하한인 $\Omega (n\log n)$ 이 알려져 있다. 따라서 가장 좋은 정렬 알고리즘의 복잡도가 $O(n\log n)$ 이므로, 최적이다. 이 하한은 $n$ 개 값으로 만들 수 있는 순열의 가지수가 $n!$ 이라는 사실에서 비롯된다. 매 비교마다 $n!$ 개가 두 부분으로 나뉘므로, 면서 나뉘면서 모든 순열을 구분하는데 필요한 최소 비교 횟수 $N$ 은 $2^{N}>n!$ 이어야 하므로, 스털링 근사에 따라 $N=\Omega (n\log n)$ 이 된다.

복잡도의 하한을 얻는 표준적인 방법은 문제를 다른 문제로 축소하는 것이다. 보다 정확하게, $n$ 크기의 문제 $A$ 를 크기 $f (n)$ 의 문제 $B$ 의 하위 문제로 인코딩할 수 있고, $A$ 의 복잡도가 $\Omega (g(n))$ 라고 가정해 보자. 일반성을 잃지 않고, $f$ 함수가 $n$ 에 따라 증가하며, 역함수 $h$ 를 갖는다고 가정할 수 있다. 그러면 문제 $B$ 의 복잡도는 $\Omega (g(h(n)))$ 이 된다. 이 방법은 P ≠ NP(미해결 추측)인 경우 모든 NP 완전 문제의 복잡도는 모든 양의 정수 $k$ 에 대해 $\Omega (n^{k})$ 임을 증명하는 데 사용되는 방법이다.

알고리즘 설계에 사용

알고리즘의 복잡도를 평가하는 것은 예상되는 성능에 대한 유용한 정보를 제공하기 때문에 알고리즘 설계에서 중요한 부분이다.

현대 컴퓨터의 성능이 기하급수적으로 증가한다는 무어의 법칙으로 인해 알고리즘의 복잡도 평가가 덜 중요해질 것이라는 것은 일반적인 오해이다. 이러한 성능 향상으로 인해 대용량 입력 데이터(빅 데이터)로 작업할 수 있기 때문에 이는 잘못된 생각이다. 예를 들어, 책의 서지 목록과 같이 수백 개의 항목이 나열된 목록을 사전 순으로 정렬하려는 경우, 어떤 알고리즘이든 1초 이내에 잘 작동할 것이다. 반면에 백만 개의 항목(예: 대도시의 전화번호)이 있는 목록의 경우, $O(n^{2})$ 회의 비교가 필요한 알고리즘의 경우, 1조 번의 비교를 수행해야 하며, 초단 천만 번의 비교를 비교를 한다면 약 3시간이 소요된다. 반면 퀵 정렬이나 병합 정렬의 경우 $n\log _{2}n$ 회의 비교로 충분하다. $n = 1,000,000$ 인 경우, 약 30,000,000 회의 비교를 수행해야 하며, 초당 천만 회의 비교를 수행하면 3초밖에 걸리지 않는다.

따라서 복잡도 평가를 통해 구현 전에 많은 비효율적인 알고리즘을 제거할 수 있다. 또한 모든 변형을 테스트하지 않고 복잡한 알고리즘을 튜닝하는 데에도 사용할 수 있다. 복잡한 알고리즘에서 가장 비용이 많이 드는 단계를 결정함으로써 복잡도 연구를 통해 구현의 효율성을 향상시키는 노력을 이러한 단계에 집중하여 개선할 수 있다.