시간 복잡도

![Graphs of functions commonly used in the [analysis of algorithms , showing the number of operations N as the result of input size n for each function]]

이론 전산학에서 시간 복잡도는 알고리즘을 실행하는 데 걸리는 컴퓨터 시간의 양을 나타내는 계산 복잡도이다. 시간 복잡도는 일반적으로 알고리즘이 수행하는 기본 연산의 횟수를 세어 추정하며, 각 기본 연산이 수행되는 데 고정된 시간이 걸린다고 가정한다. 따라서 알고리즘이 소요하는 시간과 수행하는 기본 연산의 횟수는 상수 비례 관계에 있는 것으로 간주된다.

알고리즘의 실행 시간은 같은 크기의 서로 다른 입력에 따라 달라질 수 있으므로, 일반적으로 최악의 경우 시간 복잡도를 고려하는데, 이는 주어진 크기의 입력에 대해 요구되는 최대 시간의 양이다. 덜 일반적이며 보통 명시적으로 지정되는 것은 평균적인 경우의 복잡도로, 이는 주어진 크기의 입력에 대해 소요되는 시간의 평균이다(주어진 크기의 가능한 입력은 유한하므로 이는 의미가 있다). 두 경우 모두 시간 복잡도는 일반적으로 입력 크기의 함수로 표현된다.[^2] 이 함수는 일반적으로 정확하게 계산하기 어렵고, 작은 입력에 대한 실행 시간은 보통 중요하지 않으므로, 입력 크기가 증가할 때의 복잡도의 행동, 즉 복잡도의 점근적 행동에 주로 초점을 맞춘다. 따라서 시간 복잡도는 일반적으로 대문자 O 표기법을 사용하여 표현하며, 통상적으로 등으로 나타내는데, 여기서 는 입력을 표현하는 데 필요한 비트 단위의 크기이다.

알고리즘의 복잡도는 대문자 O 표기법에 나타나는 함수의 유형에 따라 분류된다. 예를 들어, 시간 복잡도가 O(n)인 알고리즘은 선형 시간 알고리즘이며, 어떤 상수 \alpha > 0에 대해 시간 복잡도가 O(n^\alpha)인 알고리즘은 다항 시간 알고리즘이다.

일반적인 시간 복잡도 표

다음 표는 흔히 접하는 시간 복잡도 분류의 일부를 요약한 것이다. 표에서 , 즉 x에 대한 다항식이다.

{| class="wikitable sortable" |- ! 이름 !! 복잡도 분류 !! 시간 복잡도 !! 실행 시간 예시 !! 알고리즘 예시 |- | 상수 시간 || || O(1) || 10 || 정렬된 숫자 배열에서 중앙값 찾기. 계산 . |- | 역 애커만 시간 || || O\bigl(\alpha(n)\bigr) || || 분리 집합을 이용한 연산당 분할 상환 시간 |- | 반복 로그 시간 || || O(\log^*n) || || 순환의 분산 색칠 |- | 이중 로그 || || O(\log\log n) || || 유계 우선순위 큐를 이용한 연산당 분할 상환 시간[^5] |- | 로그 시간 || DLOGTIME || O(\log n) || \log n, \log (n^2) || 이진 탐색 |- | 다중 로그 시간 || || \textsf{poly}(\log n) || (\log n)^2 || |- | 분수 거듭제곱 || || O(n^c) where 0<c<1 || \sqrt{n}, n^{\frac{2}{3}} || k-d 트리에서의 범위 탐색 |- | 선형 시간 || || O(n) || , 2n+5 || 정렬되지 않은 배열에서 최솟값 또는 최댓값 찾기. 카데인 알고리즘. 선형 탐색. |- | "n 로그-스타 n" 시간 || || O(n\log^*n) || || 자이델의 다각형 삼각분할 알고리즘. |- | 선형 로그 시간 || || O(n\log n) || n\log n, \log n! || 가능한 가장 빠른 비교 정렬. 고속 푸리에 변환. |- | 준선형 시간 || || n\textsf{poly}(\log n) || n\log^2 n || 다중점 다항식 평가 |- | 이차 시간 || || O(n^2) || n^2 || 거품 정렬. 삽입 정렬. 직접 합성곱 |- | 삼차 시간 || || O(n^3) || n^3 || 두 n\times n 행렬의 단순 곱셈. 편상관 계산. |- | 다항 시간 || P || 2^{O(\log n)}=\textsf{poly}(n) || n^2+n, n^{10} || 선형 계획법을 위한 카르마카르 알고리즘. AKS 소수 판별법[^1][^6] |- | 준다항 시간 || QP || 2^{\textsf{poly}(\log n)} || n^{\log \log n}, n^{\log n} || 유향 슈타이너 트리 문제에 대한 최적 근사 알고리즘, 최적 패리티 게임 해법,[^7] 최적 그래프 동형 알고리즘 |- | 준지수 시간(첫 번째 정의) || SUBEXP || O(2^{n^\epsilon}) for all \epsilon >0 || || EXPTIME(아래 참조)이 MA와 같지 않는 한 BPP를 포함한다.[^4] |- | 준지수 시간(두 번째 정의) || || 2^{o(n)} || 2^{\sqrt[3]{n}} || 정수 인수분해를 위한 최적 고전 알고리즘 이전 최적 그래프 동형 알고리즘 |- | 지수 시간(선형 지수) || E || 2^{O(n)} || 1.1^n, 10^n || 동적 계획법을 이용한 외판원 문제 풀기 |- | 팩토리얼 시간 || || O(n)! = 2^{O(n \log n)} || n!, n^n, 2^{n \log n} || 무차별 대입 탐색을 이용한 외판원 문제 풀기 |- | 지수 시간 || EXPTIME || 2^{\textsf{poly}(n)} || 2^n, 2^{n^2} || 무차별 대입 탐색을 이용한 행렬 연쇄 곱셈 풀기 |- | 이중 지수 시간 || 2-EXPTIME || 2^{2^{\textsf{poly}(n)}} || 2^{2^n} || 프레스버거 산술에서 주어진 명제의 참 거짓 판별 |}

상수 시간

알고리즘의 상수 시간(또한 O(1) 시간이라고도 표기)이란 T(n)(알고리즘의 복잡도)의 값이 입력 크기에 의존하지 않는 값으로 한정되는 경우를 말한다. 예를 들어, 배열에서 임의의 단일 요소에 접근하는 것은 해당 요소를 찾기 위해 단 하나의 연산만 수행하면 되므로 상수 시간이 소요된다. 마찬가지로, 오름차순으로 정렬된 배열에서 최솟값을 찾는 것도 첫 번째 요소이므로 상수 시간이다. 그러나 정렬되지 않은 배열에서 최솟값을 찾는 것은 최솟값을 결정하기 위해 배열의 각 요소를 모두 탐색해야 하므로 상수 시간 연산이 아니다. 따라서 이는 O(n) 시간이 소요되는 선형 시간 연산이다. 다만, 요소의 수가 사전에 알려져 있고 변하지 않는다면, 그러한 알고리즘도 여전히 상수 시간에 실행된다고 말할 수 있다.

"상수 시간"이라는 이름에도 불구하고, 실행 시간이 문제 크기와 무관할 필요는 없지만, 실행 시간의 상한은 문제 크기와 무관해야 한다. 예를 들어, "a \le b가 되도록 필요시 a와 b의 값을 교환하라"는 작업은 이미 a \le b인지 여부에 따라 시간이 달라질 수 있음에도 상수 시간이라고 불린다. 그러나 소요 시간이 항상 최대 특정 상수 이하인 상수가 존재한다.

로그 시간

알고리즘이 로그 시간이 소요된다고 하는 것은 T(n) = O(\log n)인 경우를 말한다. \log_a n과 \log_b n은 상수 배수로 관련되어 있고, 그러한 배수는 빅 O 분류에서 무관하므로, 로그 시간 알고리즘의 표준 표기법은 식에 나타나는 로그의 밑에 관계없이 O(\log n)이다.

로그 시간이 소요되는 알고리즘은 이진 트리에 대한 연산이나 이진 탐색을 사용할 때 흔히 볼 수 있다.

O(\log n) 알고리즘은 매우 효율적인 것으로 간주되는데, 이는 연산 횟수와 입력 크기의 비율이 n이 증가함에 따라 감소하여 0에 수렴하기 때문이다. 입력의 모든 요소에 접근해야 하는 알고리즘은 로그 시간이 될 수 없는데, 크기 n의 입력을 읽는 데 걸리는 시간이 n의 차수이기 때문이다.

로그 시간의 예시로 사전 검색이 있다. 알파벳 순서로 정렬된 n개의 항목을 포함하는 사전 D를 생각해 보자. 1 \le k \le n에 대해, 사전의 k번째 항목에 상수 시간에 접근할 수 있다고 가정하자. D(k)를 이 k번째 항목이라 하자. 이러한 가정 하에서, 단어 w가 사전에 있는지 확인하는 검사는 로그 시간에 수행될 수 있다: D\left(\left\lfloor \frac{n}{2} \right\rfloor\right)를 살펴보자, 여기서 \lfloor;\rfloor는 바닥 함수를 나타낸다. 만약 w = D\left(\left\lfloor \frac{n}{2} \right\rfloor\right)이면—즉, 단어 w가 정확히 사전의 중간에 있다면—검색이 완료된다. 그렇지 않고 w < D\left(\left\lfloor \frac{n}{2} \right\rfloor\right)이면—즉, 단어 w가 전체 사전의 중간 단어보다 알파벳 순서상 앞에 온다면—사전의 왼쪽(즉, 앞쪽) 절반에서 같은 방법으로 검색을 계속하며, 올바른 단어를 찾을 때까지 이를 반복한다. 반대로, 중간 단어 뒤에 온다면 사전의 오른쪽 절반에서 마찬가지로 계속한다. 이 알고리즘은 종이 사전에서 항목을 찾을 때 흔히 사용하는 방법과 유사하다. 결과적으로, 알고리즘이 목표 단어에 가까워질수록 사전 내의 탐색 공간은 줄어든다.

다항로그 시간

알고리즘의 시간 T(n)이 어떤 상수 에 대해 O\bigl((\log n)^k\bigr)일 때, 해당 알고리즘은 다항로그 시간에 실행된다고 한다. 이를 다르게 표기하면 O(\log^kn)이다.

예를 들어, 행렬 연쇄 순서 문제는 병렬 랜덤 접근 기계에서 다항로그 시간에 풀 수 있으며,[^8] 그래프의 평면성 여부는 완전 동적 방식으로 삽입/삭제 연산당 O(\log^3n) 시간에 판별할 수 있다.[^9]

준선형 시간

T(n)=o(n)일 때 알고리즘은 준선형 시간(흔히 sublinear time이라고도 표기)에 실행된다고 한다. 특히 이는 위에서 정의한 시간 복잡도를 가진 알고리즘들을 포함한다.

준선형 시간 알고리즘이라는 구체적인 용어는 일반적으로 입력의 작은 부분을 표본 추출하여 효율적으로 처리함으로써 전체 인스턴스의 속성을 근사적으로 추론하는 무작위 알고리즘을 가리킨다.[^10] 이러한 유형의 준선형 시간 알고리즘은 속성 검사 및 통계학과 밀접하게 관련되어 있다.

알고리즘이 준선형 시간에 실행될 수 있는 다른 환경에는 다음이 포함된다:

• 전체 작업량이 선형 이상이어서 전체 입력을 읽을 수 있지만, 깊이가 준선형인 병렬 알고리즘.
• 입력 구조에 대한 보장된 가정이 있는 알고리즘. 중요한 예로는 데이터 구조에 대한 연산이 있으며, 예를 들어 정렬된 배열에서의 이진 탐색이 이에 해당한다.
• 입력에서 지역 구조를 탐색하는 알고리즘, 예를 들어 1차원 배열에서 극솟값을 찾는 것(이진 탐색의 변형을 사용하여 O(\log(n)) 시간에 풀 수 있다).  이와 밀접하게 관련된 개념으로 지역 계산 알고리즘(LCA)이 있는데, 이 알고리즘은 큰 입력을 받아 유효한 큰 출력에 대한 지역 정보를 질의한다.[^11]

선형 시간

알고리즘의 시간 복잡도가 O(n)일 때, 해당 알고리즘은 선형 시간, 즉 O(n) 시간이 소요된다고 한다. 비공식적으로 이는 실행 시간이 입력 크기에 비례하여 최대 선형적으로 증가한다는 것을 의미한다. 보다 정확히 말하면, 어떤 상수 가 존재하여 크기 의 모든 입력에 대해 실행 시간이 최대 cn이라는 것을 의미한다. 예를 들어, 리스트의 모든 원소를 더하는 절차는 덧셈 시간이 상수이거나 적어도 상수로 한정되는 경우, 리스트의 길이에 비례하는 시간이 필요하다.

선형 시간은 알고리즘이 전체 입력을 순차적으로 읽어야 하는 상황에서 가능한 최선의 시간 복잡도이다. 따라서 선형 시간 또는 최소한 거의 선형 시간을 보이는 알고리즘을 발견하기 위해 많은 연구가 이루어져 왔다. 이러한 연구에는 소프트웨어 및 하드웨어 방법이 모두 포함된다. 병렬성을 활용하여 이를 제공하는 여러 하드웨어 기술이 있다. 그 예로 내용 주소화 메모리가 있다. 이러한 선형 시간의 개념은 보이어-무어 문자열 탐색 알고리즘 및 우코넨 알고리즘과 같은 문자열 매칭 알고리즘에서 사용된다.

준선형 시간

알고리즘이 어떤 양의 상수 에 대해 T(n)=O(n\log^kn)이면 준선형 시간(quasilinear time, 로그 선형 시간(log-linear time)이라고도 함)으로 실행된다고 한다.[^12] 선형로그 시간(linearithmic time)은 k=1인 경우이다.[^13] 소프트 O 표기법을 사용하면 이러한 알고리즘은 \tilde{O}(n)이다. 준선형 시간 알고리즘은 모든 상수 \varepsilon >0에 대해 O(n^{1+\varepsilon })이기도 하며, 따라서 c>1인 항 n^c를 포함하는 시간 한계를 가진 어떤 다항 시간 알고리즘보다도 빠르게 실행된다.

준선형 시간으로 실행되는 알고리즘에는 다음이 포함된다:

• 제자리 병합 정렬, O(n\log^2n)
• 퀵 정렬, O(n\log n), 무작위화 버전에서는 최악의 경우 입력에 대해 기대 실행 시간이 O(n\log n)이다. 비무작위화 버전은 평균 사례 복잡도를 고려할 때만 O(n\log n) 실행 시간을 가진다.
• 힙 정렬, O(n\log n), 병합 정렬, 인트로 정렬, 이진 트리 정렬, 스무스 정렬, 페이션스 정렬 등은 최악의 경우
• 고속 푸리에 변환, O(n\log n)
• 몽주 배열 계산, O(n\log n)
• 쇤하게-슈트라센 곱셈 알고리즘, O(n\log n\log \log n)

많은 경우에 O(n\log n) 실행 시간은 단순히 \Theta (\log n) 연산을 번 수행한 결과이다(표기법에 대해서는 참조). 예를 들어, 이진 트리 정렬은 크기 인 배열의 각 원소를 하나씩 삽입하여 이진 트리를 생성한다. 자가 균형 이진 탐색 트리에서의 삽입 연산이 O(\log n) 시간이 걸리므로, 전체 알고리즘은 O(n\log n) 시간이 걸린다.

비교 정렬은 스털링 근사에 의해 \log (n!)=\Theta (n\log n)이므로 최악의 경우 최소 \Omega (n\log n)번의 비교가 필요하다. 이들은 또한 점화식 T(n) = 2T\left(\frac{n}{2}\right)+O(n)에서 자주 나타난다.

준이차 시간

알고리즘이 T(n)=o(n^2)이면 준이차 시간(subquadratic time)이라고 한다.

예를 들어, 단순한 비교 기반 정렬 알고리즘은 이차 시간이지만(예: 삽입 정렬), 더 발전된 알고리즘은 준이차 시간이 될 수 있다(예: 셸 정렬). 범용 정렬 중 선형 시간으로 실행되는 것은 없지만, 이차에서 준이차로의 변화는 실용적으로 매우 중요하다.

다항 시간

알고리즘의 수행 시간이 알고리즘 입력 크기에 대한 다항식으로 상한이 정해질 때, 즉 어떤 양의 상수 k에 대해 그러한 경우, 해당 알고리즘을 다항 시간 알고리즘이라 한다.[^2][^14] 결정론적 다항 시간 알고리즘이 존재하는 문제들은 복잡도 클래스 P에 속하며, 이는 계산 복잡도 이론의 핵심이다. 코브햄의 명제는 다항 시간이 "다루기 쉬운", "실현 가능한", "효율적인", 또는 "빠른"의 동의어라고 말한다.[^15]

다항 시간 알고리즘의 몇 가지 예:

• n개의 정수에 대한 선택 정렬 알고리즘은 어떤 상수 A에 대해 An^2번의 연산을 수행한다. 따라서 O(n^2) 시간에 실행되며 다항 시간 알고리즘이다.
• 모든 기본 산술 연산(덧셈, 뺄셈, 곱셈, 나눗셈, 비교)은 다항 시간에 수행할 수 있다.
• 그래프에서 최대 매칭은 다항 시간에 찾을 수 있다. 일부 맥락에서, 특히 최적화 분야에서는 강한 다항 시간 알고리즘과 약한 다항 시간 알고리즘을 구별한다.

이 두 개념은 알고리즘의 입력이 정수로 구성된 경우에만 관련이 있다.

복잡도 클래스

다항 시간의 개념은 계산 복잡도 이론에서 여러 복잡도 클래스로 이어진다. 다항 시간을 사용하여 정의되는 몇 가지 중요한 클래스는 다음과 같다.

• P: 결정론적 튜링 기계에서 다항 시간 내에 풀 수 있는 결정 문제의 복잡도 클래스
• NP: 비결정론적 튜링 기계에서 다항 시간 내에 풀 수 있는 결정 문제의 복잡도 클래스
• ZPP: 확률적 튜링 기계에서 오류 없이 다항 시간 내에 풀 수 있는 결정 문제의 복잡도 클래스
• RP: 확률적 튜링 기계에서 단측 오류로 다항 시간 내에 풀 수 있는 결정 문제의 복잡도 클래스
• BPP: 확률적 튜링 기계에서 양측 오류로 다항 시간 내에 풀 수 있는 결정 문제의 복잡도 클래스
• BQP: 양자 튜링 기계에서 양측 오류로 다항 시간 내에 풀 수 있는 결정 문제의 복잡도 클래스

P는 결정론적 기계에서 기계 모델 변경에 대해 강건한 가장 작은 시간 복잡도 클래스이다. (예를 들어, 단일 테이프 튜링 기계에서 다중 테이프 기계로의 변경은 이차적 속도 향상을 가져올 수 있지만, 한 모델에서 다항 시간에 실행되는 모든 알고리즘은 다른 모델에서도 마찬가지이다.) 주어진 추상 기계는 해당 기계에서 다항 시간 내에 풀 수 있는 문제에 대응하는 복잡도 클래스를 가진다.

초다항 시간

T(n)이 어떤 다항식으로도 상한이 정해지지 않는 경우, 즉 모든 양의 정수에 대해 그러한 경우, 해당 알고리즘은 초다항 시간이 소요된다고 정의한다.

예를 들어, 크기 의 입력에 대해 단계를 실행하는 알고리즘은 초다항 시간(더 구체적으로는 지수 시간)이 필요하다.

지수적 자원을 사용하는 알고리즘은 명백히 초다항적이지만, 일부 알고리즘은 매우 약하게만 초다항적이다. 예를 들어, 애들먼-포머랜스-루멜리 소수 판정법은 비트 입력에 대해 시간에 실행된다; 이는 충분히 큰 에 대해 어떤 다항식보다도 빠르게 증가하지만, 작은 차수의 다항식으로 지배할 수 없게 되기 전에 입력 크기가 비현실적으로 커져야 한다.

초다항 시간이 필요한 알고리즘은 복잡도 클래스 P 밖에 위치한다. 코브햄의 명제는 이러한 알고리즘이 비실용적이라고 주장하며, 많은 경우 실제로 그러하다. P 대 NP 문제가 미해결이므로, NP-완전 문제가 초다항 시간을 필요로 하는지는 알려져 있지 않다.

준다항 시간

준다항 시간 알고리즘은 실행 시간이 준다항적 증가를 보이는 알고리즘으로, 다항 시간보다는 느릴 수 있지만 지수 시간보다는 현저히 빠른 유형의 동작이다. 준다항 시간 알고리즘의 최악의 경우 실행 시간은 어떤 고정된 값에 대해 2^{O(\log^c n)}이다. c=1일 때 이는 다항 시간이 되며, c < 1일 때는 부분선형 시간이 된다.

준다항 시간 알고리즘은 알려져 있지만 다항 시간 알고리즘은 알려지지 않은 문제들이 있다. 이러한 문제들은 근사 알고리즘에서 발생한다. 유명한 예로는 유향 슈타이너 트리 문제가 있는데, 이 문제에 대해 O(\log^3 n)의 근사 비율을 달성하는 준다항 시간 근사 알고리즘이 존재하지만(n은 꼭짓점의 수), 그러한 다항 시간 알고리즘의 존재를 보이는 것은 미해결 문제이다.

준다항 시간 해법은 있지만 다항 시간 해법이 알려지지 않은 다른 계산 문제로는 심어진 클리크 문제가 있는데, 이는 클리크와 무작위 그래프의 합집합에서 큰 클리크를 찾는 것이 목표이다. 준다항적으로 풀 수 있음에도 불구하고, 심어진 클리크 문제에는 다항 시간 해법이 없다고 추측되어 왔다. 이 심어진 클리크 추측은 계산 게임 이론, 속성 검사, 기계 학습에서 여러 다른 문제의 난이도를 증명하기 위한 계산 난이도 가정으로 사용되어 왔다.[^16]

복잡도 클래스 QP는 준다항 시간 알고리즘을 가지는 모든 문제로 구성된다. 이는 DTIME을 사용하여 다음과 같이 정의할 수 있다.[^17] \mbox{QP} = \bigcup_{c \in \mathbb{N}} \mbox{DTIME} \left(2^{\log^c n}\right)

NP-완전 문제와의 관계

복잡도 이론에서, 미해결 문제인 P 대 NP 문제는 NP에 속하는 모든 문제가 다항 시간 알고리즘을 가지는지를 묻는다. 3SAT 등과 같은 NP-완전 문제에 대해 알려진 최선의 알고리즘은 모두 지수 시간이 걸린다. 실제로 많은 자연스러운 NP-완전 문제에 대해 부분지수 시간 알고리즘이 존재하지 않는다고 추측된다. 여기서 "부분지수 시간"은 아래에 제시된 두 번째 정의를 의미한다. (반면에, 인접 행렬로 자연스럽게 표현되는 많은 그래프 문제는 입력의 크기가 꼭짓점 수의 제곱이기 때문에 단순히 부분지수 시간에 풀 수 있다.) 이 추측(k-SAT 문제에 대한)은 지수 시간 가설로 알려져 있다.[^3] NP-완전 문제가 준다항 시간 알고리즘을 가지지 않는다고 추측되므로, 근사 알고리즘 분야의 일부 근사 불가능성 결과는 NP-완전 문제가 준다항 시간 알고리즘을 가지지 않는다는 가정을 사용한다. 예를 들어, 집합 덮개 문제에 대한 알려진 근사 불가능성 결과를 참조하라.

준지수 시간

준지수 시간(sub-exponential time)이라는 용어는 어떤 알고리즘의 실행 시간이 임의의 다항식보다는 빠르게 증가할 수 있지만 지수 함수보다는 여전히 상당히 작은 경우를 표현하기 위해 사용된다. 이러한 의미에서 준지수 시간 알고리즘을 가진 문제는 지수 시간 알고리즘만 존재하는 문제보다 다소 다루기 쉽다. "준지수"의 정확한 정의는 일반적으로 합의되어 있지 않으나,[^18] 가장 널리 사용되는 두 가지 정의는 아래와 같다.

첫 번째 정의

어떤 문제의 실행 시간의 로그값이 임의의 주어진 다항식보다 작게 증가한다면, 그 문제는 준지수 시간에 풀 수 있다고 말한다. 더 정확하게는, 모든 에 대해 해당 문제를 시간 O(2nε)에 푸는 알고리즘이 존재하면 그 문제는 준지수 시간에 속한다. 이러한 모든 문제의 집합은 복잡도 클래스 SUBEXP이며, DTIME을 이용하여 다음과 같이 정의할 수 있다.[^4][^19][^20][^21]

\textsf{SUBEXP}=\bigcap_{\varepsilon>0} \textsf{DTIME}\left(2^{n^\varepsilon}\right)

이 준지수의 개념은 ε에 대해 비균일적(non-uniform)인데, 이는 ε이 입력의 일부가 아니며 각 ε마다 해당 문제에 대한 고유한 알고리즘이 존재할 수 있다는 의미이다.

두 번째 정의

일부 저자들은 준지수 시간을 2^{o(n)}의 실행 시간으로 정의한다.[^3][^22][^23] 이 정의는 첫 번째 준지수 시간 정의보다 더 큰 실행 시간을 허용한다. 이러한 준지수 시간 알고리즘의 예로는 정수 인수분해를 위한 가장 잘 알려진 고전적 알고리즘인 일반 수체 체(general number field sieve)가 있으며, 이는 입력의 길이가 일 때 대략 의 시간에 실행된다. 또 다른 예로 그래프 동형 판정 문제가 있었는데, 1982년부터 2016년까지 가장 잘 알려진 알고리즘은 에 문제를 풀었다. 그러나 STOC 2016에서 준다항 시간 알고리즘이 발표되었다.[^24]

알고리즘이 인스턴스의 크기, 정점의 수, 또는 간선의 수에 대해 준지수인지 여부는 차이를 만든다. 매개변수화된 복잡도에서는 결정 문제와 매개변수 k의 쌍 (L,k)을 고려함으로써 이 차이를 명시적으로 나타낸다. SUBEPT는 k에 대해 준지수이고 입력 크기 n에 대해 다항 시간인 모든 매개변수화된 문제의 클래스이다:[^25]

\textsf{SUBEPT}=\textsf{DTIME}\left(2^{o(k)} \cdot \textsf{poly}(n)\right).

더 정확하게는, SUBEPT는 f \in o(k)인 계산 가능한 함수 f : \N \to \N가 존재하고 L을 시간 2^{f(k)} \cdot \textsf{poly}(n)에 결정하는 알고리즘이 존재하는 모든 매개변수화된 문제 (L,k)의 클래스이다.

지수 시간 가설

지수 시간 가설(ETH)은 절당 최대 세 개의 리터럴을 가지는 논리곱 정규형 불 논리식의 충족 가능성 문제인 3SAT가 n개의 변수에 대해 시간 2o(n)에 풀릴 수 없다는 것이다. 더 정확하게는, 어떤 절대 상수 가 존재하여 어떤 결정론적 튜링 기계도 3SAT를 시간 2cn에 결정할 수 없다는 가설이다. m을 절의 수라 할 때, ETH는 임의의 정수 에 대해 kSAT가 시간 2o(m)에 풀릴 수 없다는 가설과 동치이다.[^26] 지수 시간 가설은 P ≠ NP를 함의한다.

지수 시간

알고리즘의 T(n)이 2poly(n)으로 상계되는 경우, 이를 지수 시간이라 하며, 여기서 poly(n)은 n에 대한 다항식이다. 보다 형식적으로, T(n)이 어떤 상수 k에 대해 O(2nk)로 한정되면 해당 알고리즘은 지수 시간이다. 결정론적 튜링 기계에서 지수 시간 알고리즘이 존재하는 문제들은 EXP로 알려진 복잡도 클래스를 형성한다. \textsf{EXP} = \bigcup_{c \in \mathbb{R_+}} \textsf{DTIME}\left(2^{n^c}\right)

때로 지수 시간은 T(n) = 2O(n)인 알고리즘, 즉 지수가 n의 최대 선형 함수인 경우를 지칭하기도 한다. 이로부터 복잡도 클래스 E가 정의된다. \textsf{E} = \bigcup_{c \in \mathbb{N}} \textsf{DTIME}\left(2^{cn}\right)

계승 시간

*T(n)*이 계승 함수 *n!*로 상계되는 경우, 해당 알고리즘을 계승 시간이라 한다. 모든 \epsilon > 0에 대해 n! \leq n^n = 2^{n \log n}= O \left(2^{n^{1 + \epsilon}} \right)이므로, 계승 시간은 지수 시간(EXP)의 부분집합이다. 그러나 E의 부분집합은 아니다.

계승 시간으로 실행되는 알고리즘의 예로는 시행착오에 기반한 악명 높은 비효율적 정렬 알고리즘인 보고정렬(bogosort)이 있다. 보고정렬은 n개 항목의 목록을 정렬될 때까지 반복적으로 섞어서 정렬한다. 평균적으로, 보고정렬 알고리즘의 각 순회는 n개 항목의 n!가지 순서 중 하나를 검사한다. 항목들이 모두 서로 다르다면, 그중 정렬된 순서는 단 하나뿐이다. 보고정렬은 무한 원숭이 정리와 맥을 같이한다.

이중 지수 시간

알고리즘의 T(n)이 22poly(n)으로 상계되는 경우, 이를 이중 지수 시간이라 하며, 여기서 poly(n)은 n에 대한 다항식이다. 이러한 알고리즘은 복잡도 클래스 2-EXPTIME에 속한다. \textsf{2-EXPTIME} = \bigcup_{c \in \N} \textsf{DTIME}\left( 2^{2^{n^c}}\right)

잘 알려진 이중 지수 시간 알고리즘에는 다음이 포함된다:

• 프레스버거 산술의 결정 절차
• 그뢰브너 기저 계산 (최악의 경우[^27])
• 실폐체에서의 한정사 소거는 최소 이중 지수 시간이 소요되며,[^28] 이 시간 내에 수행할 수 있다.[^29]

같이 보기

• L-표기법
• 공간 복잡도

---

참고 문헌

[^1]: Tao, Terence. 여유 공간의 엡실론, II: 수학 블로그 3년차의 페이지들. American Mathematical Society

[^2]: Cite book last=Sipser first=Michael author-link=Michael Sipser title=계산 이론 입문 year=2006 publisher=Course Technology Inc isbn=0-619-21764-2

[^3]: cite journal last1 = Impagliazzo first1 = Russell author1-link = Russell Impagliazzo last2 = Paturi first2 = Ramamohan doi = 10.1006/jcss.2000.1727 issue = 2 journal = [[Journal of Com

[^4]: Cite journal last1=Babai first1=László author1-link = László Babai last2=Fortnow first2=Lance author2-link = Lance Fortnow last3=Nisan first3=N. author3-link = Noam Nisan last4=Wigd

[^5]: Mehlhorn, Kurt. 유계 순서 사전 {{math

[^6]: cite journal last1 = Lenstra first1 = H. W. Jr. author1-link = Hendrik Lenstra last2 = Pomerance first2 = Carl author2-link = Carl Pomerance doi = 10.4171/JEMS/861 issue = 4 journal

[^7]: cite book author = Calude, Cristian S. and Jain, Sanjay and Khoussainov, Bakhadyr and Li, Wei and Stephan, Frank title = 제49회 연례 ACM SIGACT 컴퓨팅 이론 심포지엄 논문집 c

[^8]: cite journal last1 = Bradford first1 = Phillip G. last2 = Rawlins first2 = Gregory J. E. last3 = Shannon first3 = Gregory E. doi = 10.1137/S0097539794270698 issue = 2 journal = [[SIA

[^9]: cite conference last1 = Holm first1 = Jacob last2 = Rotenberg first2 = Eva editor1-last = Makarychev editor1-first = Konstantin editor2-last = Makarychev editor2-first = Yury editor3

[^10]: cite journal last1 = Kumar first1 = Ravi last2 = Rubinfeld first2 = Ronitt author2-link = Ronitt Rubinfeld title = 부분선형 시간 알고리즘 journal = [[SIGACT News]] volume = 34 iss

[^11]: cite book last1=Rubinfeld first1=Ronitt author1-link = Ronitt Rubinfeld date=2019 chapter=지역 계산 알고리즘 title=2019 ACM 분산 컴퓨팅 원리 심포지엄 논문집

[^12]: cite journal last1 = Naik first1 = Ashish V. last2 = Regan first2 = Kenneth W. last3 = Sivakumar first3 = D. doi = 10.1016/0304-3975(95)00031-Q issue = 2 journal = [[Theoretical Comp

[^13]: cite book last1 = Sedgewick first1 = Robert last2 = Wayne first2 = Kevin edition = 4th page = 186 publisher = Pearson Education title = 알고리즘 url = https://algs4.cs.princeton.ed

[^14]: Cite book last=Papadimitriou first=Christos H. author-link=Christos H. Papadimitriou title=계산 복잡도 year=1994 publisher=Addison-Wesley location=Reading, Mass. isbn=0-20

[^15]: Cite book last=Cobham first=Alan author-link=Alan Cobham (mathematician) year = 1965 chapter = 함수의 본질적 계산 난이도 title = 논리학, 방법론 및 과학철학 학회 논문집

[^16]: cite conference last1 = Braverman first1 = Mark author1-link = Mark Braverman (mathematician) last2 = Kun-Ko first2 = Young last3 = Rubinstein first3 = Aviad last4 = Weinstein first4

[^17]: ComplexityZoo Class QP: 준다항 시간 Q#qp

[^18]: 완전히 지수적이지는 않은 딜레마. (2009년 4월 5일)

[^19]: ComplexityZoo Class SUBEXP: 결정론적 준지수 시간 S#subexp

[^20]: 계산 이론의 기초: 제14회 국제 심포지엄, FCT 2003, 스웨덴 말뫼, 2003년 8월 12-15일, 논문집

[^21]: Cite book last1=Miltersen first1=P.B. chapter=복잡도 클래스의 탈무작위화 title=무작위 컴퓨팅 핸드북 publisher=Kluwer Academic Pub year=2001 volume=9 page=843 doi=10.1

[^22]: Cite journal last1=Kuperberg first1=Greg title=이면체 은닉 부분군 문제에 대한 준지수 시간 양자 알고리즘 location=Philadelphia year=2005 journal=SIAM Journal on Compu

[^23]: 다항 공간을 사용한 이면체 은닉 부분군 문제의 준지수 시간 알고리즘

[^24]: cite book last1 = Grohe first1 = Martin last2 = Neuen first2 = Daniel editor1-last = Dabrowski editor1-first = Konrad K. editor2-last = Gadouleau editor2-first = Maximilien edit

[^25]: Cite book last1=Flum first1=Jörg last2=Grohe first2=Martin author2-link = Martin Grohe title = 매개변수화된 복잡도 이론 year = 2006 publisher = Springer url = https://ww

[^26]: Impagliazzo, R.. 어떤 문제가 강한 지수적 복잡도를 가지는가?

[^27]: cite journal last1 = Mayr first1 = Ernst W. author1-link = Ernst Mayr (computer scientist) last2 = Meyer first2 = Albert R. author2-link = Albert R. Meyer doi = 10.1016/0001-8708(82)9004

[^28]: cite journal last1 = Davenport first1 = James H. author1-link = James H. Davenport last2 = Heintz first2 = Joos author2-link=Joos Ulrich Heintz doi = 10.1016/S0747-7171(88)80004-X issue

[^29]: cite conference last = Collins first = George E. author-link = George E. Collins editor-last = Brakhage editor-first = H. contribution = 원통 대수적 분해에 의한 실폐체에 대한 한정사 소거