시간 복잡도

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

시간 복잡도는 알고리즘의 효율성을 나타내는 지표로, 입력 크기에 따른 연산 횟수를 의미한다. O(1) (상수 시간)부터 O(2^{2^poly(n)}) (이중 지수 시간)까지 다양한 시간 복잡도가 존재하며, 알고리즘의 수행 시간은 입력 크기에 따라 선형, 로그, 다항, 지수적으로 증가할 수 있다. 시간 복잡도는 알고리즘 설계 및 분석에 중요한 개념이며, 복잡도 클래스 P, NP, ZPP, RP, BPP, BQP 등과 같은 복잡도 클래스와 연관된다.

더 읽어볼만한 페이지

계산 자원 - 계산 복잡도
계산 복잡도는 알고리즘의 효율성을 평가하는 척도로, 시간, 공간 등의 자원을 고려하며, 입력 크기의 함수로 표현되고, 빅 오 표기법을 사용하여 알고리즘의 예상 성능을 파악하는 데 중요한 역할을 한다.
계산 자원 - 공간 복잡도
공간 복잡도는 알고리즘이 문제 해결에 필요한 메모리 공간의 양을 나타내며, DSPACE와 NSPACE는 튜링 기계의 공간 사용량을, PSPACE와 NPSPACE는 다항식 공간 사용 문제를 나타내고, 사비치 정리는 NSPACE와 DSPACE의 관계를 보여주며, LOGSPACE는 O(log n) 공간으로 풀 수 있는 문제의 집합을 의미한다.
알고리즘 분석 - 계산 복잡도
계산 복잡도는 알고리즘의 효율성을 평가하는 척도로, 시간, 공간 등의 자원을 고려하며, 입력 크기의 함수로 표현되고, 빅 오 표기법을 사용하여 알고리즘의 예상 성능을 파악하는 데 중요한 역할을 한다.
알고리즘 분석 - 비결정적 알고리즘
비결정적 알고리즘은 계산 과정에서 여러 선택지를 가질 수 있는 비결정론적 튜링 기계 또는 비결정성을 활용하는 프로그래밍 패러다임인 비결정론적 프로그래밍과 관련된 알고리즘을 포괄적으로 지칭한다.
계산 복잡도 이론 - 양자 컴퓨터
양자 컴퓨터는 양자역학적 현상을 이용하여 정보를 처리하는 컴퓨터로, 큐비트를 통해 0과 1을 동시에 표현하여 특정 연산에서 기존 컴퓨터보다 빠른 속도를 보이며 암호 해독, 신약 개발 등 다양한 분야에 혁신을 가져올 것으로 기대된다.
계산 복잡도 이론 - 선형 시간
선형 시간은 알고리즘의 실행 시간이 입력 크기에 비례하여 증가하는 것을 의미하며, O(n)의 시간 복잡도를 가지는 알고리즘 분석의 중요한 척도로 활용된다.

시간 복잡도
개요
분야	알고리즘
연구 분야	알고리즘 계산 복잡도 이론
관련 주제	점근 표기법, 최악의 경우 및 평균 사례 복잡도, 계산 복잡도, 알고리즘 분석
정의
설명	알고리즘을 실행하는 데 필요한 시간의 양
측정	일반적으로 필요한 단계 수로 측정됨
표현	빅 오 표기법을 사용하여 표현됨
영향 요인	입력 크기 알고리즘 효율성 하드웨어 성능
중요성
설명	알고리즘의 효율성을 평가하고 비교하는 데 중요
활용	알고리즘 선택 시스템 성능 최적화 자원 사용량 예측
점근 표기법
빅 오 표기법 (O)	알고리즘의 최악의 경우 실행 시간을 나타냄
빅 오메가 표기법 (Ω)	알고리즘의 최상의 경우 실행 시간을 나타냄
빅 세타 표기법 (Θ)	알고리즘의 평균 실행 시간을 나타냄
일반적인 시간 복잡도
상수 시간	O(1)
로그 시간	O(log n)
선형 시간	O(n)
로그 선형 시간	O(n log n)
이차 시간	O(n^2)
지수 시간	O(2^n)
계승 시간	O(n!)
예시
선형 탐색	O(n)
이진 탐색	O(log n)
병합 정렬	O(n log n)
퀵 정렬 (최악의 경우)	O(n^2)
추가 정보
주의사항	시간 복잡도는 알고리즘의 성능을 나타내는 중요한 지표이지만, 실제 실행 시간은 하드웨어 및 소프트웨어 환경에 따라 달라질 수 있음

2. 공통 시간 복잡도 표

이름	복잡도 종류	수행 시간 (T(n))	수행 횟수 예시	알고리즘 예시
상수 시간		O(1)	10	정수(이진수로 표현되는)가 짝수이거나 홀수인지 결정
역 아커만 시간		O(α(n))		서로소 집합을 사용한 연산 당 분할상환 시간
반복 로그 시간		O(n)
로그-로그 시간		O(log log n)		유계 우선순위 큐를 사용한 연산 당 분할상환 시간^[30]
로그 시간	DLOGTIME	O(log n)	log n, log(n²)	이진탐색
다항 로그 시간		poly(log n)	(log n)²
분수 지수		O(n^c) where 0 < c < 1	n^1/2, n^2/3	k차원 트리 탐색
선형 시간		O(n)	n	정렬되지 않은 배열에서 가장 작은 수 또는 가장 큰 수를 탐색
"n log^* n" 시간		O(n n)		자이델(Seidel)의 다각형 삼각화 알고리즘
선형 로그 시간		O(n log n)	n log n, log n!	고속 푸리에 변환, 가장 빠른 비교정렬
2차 시간		O(n²)	n²	버블 정렬, 삽입 정렬, 직접적 합성곱
3차 시간		O(n³)	n³	n×n 행렬 두 개의 무식한 곱셈, 편상관계 계산
다항 시간	P	2^O(log n) = poly(n)	n, n log n, n¹⁰	선형 계획법을 위한 카르마카(Karmarkar)의 알고리즘, AKS 소수판별법
준 다항 시간	QP	2^poly(log n)	n^log log n, n^log n	유향 슈타이너 트리 문제에 대해 잘 알려진 O(log² n)-근사 알고리즘
서브 지수함수 (1번째 정의)	SUBEXP	O(2^{n^ε}) for all ε > 0	O(2^{log n^{log log n}})	복잡도의 이론적 추측을 생각했을 때, BPP는 SUBEXP에 포함.
서브 지수함수 (2번째 정의)		2^o(n)	2^{n^1/3}	소인수분해와 그래프 동형에 대해 잘 알려진 알고리즘
지수 시간 (선형 지수)	E	2^O(n)	1.1ⁿ, 10ⁿ	동적 계획법을 사용한 외판원 문제 해결방법
지수 시간	EXPTIME	2^poly(n)	2ⁿ, 2^n²	브루트 포스 탐색을 통한 연쇄 행렬 곱셈의 해결방법
팩토리얼 시간		O(n!)	n!	브루트 포스 탐색을 통한 외판원 문제 해결방법
이중 지수 시간	2-EXPTIME	2^{2^poly(n)}	2^2ⁿ	프레스버거(Presburger) 산술 명제의 진위 여부 결정

2. 1. 상수 시간 (O(1))

어떤 알고리즘의 ''T''(''n'') 값이 입력 크기에 영향을 받지 않는 값으로 제한된다면, 이 알고리즘은 '''상수 시간'''( '''O(1)''' 시간이라고도 함)이라고 할 수 있다. 예를 들어, 배열에서 특정 인덱스의 요소를 찾는 것은 단 하나의 연산만으로 가능하므로 상수 시간이 걸린다.^[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)이다'라는 것과 같으며, 이것이 표준 표기법으로 사용된다.

2. 2. 로그 시간 (O(log n))

Logarithmic time^영어 알고리즘은 `T(n) = O(log n)`일 때를 말한다. 로그의 밑은 빅 오 분류에서 상수 배수로 나타나므로, 로그 시간 알고리즘의 표준 표기법은 `O(log n)`이다.

로그 시간을 사용하는 알고리즘은 주로 이진 트리 연산이나 이진 탐색에서 나타난다.

`O(log n)` 알고리즘은 입력 크기가 커질수록 연산 횟수와 입력 크기의 비율이 감소하고 0에 가까워지므로 매우 효율적인 것으로 간주된다. 입력의 모든 요소에 접근해야 하는 알고리즘은 크기 `n`의 입력을 읽는 데 걸리는 시간이 `n`에 비례하기 때문에 로그 시간을 가질 수 없다.

로그 시간의 예시로 사전 검색이 있다. `n`개의 항목이 알파벳순으로 정렬된 사전 `D`를 생각해보자. `1 ≤ k ≤ n`에 대해, 상수 시간 내에 사전의 `k`번째 항목에 접근할 수 있다고 가정한다. `D(k)`는 이 `k`번째 항목을 나타낸다. 이러한 가정 하에, 단어 `w`가 사전에 있는지 확인하는 것은 로그 시간 내에 가능하다. `D(⌊n/2⌋)`를 보자. 여기서 `⌊ ⌋`는 바닥 함수를 의미한다. 만약 `w = D(⌊n/2⌋)`라면, 즉 단어 `w`가 사전의 정확히 중간에 있다면, 검색이 완료된 것이다. 만약 `w < D(⌊n/2⌋)`라면, 즉 단어 `w`가 사전의 중간 단어보다 알파벳순으로 더 앞선다면, 사전의 왼쪽 절반에서 같은 방식으로 검색을 계속한다. 그렇지 않고 중간 단어보다 뒤에 오는 경우, 사전의 오른쪽 절반에서 검색을 계속한다. 이 알고리즘은 종이 사전에서 항목을 찾는 방법과 유사하다. 결과적으로 알고리즘이 목표 단어에 가까워질수록 사전 내의 검색 공간이 줄어든다.

이진 탐색은 대표적인 로그 시간 알고리즘의 예시이다.^[1]

2. 3. 다항 로그 시간 (O((log n)^k))

폴리로그 시간(Polylogarithmic time) 알고리즘은 입력 크기의 로그 함수의 거듭제곱 형태로 실행 시간이 증가한다. 즉, 어떤 상수 $k$에 대해 실행 시간이 $O((\log n)^k)$인 경우이다. 다른 표현으로는 $O(\log^k n)$으로 나타낼 수 있다.

예를 들어, 행렬 연쇄 곱셈 문제는 병렬 임의 접근 기계에서 폴리로그 시간에 해결될 수 있다.^[5] 또한, 그래프는 삽입/삭제 연산 당 $O(\log^3 n)$ 시간에 동적 연결성 방식으로 평면 그래프 판별을 수행하여 평면 그래프 여부를 판단할 수 있다.^[6]

2. 4. 서브 선형 시간 (o(n))

만약 T(''n'') = o(''n'')이면, 이 알고리즘은 서브-선형시간 동안 작동된다고 말할 수 있다. 특히 이 알고리즘은 O(''n''^1/2)인 Grover 탐색 알고리즘을 포함한다.^[1]

서브-선형 시간 동안 작동하는 전형적인 알고리즘들은 병렬 프로세싱, 비표준 프로세싱을 사용하거나, 입력 구조에 대한 보장된 가정을 갖는다. 그러나 문자열의 처음부터 log(n)번째 비트 위치에서의 한 개의 비트를 갖는 모든 문자열의 집합과 같은 형식 언어는 입력의 모든 비트에 종속적일 수 있고, 서브-선형 시간에 가깝게 계산될 수 있다.

서브-선형 시간 알고리즘이라는 특정 용어는 알고리즘들이 전형적인 일렬 기계 모델에서 작동하며 입력에 대해 우선 가정을 허용하지 않는다는 점에서, 위와는 다른 알고리즘을 지칭한다. 그러나 이 알고리즘들은 랜덤화될 수 있고, 거의 가장 사소한 정도의 태스크들에 대해서는 반드시 랜덤화되어야만 한다.

이러한 알고리즘은 반드시 전체 입력을 읽지 않고 결과를 제공해야 하기 때문에, 이것의 특별함은 상세 명세는 입력에 허용되는 접근에 굉장히 종속적이다. 보통 b₁,..., b_k로 표현되는 이진 문자열에 대해서, 알고리즘이 어떤 i에 대해 b_i의 값을 요청하거나 얻는데 O(1) 시간이 걸린다고 가정할 수 있다.

서브-선형 시간 알고리즘은 보통 랜덤화되며, 오로지 대략적인 해결책만을 제공해준다. 사실, 0만 가지는 이진 문자열의 특성은 (비근사적인) 서브-선형 시간 알고리즘에 의해서 결정될 수 없다는 것을 쉽게 증명할 수 있다. 서브-선형 시간 알고리즘은 특성 테스팅 (Property testing) 조사에서 자연스럽게 나타난다.

2. 5. 선형 시간 (O(n))

시간복잡도가 O(n)이면, 이 알고리즘은 O(n)시간 혹은 선형 시간을 갖는다고 말할 수 있다. 충분히 큰 입력 크기에 대해서 수행시간이 입력 크기에 따라 선형적으로 증가함을 의미한다.^[1] 예를 들어, 리스트의 모든 요소를 더하는 프로시저는 리스트의 길이에 비례하는 시간을 요구한다.

종종 선형 시간은 알고리즘의 이상적인 특성으로 여겨진다. 많은 연구자들이 선형 시간이나 그보다 더 좋은 알고리즘을 만드는 것을 연구해왔다. 이러한 연구는 소프트웨어와 하드웨어적인 방법 모두를 포함한다. 수학적으로, 표준 계산 모델을 사용해 선형 시간을 절대 얻을 수 없는 알고리즘들은 하드웨어적인 관점에서 선형 시간 동안 실행될 수 있다. 이것을 제공하는 병렬식 방법을 이용하는 하드웨어 기술이 존재하며, 예로 내용 주소 지정 메모리와 같은 것이 있다. 이러한 선형시간 개념은 보이어-무어 문자열 검색 알고리즘 및 우코넨 알고리즘과 같은 문자열 매칭 알고리즘에서 사용된다.

정렬되지 않은 배열에서 가장 크거나 작은 항목 찾기, 카데인 알고리즘, 선형 탐색 등은 선형 시간안에 동작하는 알고리즘의 예시이다.^[1]

2. 6. 유사 선형 시간 (O(n log^k n))

어떤 양의 상수 ''k''에 대해서 T(''n'') = '''O(''n'' log^''k''''n'')'''이면, 이 알고리즘은 유사 선형 시간 동안 실행된다고 말할 수 있다. 선형로그 시간은 ''k''=1인 경우이다. 소프트-오 표기법을 사용하면, 이 알고리즘은 Õ(''n'')이다. 유사 선형 시간 알고리즘은 모든 ɛ < 0 에 대해서 O(''n''^1+ɛ)이고, 그러므로 1보다 엄격하게 큰 지수를 가진 n에서의 모든 다항식보다 빠르다.

유사 선형 시간에서 실행되는 알고리즘은 다음과 같다.

In-place 합병 정렬, O(''n'' log²''n'')
퀵 정렬, O(''n'' log ''n'') (랜덤화된 버전에서는 최악의 경우 입력에 대한 평균에서의 선형로그 시간을 수행시간으로 갖는다.)
힙 정렬, O(''n'' log ''n''), 합병 정렬, intro정렬, 이진 트리 정렬, smooth정렬, patience 정렬 등에서의 최악의 경우
고속 퓨리에 변환, O(''n'' log ''n'')
Monge 배열 계산, O(''n'' log ''n'')

2. 7. 선형 로그 시간 (O(n log n))

선형 로그 시간은 ''n'' log ''n'' 형태의 함수, 즉 선형과 로그 항의 곱으로 표현된다. 만약 T(''n'') = O(''n'' log ''n'') 이라면, 해당 알고리즘은 선형 로그 시간 동안 실행된다고 할 수 있다. 선형 로그 항은 선형 항보다는 빠르게 증가하지만, 1보다 큰 지수를 가진 n의 다항식보다는 느리게 증가한다.^[1]

많은 경우 ''n'' log ''n'' 수행 시간은 Θ(log ''n'') 연산을 n번 수행한 결과로 나타난다. 예를 들어, 이진 트리 정렬은 n 크기의 배열에서 각 요소를 하나씩 자가 균형 이진 탐색 트리에 삽입하여 이진 트리를 만든다. 자가 균형 이진 탐색 트리의 삽입 연산에는 O(log ''n'') 시간이 걸리므로, 전체 알고리즘은 선형 로그 시간이 소요된다.^[1]

비교 정렬은 Stirling 근사에 의해 log(''n''!) = Θ(''n'' log ''n'')이 되므로, 최악의 경우 비교 횟수가 최소 선형 로그만큼 필요하다. 또한 T(''n'') = 2T(''n''/2) + O(''n'') 와 같은 재귀 관계에서도 자주 나타난다.^[1]

아래 표는 일반적인 시간 복잡도 종류를 나타낸다.

이름	시간 복잡도	실행 시간 예시	예시 알고리즘
선형 로그 시간	$O(n\log n)$	$n\log n$ , $\log n!$	퀵 정렬, 합병 정렬 과 같은 효율적인 비교 정렬, 고속 푸리에 변환

2. 8. 서브 이차 시간 (o(n^2))

만약 T(''n'') = o(''n''²)이면, 서브-이차 시간 알고리즘이라고 말할 수 있다.^[1]

예를 들어, 간단한 비교 기반 정렬 알고리즘은 이차 시간(예: 삽입 정렬)이지만, 더 심화된 알고리즘은 서브-이차 시간(예: 쉘 정렬)인 것을 찾을 수 있다. 어떤 범용 정렬도 선형 시간에 수행될 수 없지만, 이차에서 서브-이차로의 변경은 대단히 현실적으로 중요하다.^[1]

2. 9. 다항 시간 (O(n^k))

어떤 상수 ''k''에 대해 T(''n'') = O(''n''^k)와 같이, 입력 크기에 어떤 다항 표현의 상한을 가지고 수행되는 알고리즘은 다항 시간을 가진다고 말할 수 있다. 결정론적 다항시간 알고리즘(deterministic polynomical time algorithm)이 존재하는지에 대한 문제들은 계산 복잡도 이론 분야에서 핵심을 차지하는 복잡도 클래스 P에 속한다. Cobham 논제는 다항 시간이 "추적 가능한", "실현 가능한", "효율적인" 또는 "빠른" 과 같은 동의어를 갖는다고 언급한다.^[11]^[12]^[13]

몇 가지 다항 시간 알고리즘의 예는 다음과 같다.

정수 ''n''에 대한 선택 정렬 알고리즘은 상수 ''A''에 대해서 $An^2$ 개의 연산을 수행한다. 따라서 $O(n^2)$ 의 시간 동안 수행되며, 다항시간 알고리즘이라고 할 수 있다.
모든 기본 산술 연산 (덧셈, 뺄셈, 곱셈, 나눗셈 그리고 비교)은 다항시간 동안 이루어진다.
그래프에서의 최대 매칭은 다항 시간 동안 찾을 수 있다.

2. 10. 강력한 다항 시간과 약한 다항 시간

일부 문맥, 특히 최적화에서는 입력이 정수로 구성된 경우 '강력한 다항 시간'과 '약한 다항 시간' 알고리즘을 구분한다.

강력한 다항 시간은 계산의 산술 모델에서 정의된다. 이 모델에서는 피연산자의 크기에 상관없이 기본 산술 연산에 단위 시간이 걸린다. 알고리즘이 다음 두 조건을 만족하면 강력한 다항 시간에 수행된다고 한다.

# 계산의 산술 모델에서 연산 횟수가 입력 인스턴스의 정수 개수에 대한 다항식으로 경곗값이 정해진다.

# 알고리즘이 사용하는 공간이 입력 크기에 대한 다항식으로 경곗값이 정해진다.

이러한 특성을 가진 알고리즘은 산술 연산을 수행하는 적절한 알고리즘으로 대체하여 튜링 머신에서도 다항 시간 알고리즘으로 만들 수 있다. 그러나 두 번째 조건이 충족되지 않으면 다항 시간으로 만드는 것이 불가능하다. 예를 들어, 튜링 머신에서 n에 비례하는 공간을 차지하는 정수

2^n

이 주어졌을 때, 반복 제곱을 사용하여

2^{2^{n}}

을 n번의 곱셈으로 계산할 수 있지만,

2^{2^{n}}

을 표현하는 데 사용되는 공간은

2^n

에 비례하므로 입력 공간은 다항 공간이 아니라 지수 공간이 된다. 따라서 튜링 머신에서 다항 시간에 이 계산의 결괏값을 도출하는 것은 불가능하다.

반대로, 2진 인코딩된 입력 길이로 다항식 경계가 지어진 많은 튜링 머신 단계에서 작동하는 알고리즘들이 있지만, 입력 수의 개수로 다항식 경계가 지어진 많은 산술 연산들은 채택하지 않는다. 두 정수의 최대공약수를 계산하기 위한 유클리드 알고리즘이 그 예이다. 알고리즘의 수행 시간은 주어진 두 정수 a와 b에 대해

O((\log a+\log b)^2)

튜링 머신 단계로 경계를 가지며, a와 b의 이진 표현의 크기는 대략

\log a+\log b

이므로 다항 크기를 갖는다. 그러나 산술 연산 개수는 입력에서의 정수 개수(항상 2개)로 제한될 수 없으므로, 강력한 다항 시간에서 이 알고리즘은 작동할 수 없다.

다항 시간에 작동하지만 강력한 다항 시간은 아닌 알고리즘은 약한 다항 시간 동안에 작동한다고 말할 수 있다. 약한 다항 시간 알고리즘으로 알려졌지만 강력한 다항 시간 알고리즘은 아닌 예로 선형 계획법이 있다. 약한 다항 시간은 유사 다항 시간과 혼동해서는 안 된다.

2. 11. 초다항 시간 (Superpolynomial time)

만약 ''T''(''n'')이 모든 다항식 위에서 경계를 갖지 않는다면, 이것을 초다항 시간이 걸리는 알고리즘이라고 말할 수 있다. 이것은 모든 상수 ''c''에 대해서 n이 입력 파라미터 일 때, ω(''n''^c)시간을 갖는다. (일반적으로, 이 n은 입력값에서의 비트 개수를 뜻한다.)^[1]

예를 들면, 크기 ''n'' 의 입력값에 대해 2^''n''단계 실행되는 알고리즘은 초다항 시간을 요구한다. (좀 더 정확히 말하자면, 지수 시간이다.)^[1]

지수 자원을 사용하는 알고리즘은 분명하게 초다항 시간이지만, 어떤 알고리즘들은 매우 약한 초다항적일 뿐이다. 예를 들어, 애들먼-포머란스-루멜리 소수성 검사는 ''n'' 비트 입력에 대해 시간이 걸린다. 이는 ''n''이 충분히 커지면 어떤 다항식보다 빠르게 증가하지만, 입력 크기는 차수가 작은 다항식에 의해 지배될 수 없을 만큼 비실용적으로 커져야 한다.^[1]

초다항 시간을 필요로 하는 알고리즘은 복잡도 클래스 P 밖에 있다. 코밤의 추론은 이러한 알고리즘이 비실용적이라고 가정하며, 많은 경우에 그렇다. P 대 NP 문제가 해결되지 않았기 때문에, NP-완전 문제가 초다항 시간을 필요로 하는지 여부는 알려져 있지 않다.^[1]

2. 12. 준다항 시간 (Quasi-polynomial time)

준다항 시간 알고리즘은 다항 시간보다는 느리지만, 지수 시간보다는 덜 느린 알고리즘이다. 준다항 시간 알고리즘의 최악의 경우 시간은 어떤 고정된

c > 0

에 대해

2^{O((\log n)^c)}

값을 갖는다.^[15] 만약 준다항 시간 알고리즘 정의에서의 상수

c

가 1과 같다면, 다항 시간 알고리즘을 얻을 수 있고, 1보다 작다면, 서브 선형 시간 알고리즘을 얻을 수 있다.

준다항 시간 알고리즘은 전형적으로 NP-난제 문제에서 다른 문제로의 환원에서 생길 수 있다. 예를 들어, 3SAT이라는 NP-난제 문제를 다른 문제 B로 바꾸는데, 이 문제의 크기가

2^{O((\log n)^c)}

인 경우가 있다. 이런 경우, 이 환원은 문제 B가 NP-난제임을 증명할 수는 없다. 이 환원은 만약 3SAT에 대한 준다항 시간 알고리즘이 없다면, 단지 B에 부합하는 다항 시간 알고리즘이 없다는 것만 보여줄 수 있다.

몇 가지 문제는 준다항 시간 알고리즘이 알려져 있지만, 다항 시간 알고리즘은 알려져 있지 않다. 이러한 문제는 근사 알고리즘에서 발생한다. 가장 유명한 예시는 방향성 슈타이너 트리 문제로, 정점 개수가

n

인 트리에서

O(\log^3 n)

의 근사 인자를 달성하는 준다항 시간 근사 알고리즘이 존재한다. 그러나 다항 시간 알고리즘의 존재를 증명하는 것은 아직 해결되지 않은 문제이다.

다항 시간은 아니지만, 준다항 시간인 다른 해결 계산 문제로는 László Babai에 의한 그래프 동형 문제와 클릭의 합집합과 랜덤 그래프에서 가장 큰 클릭을 찾는 목표를 가지고 있는 planted clique 문제가 있다.

준-다항 알고리즘이 해결가능하긴 하지만, planted clique 문제는 다항 시간 해결방법이 없다고 추측된다. 이 planted clique의 경우는 계산 게임 이론, 특성 테스팅, 기계 학습에서의 다른 여러 문제들의 어려운 정도를 증명하기 위한 ''계산 난제 가정'' (computational hardness assumption) 으로서 사용된다.^[14]

QP 복잡도 클래스는 모두 준다항 시간 알고리즘으로 이루어져 있다. 이것은 다음의 DTIME으로 정의된다.^[15]

:

\mbox{QP} = \bigcup_{c \in \mathbb{N}} \mbox{DTIME}(2^{(\log n)^c})

2. 13. 서브 지수 시간 (Sub-exponential time)

Sub-exponential time^영어 알고리즘은 실행 시간의 로그가 어떤 주어진 다항식보다 작게 증가하는 알고리즘을 의미한다. 모든 ε > 0에 대해 문제를 ''O''(2^{''n''^''ε''}) 시간 안에 해결하는 알고리즘이 존재한다면, 해당 문제는 서브지수 시간에 속한다고 할 수 있다. 이러한 모든 문제들의 집합은 복잡도 클래스 '''SUBEXP'''이며, 이는 DTIME을 사용하여 다음과 같이 정의할 수 있다.^[18]^[19]^[20]^[21]

:

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

이러한 서브지수 개념은 ''ε''가 입력의 일부가 아니고 각 ε이 문제에 대한 자체 알고리즘을 가질 수 있다는 점에서 ''ε''에 관해 비균일적이다.

복잡도 이론에서, P vs. NP 문제는 모든 NP 문제가 다항 시간 알고리즘을 가지는지 묻는다. 3SAT 문제 등과 같이, 모든 알려진 NP-완비 문제 알고리즘들은 지수 시간이 걸린다.

2. 14. 지수 시간 (Exponential time)

어떤 알고리즘의 수행 시간이 입력 크기의 지수 함수로 표현될 때, 이를 지수 시간 알고리즘이라고 한다. 이러한 알고리즘은 복잡도 클래스 EXP에 속한다.

지수 시간 알고리즘은 ''T''(''n'')이 2^poly(''n'')으로 상한이 정해지는데, 여기서 poly(''n'')은 ''n''에 대한 어떤 다항식이다. 더 공식적으로, 어떤 상수 ''k''에 대해 ''T''(''n'')이 ''O''(2^{''n''^''k''})로 제한된다면 지수 시간 알고리즘이라고 할 수 있다. 이러한 문제들은 결정적 튜링 기계에서 복잡도 클래스 EXP를 형성한다.^[1]

:

\text{EXP} = \bigcup_{c \in \mathbb{R_+}} \text{DTIME}\left(2^{n^c}\right)

때때로 지수 시간은 ''T''(''n'') = 2^''O''(''n'')인 알고리즘, 즉 지수가 최대 ''n''의 선형 함수인 경우를 의미하기도 한다. 이는 복잡도 클래스 E를 발생시킨다.^[1]

:

\text{E} = \bigcup_{c \in \mathbb{N}} \text{DTIME}\left(2^{cn}\right)

2. 15. 이중 지수 시간 (Double exponential time)

poly(n)이 n에 대한 어떤 다항식일 때, T(n)이 2^{2^poly(n)}으로 상한이 정해지는 알고리즘은 이중 지수 시간 알고리즘이라고 한다. 이러한 알고리즘들은 2-EXPTIME 복잡도 클래스에 속한다.

:

\mbox{2-EXPTIME} = \bigcup_{c \in \mathbb{N}} \mbox{DTIME}\left( 2^{2^{n^c}}\right)

잘 알려진 이중 지수 시간 알고리즘은 다음과 같다:

프레스버거 산술에 대한 결정 절차
(최악의 경우) 그뢰브너 기저 계산^[27]
실수 닫힌 체에 대한 양자 제거는 최소 이중 지수 시간이 걸린다.^[28]^[29]

3. 복잡도 클래스

복잡도 클래스는 계산 복잡도 이론에서 다루는 중요한 개념으로, 시간 복잡도에 따라 문제들을 분류하는 방법이다. 대표적인 복잡도 클래스는 다음과 같다.

'''P''': 결정적 튜링 기계에서 다항 시간 안에 해결 가능한 결정 문제들의 집합이다.
'''NP''': 비결정적 튜링 기계에서 다항 시간 안에 해결 가능한 결정 문제들의 집합이다.
'''ZPP''': 확률적 튜링 기계에서 다항 시간 안에 오류 확률 0으로 해결 가능한 결정 문제들의 집합이다.
'''RP''': 확률적 튜링 기계에서 다항 시간 안에 단방향 오류(one-sided error)를 가지면서 해결 가능한 결정 문제들의 집합이다.
'''BPP''': 확률적 튜링 기계에서 다항 시간 안에 양방향 오류(two-sided error)를 가지면서 해결 가능한 결정 문제들의 집합이다.
'''BQP''': 양자 튜링 기계에서 다항 시간 안에 양방향 오류를 가지면서 해결 가능한 결정 문제들의 집합이다.

P는 머신 모델 변화에 대해 강건한, 결정적 머신에서 가장 작은 시간 복잡도 클래스이다.^[11]^[12] 주어진 추상 머신은 해당 머신에서 다항 시간 안에 해결 가능한 문제에 해당하는 복잡도 클래스를 가진다.

컴퓨터 과학에서 아직 해결되지 않은 중요한 문제 중 하나는 '''P 대 NP 문제'''이다. 이 문제는 NP에 속하는 모든 문제가 다항 시간 알고리즘을 갖는지, 즉 P에 속하는지 묻는다. 3SAT과 같은 NP-완전 문제에 대해 알려진 대부분의 알고리즘은 지수 시간이 걸린다. 많은 NP-완전 문제가 서브 지수 시간 알고리즘을 갖지 않는다는 추측이 있으며, 이를 지수 시간 가설이라고 한다.^[16]

이름	복잡도 클래스	시간 복잡도	실행 시간 예시	예시 알고리즘
로그 시간	DLOGTIME	$O(\log n)$	$\log n$ , $\log (n^2)$	이진 탐색
다항 시간	P	$2^{O(\log n)}=\text{poly}(n)$	$n^2+n$ , $n^{10}$	선형 계획법을 위한 카르마르카의 알고리즘, AKS 소수성 검사^[2]^[3]
준다항 시간	QP	$2^{\text{poly}(\log n)}$	$n^{\log \log n}$ , $n^{\log n}$	지향 슈타이너 트리 문제에 대한 최상의 알려진 근사 알고리즘, 최상의 알려진 패리티 게임 해결사,^[4] 최상의 알려진 그래프 동형 사상 알고리즘
준지수 시간 (첫 번째 정의)	SUBEXP	$O(2^{n^\epsilon})$ for all $0<\epsilon <1$		EXPTIME(아래 참조)가 MA와 같은 경우가 아니면 BPP를 포함^[18]
지수 시간 (선형 지수 포함)	E	$2^{O(n)}$	$1.1^n$ , $10^n$	동적 계획법을 사용한 외판원 문제 해결
지수 시간	EXPTIME	$2^{\text{poly}(n)}$	$2^n$ , $2^{n^2}$	무차별 대입 검색을 통한 행렬 연쇄 곱셈 해결
이중 지수 시간	2-EXPTIME	$2^{2^{\text{poly}(n)}}$	$2^{2^n}$	프레스버거 산술에서 주어진 명제의 진실성 결정

4. 시간 복잡도와 관련된 추가 정보

시간 복잡도와 관련된 추가 정보는 다음과 같다.

역 아커만 함수 시간: 분할 상환 시간 상호 배타적 집합을 사용하는 연산과 관련되어 있다.^[1]
반복 로그 시간: 매우 느리게 증가하는 시간 복잡도이다. 주기 분산 색칠 알고리즘 등에 사용된다.^[1]
로그-로그 시간: 제한된 우선순위 큐를 사용하는 연산당 분할 상환 시간은 $O(\log\log n)$ 이다.^[1]
팩토리얼 시간: 알고리즘의 시간 복잡도가 팩토리얼 함수 ''n!''에 의해 상한이 정해지는 경우를 말한다. 보고소트가 대표적인 예시이다.^[1]

4. 1. 역 아커만 함수 시간

역 아커만 함수 시간은 분할 상환 시간 상호 배타적 집합을 사용하는 연산과 관련이 있다.^[1]

4. 2. 반복 로그 시간

반복 로그 시간은 매우 느리게 증가하는 시간 복잡도이다. 주기 분산 색칠 알고리즘 등에 사용된다.^[1]

4. 3. 로그-로그 시간

제한된 우선순위 큐를 사용하는 연산당 분할 상환 시간은

O(\log\log n)

이다.^[1]

4. 4. 팩토리얼 시간

팩토리얼 시간은 알고리즘의 시간 복잡도가 팩토리얼 함수 ''n!''에 의해 상한이 정해지는 경우를 말한다. 즉, 입력 크기 ''n''에 대해 알고리즘이 수행하는 연산 횟수가 최대 ''n!''에 비례한다. 팩토리얼 시간은 지수 시간 (EXPTIME)의 부분 집합인데,

n! \leq n^n = 2^{n \log n}= O \left(2^{n^{1 + \epsilon}} \right)

이기 때문이다 (모든

\epsilon > 0

에 대해). 하지만, 팩토리얼 시간은 E의 부분 집합은 아니다.

팩토리얼 시간으로 실행되는 알고리즘의 예시로는 극도로 비효율적인 정렬 알고리즘인 보고소트가 있다.^[1] 보고소트는 시행착오를 기반으로 작동한다. 보고소트는 ''n''개의 항목이 있는 목록을 정렬하기 위해 정렬된 상태가 될 때까지 목록을 반복적으로 셔플한다. 평균적인 경우, 보고소트 알고리즘의 각 패스는 ''n''개의 항목의 ''n''!개의 순서 중 하나를 검사한다. 항목이 서로 다르다면, 그러한 순서 중 오직 하나만이 정렬된다. 보고소트는 무한 원숭이 정리와 유사한 성격을 갖는다.

참조

_[1] 논문 Bounded ordered dictionaries in {{math|''O''(log log ''N'')}} time and {{math|''O''(''n'')}} space
_[2] 서적 An epsilon of room, II: Pages from year three of a mathematical blog American Mathematical Society
_[3] 논문 Primality testing with Gaussian periods https://math.dartmou[...]
_[4] 서적 Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing Association for Computing Machinery 2017
_[5] 논문 Efficient matrix chain ordering in polylog time
_[6] 간행물 Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020 Association for Computing Machinery
_[7] 논문 Sublinear time algorithms http://www.cs.prince[...]
_[8] 간행물 Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing (PODC)
_[9] 논문 On quasilinear-time complexity theory http://www.cse.buffa[...]
_[10] 서적 Algorithms https://algs4.cs.pri[...] Pearson Education
_[11] 서적 Introduction to the Theory of Computation Course Technology Inc
_[12] 서적 Computational complexity Addison-Wesley
_[13] 서적 Proc. Logic, Methodology, and Philosophy of Science II North Holland
_[14] 간행물 Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2017, Barcelona, Spain, Hotel Porta Fira, January 16-19 Society for Industrial and Applied Mathematics
_[15] 문서 Class QP: Quasipolynomial-Time
_[16] 논문 On the complexity of {{mvar|k}}-SAT https://cseweb.ucsd.[...]
_[17] 웹사이트 A not-quite-exponential dilemma http://scottaaronson[...] 2009-04-05
_[18] 논문 BPP has subexponential time simulations unless EXPTIME has publishable proofs Springer-Verlag
_[19] 문서 Class SUBEXP: Deterministic Subexponential-Time
_[20] 간행물 Fundamentals of Computation Theory: 14th International Symposium, FCT 2003, Malmö, Sweden, August 12-15, 2003, Proceedings Springer-Verlag
_[21] 논문 Derandomizing Complexity Classes Kluwer Academic Pub
_[22] 논문 A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem
_[23] arXiv A Subexponential Time Algorithm for the Dihedral Hidden Subgroup Problem with Polynomial Space
_[24] 서적 Surveys in combinatorics 2021 Cambridge University Press
_[25] 서적 Parameterized Complexity Theory https://www.springer[...] Springer
_[26] 논문 Which problems have strongly exponential complexity?
_[27] 논문 The complexity of the word problems for commutative semigroups and polynomial ideals
_[28] 논문 Real quantifier elimination is doubly exponential
_[29] 간행물 Automata Theory and Formal Languages: 2nd GI Conference, Kaiserslautern, May 20–23, 1975 Springer
_[30] 저널 Bounded ordered dictionaries in O(log log N) time and O(n) space

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com