시간 복잡도

러닝 타임 (매체) 계산 복잡도 이론에서 **시간 복잡도**는 문제를 해결하는데 걸리는 시간과 입력의 함수 관계를 가리킨다. 컴퓨터과학에서 알고리즘의 시간복잡도는 입력을 나타내는 문자열 길이의 함수로서 작동하는 알고리즘을 취해 시간을 정량화하는 것이다. 알고리즘의 시간복잡도는 주로 빅-오 표기법을 사용하여 나타내며, Pan Bubilek이 빅-오 표기법은 계수와 낮은 차수의 항을 제외시키는 방법이다. 이런 방식으로 표현할 때, (예를 들면, 입력 크기를 무한대로 입력하여) 시간복잡도를 점근적으로 묘사한다고 말한다. 예시로서, 만약 크기 n의 모든 입력에 대한 알고리즘에 필요한 시간이 최대 (어떤 n0보다 크지 않은 모든 n에 대하여) 5*n3* + 3*n*의 식을 가진다면, 이 알고리즘의 점근적 시간 복잡도는 O(*n3*)이라고 할 수 있다. 시간 복잡도는 기본적인 연산을 수행하는데에 어떤 고정된 시간이 걸릴 때, 알고리즘에 의해서 수행되는 기본 연산의 개수를 세어 예측할 수 있다. 그러므로 걸리는 시간의 총량과 알고리즘에 의해 수행되는 기본적인 연산의 개수는 최대 상수 인자만큼 다르다. 알고리즘의 수행 시간은 동일 크기의 다양한 입력에 의해 달라질 수 있기 때문에, 가장 많이 쓰이는 *최악의 시간 복잡도*의 알고리즘 시간을 ***T(n)***이라고 했을 때, 이것은 크기 n의 모든 입력에 대해 걸리는 *최대의 시간*으로 정의할 수 있다. 그 다음으로 덜 흔하게 쓰이면서, 보통 명확하게 서술되는 측정방법은 *평균 시간 복잡도*이다. 시간 복잡도는 함수 T(n)의 특성에 의해 분류할 수 있다. 예를 들면, T(n)=O(n)인 알고리즘은 *선형 시간 알고리즘*이라고 부르며, 몇몇 M ≥ *n* >1에 대해 T(n)=O(Mn)이고 Mn=O(T(n)) 인 알고리즘은 *지수 시간 알고리즘*이라고 한다.
# 공통 시간 복잡도 표
{| class="wikitable sortable" |- ! 이름 !! 복잡도종류!! 수행시간 (*T*(*n*)) !! 수행 횟수 예시 !! 알고리즘 예시 |- | 상수 시간 || || *O*(1) || 10 || 정수(이진수로 표현되는)가 짝수이거나 홀수인지 결정 |- | 역 아커만 시간 (Inverse Ackermann time) || || *O*(α(n)) || || 서로소 집합을 사용한 연산 당 분할상환 시간 |- | 반복 로그 시간 (iterated logarithmic time) || || *O*(log-star *n*) || || |- | 로그-로그 시간 || || *O*(log log *n*) || || 유계 우선순위 큐를 사용한 연산 당 분할상환 시간pages=183–189 |- | 로그 시간 || DLOGTIME || *O*(log *n*) || log *n*, log(*n*2) || 이진탐색 |- | 다항 로그 시간 || || poly(log *n*) || (log *n*)2 || |- | 분수 지수 || || *O*(*n*c) where 0 0 || *O*(2log *n*log log *n*) || 복잡도의 이론적 추측을 생각했을 때, BPP는 SUBEXP에 포함. |- | 서브 지수함수
(2번째 정의) || || 2*o*(*n*) || 2*n*1/3 || 소인수분해와 그래프 동형에 대해 잘 알려진 알고리즘 |- | 지수 시간
(선형 지수) || E || 2*O*(*n*) || 1.1*n*, 10*n* || 동적 계획법을 사용한 외판원 문제 해결방법 |- | 지수 시간 || EXPTIME || 2poly(*n*) || 2*n*, 2*n*2 || 브루트 포스 탐색을 통한 연쇄 행렬 곱셈의 해결방법 |- | 팩토리얼 시간 || || *O*(*n*!) || *n*! || 브루트 포스 탐색을 통한 외판원 문제 해결방법 |- | 이중 지수 시간 || 2-EXPTIME || 22poly(*n*) || 22*n* || 프레스버거(Presburger) 산술 명제의 진위 여부 결정 |}
# 상수 시간 (Constant time)
만약 어떤 알고리즘의 *T*(*n*) 값이 입력 크기에 구애받지 않는 값에 의해서 한정된다면, 이 알고리즘은 **상수 시간**(**O(1)** 시간이라고 쓰기도 함) 이라고 말할 수 있다. 예를 들면, 단 하나의 연산이 어떤 배열에서의 요소 위치를 알아내는 것을 수행한다고 할 때, 이 요소에 접근하는 것은 상수 시간이 걸린다. 그러나 순서가 정해져있지 않은 배열에서의 최소 값을 찾는 것은, 가장 작은 값을 결정하기 위해 어떤 배열에서의 각 요소를 훑는 것이 필요하기 때문에 상수 시간이 아니다. 이것은 그렇기 때문에 선형 시간 연산이며, **O(*n*)**시간이 소요된다. 그러나 만약 요소들의 개수를 미리 알고있고 변화가 없다면, 이러한 알고리즘은 상수 시간에 이루어질 수 있다고 말할 수 있다. "상수 시간"이라는 이름에도 불구하고, *수행시간*은 문제의 크기에 독립적일 필요가 없지만 *수행시간의 상한*은 문제의 크기에 독립적으로 제한된다. 예를 들면, "*필요하다면 a와 b를 바꿔서 a≤b가 되도록 하시오*"와 같은 것은, 시간이 이미 *a≤b*조건 만족여부에 종속적이라고 한다고 해도, 상수 시간을 갖는다고 할 수 있다. 그러나 요구되는 시간이 항상 *최대* *t*인 상수 *t*가 존재하기도 한다. 아래는 상수 시간 동안 수행되는 코드의 예제이다. int index = 5; int item = list[index]; if(조건이 참일 때) then 상수 시간 동안 수행되는 어떤 연산을 실행 else 상수 시간 동안 수행되는 어떤 연산을 실행 for i = 1 to 100 for j = 1 to 200 상수 시간 동안 수행되는 어떤 연산을 실행 만약 T(*n*)이 O(*어떤 상수값*)이라면, 'T(*n*)은 O(1)이다'라는 것과 동등하며, 이것을 표준 표기법으로 사용한다.
# 로그 시간 (Logarithmic time)
만약 T(*n*) = **O(log *n*)** 이라면, 이 알고리즘은 로그 시간이 걸린다고 말할 수 있다. 컴퓨터가 이진수 시스템을 사용하기 때문에, 로그는 밑을 대부분 2로 사용한다. (즉, log2*n*, 때때로는 log *n* 이라고 쓰임.) 그러나, 로그의 밑이 변할 때, loga*n*와 logb*n*는 오로지 *상수 승수*에 따라서만 달라지며 이것은 빅-오 표기법에서는 버림한다; 그러므로 O(log *n*)은 로그의 밑과 상관없이 로그 시간 알고리즘에 대한 표준 표기법이 된다. 로그시간이 걸리는 알고리즘은 이진트리에서의 연산에서나 또는 이진 탐색에서 찾아볼 수 있다. O(log *n*)알고리즘은 인스턴스당 연산이 각 인스턴스에 대해서 최대한 줄어드는 것이 필요하기 때문에, 높은 효율을 갖고 있다고 여긴다. 이런 타입의 가장 쉬운 예제 알고리즘은, 문자열을 절반으로 쪼개어 그 오른쪽의 문자열을 다시 또 절반으로 쪼개고, 이를 반복하는 알고리즘으로 생각할 수 있다. 이 알고리즘은 우리가 각각의 출력 이전에 문자열을 절반으로 나누기 때문에, O(log n)시간 (n은 문자열의 길이) 이 소요된다. 이것은 출력 횟수를 증가시키기 위해서는 문자열의 길이를 두배로 늘려야 함을 의미한다. // 문자열의 오른쪽 절반을 재귀적으로 출력하는 함수. var right = function(str){ var length = str.length; // Helper function var help = function(index){ //재귀호출 부분: 오른쪽 절반을 출력 if(index 0에 대해 2^{O((\log n)^c)} 값을 갖는다. 정수 인수분해에 대해 2^{\tilde{O}(n^{1/3})} 시간이 소요되는 가장 잘 알려진 고전 알고리즘인 *대표 숫자 영역 거르기* (general number field sieve)는 실행 시간이 고정된 c에 대해서 2^{O((\log n)^c)}로 나타낼 수 없기 때문에 준-다항시간 알고리즘이 아니다. 만약 준-다항 시간 알고리즘 정의에서의 상수 c가 1과 같다면, 우리는 다항시간 알고리즘을 얻을 수 있고, 1보다 작다면, 서브 선형 시간 알고리즘을 얻을 수 있다. 준-다항 시간 알고리즘은 전형적으로 NP-난제 문제에서 다른 문제로의 환원에서 생길 수 있다. 예를 들면, NP-난제 문제 하나가 3SAT이고, 이것을 다른 문제 B로 바꾸지만 이 문제의 크기는 2^{O((\log n)^c)}이다. 이런 경우, 이 환원은 문제 B가 NP-난제임을 증명할 수 없다; 이 환원은 만약 3SAT에 대한 준-다항 시간 알고리즘이 없다면, 단지 B에 부합하는 다항시간 알고리즘이 없다는 것만을 보여줄 수 있다. 비슷하게, 우리가 알고있는 준-다항 시간 알고리즘은 몇가지 있지만, 다항 시간 알고리즘은 없다. 이런 문제는 근사 알고리즘에서 발생한다; 가장 유명한 예제는 방향성 Steiner 트리 문제이고, 이 문제는 정점 개수가 n인 트리에서 O(\log^3 n) 의 근사 인자를 달성하는 준-다항 시간 근사 알고리즘이다. 그러나, 다항 시간 알고리즘의 존재를 보여주는 것은 열린 문제이다. 다항시간은 아니지만, 준-다항 시간인 다른 해결 계산 문제들은 László Babai에 의한 그래프 동형 문제와 클릭의 합집합과 랜덤 그래프에서 가장 큰 클릭을 찾는 목표를 가지고 있는 planted clique 문제가 있다. 준-다항 알고리즘이 해결가능하긴 하지만, planted clique 문제는 다항 시간 해결방법이 없다고 추측된다; 이 planted clique의 경우는 계산 게임이론, 특성 테스팅, 기계학습에서의 다른 여러 문제들의 어려운 정도를 증명하기 위한 *계산 난제 가정* (computational hardness assumption) 으로서 사용된다. QP 복잡도 클래스는 모두 준-다항 시간 알고리즘으로 이루어져있다. 이것은 다음의 DTIME으로 정의된다. \mbox{QP} = \bigcup_{c \in \mathbb{N \mbox{DTIME}(2^{(\log n)^c})
## NP-완비문제와의 연관
복잡도 이론에서, 미해결 문제인 P vs. NP문제는 NP문제 모두가 다항 시간 알고리즘인지의 여부를 묻는다. 3SAT문제 등과 같은, 모든 알려진 NP-완비문제 알고리즘들은 지수 시간이 걸린다. 실제로, 서브-지수 시간 알고리즘을 가지지 않는 많은 자연 NP-완비 문제들에 대해 추측이 되어왔다. 여기서 "서브-지수 시간"은 아래 두번째 정의에 표시되어 있다. (반면, 인접 행렬 방법을 사용한 많은 그래프 문제들은 입력 크기가 정점 개수의 제곱이기 때문에, 서브 지수 시간에 해결이 가능하다.) 이러한 k-SAT문제에 대한 가정은 *지수 시간 가정*으로 알려져있다. NP-완비 문제가 준-다항 시간 알고리즘을 갖고있지 않다고 생각되기 때문에, 근사 알고리즘 영역에서 근사적이지 않은 결과는 NP-완비 문제가 준-다항 시간 알고리즘을 갖지 않는다는 가정을 만든다. 예를 들면, 집합 덮개 문제의 비근사적 결과와 같은 것이다.
# 서브-지수 시간 (Sub-exponential time)
서브-지수 시간이라는 용어는 어떤 알고리즘의 수행시간이 다항시간보다 빠르지만 현저히 지수시간 보다는 작게 증가하는 것을 표현하는데 사용한다. 이러한 점에서, 서브-지수 시간 알고리즘은 오로지 지수 알고리즘보다는 다소 더 추적이 가능한 문제들이다. "서브-지수 시간"의 정확한 정의는 동의가 되어있지 않고, 아래의 두 정의가 폭넓게 사용되고 있다.
## 첫 번째 정의
만약 어떤 알고리즘이 주어진 다항식보다 작게 증가하는 수행시간 안에 해결될 수 있다면, 그 문제는 서브-지수 시간이 걸린다고 말한다. 더 정확하게는, 모든 ε > 0에 대해서 O(2nε) 시간에 문제를 해결하는 알고리즘이 존재한다면, 서브-지수 시간 문제이다. 이러한 문제들은 다음과 같이 DTIME으로 정의되는 SUBEXP 복잡도 클래스를 갖는다.

\text{SUBEXP}=\bigcap_{\varepsilon>0} \text{DTIME}\left(2^{n^\varepsilon}\right)
서브-지수 표기법은, 입력 값의 부분이 아니라는 점과 각 ε이 해당 문제만의 알고리즘을 갖고있다는 점에서 ε에 대해 비균일하다.
## 두 번째 정의
어떤 사람들은 2o(*n*) 로 서브-지수 시간을 정의한다. 이 정의는 서브-지수 시간의 첫번째 정의보다는 더 큰 실행 시간이 허용된다. 예제로는, 정수 인수분해하는 가장 잘 알려진 고전 알고리즘인 *대표 숫자 영역 거르기* (general number field sieve) 가 있으며, 이것의 실행 시간은 입력 크기가 n의 길이를 가질 때, 2^{\tilde{O}(n^{1/3})}를 갖는다. 또 다른 예제는 *그래프 동형 문제*로 2^{O(\sqrt{n \log n})}시간이 소요된다. 이것은 알고리즘이 인스턴스의 크기, 정점의 개수 또는 간선의 개수에서 서브-지수가 되는 것을 허용하는 알고리즘인지의 여부에 따라 다르다는 것을 명심하자. *매개변수화 복잡도*에서는, 이러한 차이점이 결정 문제의 (L,k) 페어와 인자 k를 고려하는 것으로서 분명해진다. SUBEPT는, 입력 크기 n일 때 다항이며 k에 대해 서브-지수시간 수행되는 모든 매개변수화 문제의 복잡도 클래스이다. :\text{SUBEPT}=\text{DTIME}\left(2^{o(k)} \cdot \text{poly}(n)\right). 더 정확하게 SUBEPT는 계산 가능한 함수 f : \mathbb N\to\mathbb N with f \in o(k)에 대해서 모든 매개변수화 문제 (L,k) 의 복잡도 클래스이며, 알고리즘은 2^{f(k)} \cdot \text{poly}(n) 시간 동안 L을 결정한다.
# 지수 시간 (Exponential time)
poly(n)이 n에서의 어떤 다항식이라고 할 때, 만약 T(n)이 2poly(n)로 상한이 정해진다면, 이 알고리즘은 지수 시간을 갖는다고 말할 수 있다. 더 형식적으로, 만약 T(n)이 어떤 상수 k에 대해서 O(2^{n{^k)를 갖는다면, 지수 시간을 갖는다. 결정적 튜링 머신에 대해 지수 시간 알고리즘인 문제들은 EXP로 알려져있는 복잡도 클래스를 만든다. EXP = \bigcup_{c\in\mathbb{NDTIME({2^{n{^c) 가끔 지수 시간은 지수가 최대 n의 선형 함수일 때, T(n) = 2O(n)을 갖는 알고리즘으로 사용되기도 하며, 복잡도 클래스 E를 표현한다. E = \bigcup_{c \in \mathbb{N{DTIME}(2^{cn})
# 이중지수 시간 (Double exponential time)
poly(n)이 n에서의 어떤 다항식이라고 할 때, 만약 T(n)이 22poly(n)로 상한이 정해진다면, 이 알고리즘은 이중지수 시간을 갖는다고 말할 수 있다. 이러한 알고리즘들은 2-EXPTIME 복잡도 클래스에 속한다. \mbox{2-EXPTIME} = \bigcup_{c \in \mathbb{N \mbox{DTIME}\left( 2^{2^{n^c\right) 잘 알려진 이중지수 시간 알고리즘은 다음을 포함한다: * Presburger 연산을 위한 결정 과정 * (최악의 경우에서) Grõbner basis 계산 * 닫힌 실수 영역에 대한 한정 기호 제거 (Quantifier elimination)는 최소 이중지수 시간이 걸린다.