다항 시간
1. 개요
다항 시간은 알고리즘의 실행 시간을 특징짓는 개념으로, 입력 크기에 대한 실행 시간의 증가율이 다항식으로 표현될 수 있는 알고리즘을 의미한다. 어떤 다항식 l(k)가 존재하여, 임의의 k 비트 데이터 x에 대해 알고리즘 A에 x를 입력했을 때 A가 멈출 때까지의 단계 수가 l(k) 이하일 경우, A는 다항 시간 알고리즘으로 간주된다. 결정적 알고리즘과 확률적 알고리즘 모두 다항 시간 알고리즘으로 인정될 수 있으며, 결정적 다항 시간 알고리즘으로 풀 수 있는 판정 문제의 집합을 클래스 P라고 한다. 다항 시간의 종류에는 선형 시간, 제곱 시간, 세제곱 시간 등이 있다.
2. 정의
어떤 문제를 해결하는 데 걸리는 시간이 입력 크기의 다항식으로 표현되는 알고리즘을 다항 시간 알고리즘이라고 한다. 결정적 알고리즘뿐만 아니라 확률적 알고리즘도 포함될 수 있다. 다항 시간 알고리즘으로 풀 수 있는 판정 문제의 집합을 복잡도 클래스 P라고 부른다.
2.1. 다항 시간 알고리즘 (Polynomial Time Algorithm)
어떤 다항식 l(k)가 존재하여, 임의의 k와 임의의 k 비트 데이터 x에 대해, A에 x를 입력했을 때 A가 멈출 때까지의 단계 수가 l(k) 이하일 때, 알고리즘 A를 다항 시간 알고리즘이라고 한다.
다항 시간 알고리즘은 결정적 알고리즘만을 한정하는 경우와 확률적 알고리즘도 허용하는 경우가 있다.
2.2. 복잡도 클래스 P (Complexity Class P)
결정적 다항 시간 알고리즘(위에서 정의된)으로 풀 수 있는 판정 문제의 집합을 P라고 부른다(판정 문제 이외의 문제는 클래스 P에 포함되지 않음에 주의).
3. 다항 시간의 종류
다항 시간 알고리즘의 시간 복잡도는 입력 크기 n에 대한 다항식으로 표현된다.
| 종류 | 설명 |
|---|---|
| 선형 시간 | O(n) |
| 제곱 시간 | O(n2) |
| 세제곱 시간 | O(n3) |
3.1. 선형 시간 (Linear Time)
O(n)
3.2. 제곱 시간 (Quadratic Time)
O(n2)
3.3. 세제곱 시간 (Cubic Time)
알고리즘의 수행 시간이 입력 크기의 세제곱에 비례하여 증가한다. O(n3)으로 표기한다.