시간의 복잡성

알고리즘 분석에 일반적으로 사용되는 함수의 그래프로, 각 함수의 입력 크기 n의 결과 연산수 N을 나타냅니다.

컴퓨터 과학에서 시간 복잡도는 알고리즘을 실행하는 데 걸리는 컴퓨터 시간을 설명하는 계산 복잡도입니다.시간 복잡도는 일반적으로 알고리즘에 의해 실행되는 기본 연산의 수를 카운트함으로써 추정되며, 각 기본 연산을 수행하는 데 일정한 시간이 걸린다고 가정합니다.따라서 알고리즘에 의해 실행되는 기본 연산의 수와 소요 시간은 일정한 인자에 의해 관련되는 것으로 간주됩니다.

알고리즘의 실행 시간은 같은 크기의 입력마다 다를 수 있기 때문에 일반적으로 최악의 시간 복잡도, 즉 주어진 크기의 입력에 필요한 최대 시간을 고려합니다.일반적이지 않고 일반적으로 명시적으로 명시되어 있는 것은 평균 케이스 복잡도입니다.평균 케이스 복잡도는 특정 크기의 입력에 걸리는 시간의 평균입니다(이는 특정 크기의 가능한 입력 수가 한정되어 있기 때문에 의미가 있습니다).두 경우 모두 시간 복잡도는 일반적으로 ^[1]^{: 226}입력 크기의 함수로 표현된다.이 함수는 일반적으로 정확하게 계산하기 어렵고 작은 입력에 대한 실행 시간은 대개 중요하지 않기 때문에, 일반적으로 입력 크기가 증가할 때 복잡성의 동작, 즉 복잡성의 점근적 동작에 초점을 맞춘다.따라서 시간 복잡도는 일반적으로 빅 O 표기법( $O(n)$ 으로 $O(n)$ O ( $)\displaystyle$ O ( $n$ $O(n\log n)$ $O(n^{\alpha })$ ( $n$ log $O(n\log n)$ n $O(n\log n)$ $displaystyle$ O ( $n\$ $log$ $O(n\log n)$ n $)},$ O ( $O(n^{\alpha })$ α $)\$ $displaystyle$ O $(n$ $^{\$ alpha $}),$ $O(2^{n})$ ( $2$ $O(2^{n})$ n $O(2^{n})$ $등$ 을 사용하여 표현됩니다..

알고리즘의 복잡도는 빅 O 표기법에 나타나는 함수의 종류에 따라 분류된다.예를 들어 시간 $O(n)$ O $n)$ { $displaystyle$ O $(n)}$ 알고리즘은 $O(n)$ 선형 시간 알고리즘이며, $\alpha >1$ $O(n^{\alpha })$ O $O(n^{\alpha })$ α $)$ { $displaystyle$ $\alpha >1$ O $(n^{\$ alpha $O(n^{\alpha })$ }) 알고리즘은 일정 $\alpha >1$ $>$ 1 { $displaystyle$ \alpha > $1}$ 이다 $O(n^{\alpha })$ $\alpha >1$ .

일반적인 시간 복잡도 표

다음 표에는 일반적으로 발생하는 시간 복잡성의 몇 가지 클래스가 요약되어 있습니다.표에서 폴리(x) = x^O(1), 즉 x의 다항식입니다.

이름.	복잡도 클래스	실행 시간( $T (n))$	실행 시간의 예	알고리즘의 예
일정 시간		$O(1)$	10	정렬된 숫자 배열에서 중위수 값 찾기 계산 $(-1) n$
역아커만 시간		$O{\bigl (}\alpha (n){\bigr}}$		분리 집합을 사용한 작업당 상각 시간
반복 로그 시간		$O(\log^{*}n)$		사이클의 분산 컬러링
로그 메모리		$O(\log \log n)$		제한 우선^[2] 순위 큐를 사용한 작업당 상각 시간
로그 시간	로그 타임	$O(\log n)$	$\log n$ n \ $displaystyle$ \ $log$ n $\log n$ $\log(n^{2})$ $\log(n^{2})$ $\log(n^{2})$ ）{ $displaystyle \ log$ ( $n^$ {2} $)$	바이너리 검색
다산수 시간		${\displaystyle\text{poly}}(\log n)}$	$(\log n)^{2}$
분수 검정력		$O(n^{c})$ $O(n^{c})$ $O(n^{c})$ c $O(n^{c})$ ) { $displaystyle$ O ( $n^$ { $c$ ) 。 $0<c<1$ 서 $O(n^{c})$ $0<c<1$ 0 < $0<c<1$ < $0<c<1$ \ $displaystyle$ 0 < c $< 1$ }	$n^{\frac {1}{2}}$ 2 $($ n $^{\frac {1}{2$ $n^{\frac {2}{3}}$ $($ n $^{\frac {2}{3}})$	kd 트리에서 검색
선형 시간		$O(n)$	$n$ , $2n+5$ + $2n+5$ (\ $displaystyle 2n + 5$ )	정렬되지 않은 배열에서 가장 작은 항목 또는 가장 큰 항목 찾기, Kadane 알고리즘, 선형 검색
"n log-star n" 시간		$O(n\log ^{*}n}$		세이델의 폴리곤 삼각 측량 알고리즘.
선형 결석 시간		$O(n\log n)$	$n\log n$ $\log n!$ log $n\log n$ { $displaystyle$ n \ $log$ n $n\log n$ }, log $\log n!$ { $displaystyle$ \ $log$ n $\log n!$ !}	가능한 한 빠른 비교 정렬, 고속 푸리에 변환.
준선형 시간		$n\text{poly}}(\log n)$
이차 시간		$O(n^{2})$	$n^{2}$	버블 정렬, 삽입 정렬, 다이렉트 컨볼루션
입방 시간		$O(n^{3}}$	$n^{3}$	$n\times n$ 의 n $n\times n$ × $(style$ n $\times$ n $)$ 행렬의 $n\times n$ 단순한 곱셈.편상관 계산 중.
다항식 시간	P	$\displaystyle 2^{O(\log n)}=\text{poly}}(n)}$	$n^{2}+n$ 2 $n^{2}+n$ + $(디스플레이 스타일$ n $^{2}$ + n $n^{2}+n$ $n^{10}$ $($ n $^{10})$	Karmarkar의 선형 프로그래밍 알고리즘; AKS primality^[3]^[4] test
준수명	q p.	$(\displaystyle 2^{\text{poly}}(\log n)})$	$n^{\log \log n}$ log $n^{\log \log n}$ log $n^{\log \log n}$ n \ $display style$ n^ { \ $log$ \ $log$ n $n^{\log \log n}$ } , $n^{\log n}$ log $n^{\log n}$ n $n^{\log n}$ \ $display style$ n^ { \ $log$ n $n^{\log n}$ }	다이렉트 Steiner 트리 문제에 대한 가장 잘 $알려진$ O $(logn 2)$ 근사 알고리즘.
서브비전위 시간 (첫 번째 정의)	서브엑스피	$O(2^{n^{\epsilon }})$ $\epsilon >0$ $O(2^{n^{\epsilon }})$ ( $O(2^{n^{\epsilon }})$ $O(2^{n^{\epsilon }})$ $O(2^{n^{\epsilon }})$ ) $O(2^{n^{\epsilon }})$ $>$ 0 ( \ $displaystyle$ \ $epsilon > 0$ )에 $O(2^{n^{\epsilon }})$ 대해 { $displaystyle$ O ( $2$ ^ { $n$ ^ { \ $epsilon$ } ) }		EXPTIME(아래 참조)이 ^[5]MA와 동일하지 않는 한 BPP가 포함됩니다.
서브비전위 시간 (두 번째 정의)		$2^{o(n)}$	${3} {2^{n}}$	가장 잘 알려진 정수 인수 분해 알고리즘, 이전에는 그래프 동형성을 위한 최상의 알고리즘
지수 시간 (선형 지수 포함)	E	$2^{O(n)}$	$1.1^{n}$ 1 $($ .1 $^{n$ $($ 10 $^{n})$	동적 프로그래밍을 사용하여 출장 세일즈맨 문제 해결
지수 시간	제외 시간	$\displaystyle 2^{\text{poly}}(n)}}$	$($ 2 $^{n$ $($ 2 $^{n^{2}})$	무차별 검색을 통한 매트릭스 체인 곱셈 해결
요인 시간		$O(n)!$	$n!$	무차별 검색을 통한 출장 세일즈맨 문제 해결
이중 지수 시간	2회차	$\displaystyle 2^{{\text{poly}}(n)}}$	$2^{2^{n}}$	Presburger 산술에서 주어진 문장의 진실성 결정

일정한 시간

알고리즘은 ${\textstyle T(n)}$ T( $)$ { $textstyle$ T $(n)}$ 의 ${\textstyle O(1)}$ ${\textstyle T(n)}$ ${\textstyle T(n)}$ 이 입력 크기에 의존하지 않는 값으로 제한될 경우 상수 시간( ${\textstyle O(1)}$ 1 $)$ { $textstyle O$ (1 $)}$ ${\textstyle O(1)}$ 도 함)이라고 합니다.예를 들어 어레이 내의 단일 요소에 액세스하려면 해당 요소를 찾기 위해 한 번의 작업만 수행하면 되므로 일정한 시간이 걸립니다.마찬가지로 오름차순으로 정렬된 배열에서 최소값을 찾는 것이 첫 번째 요소입니다.그러나 배열 내의 각 요소에 대한 스캔이 최소값을 결정하기 위해 필요하므로 순서가 없는 배열 내의 최소값을 찾는 것은 일정한 시간 작업이 아닙니다.따라서 O $)$ { $textstyle$ O $(n)}$ 시간이 ${\textstyle O(n)}$ ${\textstyle O(n)}$ 선형 시간 연산입니다.그러나 요소의 수가 미리 알려져 있고 변경되지 않는 경우에도 이러한 알고리즘은 일정한 시간에 실행된다고 할 수 있습니다.

"정수 시간"이라는 이름에도 불구하고 실행 시간은 문제의 크기와 무관할 필요는 없지만 실행 시간의 상한은 문제의 크기와 무관해야 합니다.예를 들어, 태스크는 "필요에 $따라$ $a$ 와 b의 값을 ${\textstyle a\leq b}$ 하여 ${\textstyle a\leq b}$ 의 ${\textstyle a\leq b}$ b( $텍스트$ 스타일 $a\leq$ b)를 ${\textstyle a\leq b}$ 상수시간이라고 부릅니다.단, ${\textstyle a\leq b}$ 의 b $(텍스트 스타일$ a $\leq$ b ${\textstyle a\leq b}$ 가 이미 true인지 여부에 따라 시간이 달라질 수 있습니다.다만, 항상 t가 $최대$ t가 되도록 일정하게 설정되어 $있습니다$ .

다음으로 일정한 시간에 실행되는 코드 fragment의 예를 나타냅니다.

int index = 5; int item = list[index]; (조건 true)일 경우 일정한 시간에 실행되는 작업을 수행합니다. 그렇지 않으면 i = j = 1 ~ 100에 대해 1 ~ 200에 대해 일정한 시간에 실행되는 작업을 수행합니다.

T $)$ { $displaystyle$ T $(n)}$ 가 $T(n)$ O $({displaystyle$ O $(a$ 인 $경우$ , 여기서 a는 임의의 상수 값이며 $T(n)$ 이는 $T(n)$ n $)$ { $displaystyle T(n$ )}가 $O(1)$ O(1) $O(1)$ { $displaystyle$ O(1 $O(1)$ 인 $T(n)$ $T(n)$ 표기법과 동등합니다.

로그 시간

알고리즘은 T $T(n)=O(\log n)$ ( $T(n)=O(\log n)$ ) $T(n)=O(\log n)$ ( $T(n)=O(\log n)$ n $T(n)=O(\log n)$ ) { $displaystyle$ T ( n ) = $O$ ( \ $log$ n ) $T(n)=O(\log n)$ 。 $\log _{a}n$ a $log_{b}n$ n $displaystyle \log$ _ { $a }$ 및 l $\log _{a}n$ $log_{b}n$ g $log_{b}n$ b n { $displaystyle$ log $_$ { b } $log_{b}n$ n 은 상수 $log_{b}n$ 승수로 관련되며, 이러한 승수 O 와 관련되지 않은 경우 $T(n)=O(\log n)$ O 와 관련되지 않습니다.thic-time 알고리즘은 $T$ 의 식에 나타나는 로그의 밑변에 관계없이 O $O(\log n)$ n $O(\log n)$ )(\ $displaystyle$ O $(\log$ n $))$ 입니다 $O(\log n)$ .

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

O $O(\log n)$ ( $O(\log n)$ n $O(\log n)$ ) \ $displaystyle$ O ( \ $log$ n )알고리즘은 $O(\log n)$ $O(\log n)$ 효율적이라고 간주됩니다.입력크기에 대한 조작수의 비율이 감소하고 n이 $증가$ 하면 0이 되는 경향이 있기 때문입니다. $입력$ 의 모든 요소에 액세스해야 하는 알고리즘은 크기 n의 입력을 읽는 데 걸리는 시간이 n의 $순서$ 이기 때문에 로그 시간이 걸릴 수 없습니다.

사전 검색을 통해 로그 시간의 예를 제시합니다.알파벳 순서로 정렬된 n개의 엔트리가 $포함$ 된 $사전$ D를 생각해 보십시오.1 $1\leq k\leq n$ k $1\leq k\leq n$ n \ $displaystyle$ 1 \ $leq$ k \ $leq$ n $1\leq k\leq n$ , $1\leq k\leq n$ 、 딕셔너리의 k번째 엔트리에 일정한 시간 내에 액세스 할 수 있다고 가정합니다. $)$ { $displaystyle$ D $(k)}$ 는 $D(k)$ 이 k번째 엔트리를 나타냅니다. $이러한$ 가설 하에서 단어 w가 사전에 있는지 여부를 확인하는 테스트는 $D\left(\left\lfloor {\frac {n}{2}}\right\rfloor \right)$ D ( $D\left(\left\lfloor {\frac {n}{2}}\right\rfloor \right)$ n 2 ${\$ ) \ $displaystyle$ D \ $left$ ( \ $lfloor$ \ $floor \$ right $)$ 라고 생각할 수 있습니다 $.$ 여기서 $displaystyle \loor$ \ $rfloor$ \ $right$ $D\left(\left\lfloor {\frac {n}{2}}\right\rfloor \right)$ )는 floor floor 함수를 $\lfloor \;\rfloor$ 나타냅니다 $.$ w $w=D\left(\left\lfloor {\frac {n}{2}}\right\rfloor \right)$ ( $w=D\left(\left\lfloor {\frac {n}{2}}\right\rfloor \right)$ n $w=D\left(\left\lfloor {\frac {n}{2}}\right\rfloor \right)$ ) $w=D\left(\left\lfloor {\frac {n}{2}}\right\rfloor \right)$ { $displaystyle$ w $= D$ \ left ( \ $lfloor$ \ $frac$ { $n$ } {2 $}$ } \ $right$ \ $loor$ \ $right$ 이면 종료됩니다.또는 w $w<D\left(\left\lfloor {\frac {n}{2}}\right\rfloor \right)$ < $w<D\left(\left\lfloor {\frac {n}{2}}\right\rfloor \right)$ ( $w<D\left(\left\lfloor {\frac {n}{2}}\right\rfloor \right)$ n $w<D\left(\left\lfloor {\frac {n}{2}}\right\rfloor \right)$ ) $w<D\left(\left\lfloor {\frac {n}{2}}\right\rfloor \right)$ { $displaystyle$ w < $D$ \ $left$ ( \ $lfloor$ \ $frac$ { $n$ } {2 $}$ } \ $right$ \ $rfloor$ \ $right$ 인 경우 딕셔너리의 왼쪽 절반에서도 동일한 방법으로 검색을 계속합니다.이 알고리즘은 종이 사전에서 항목을 찾는 데 자주 사용되는 방법과 유사합니다.

다산수 시간

알고리즘은 $T(n)$ T $)$ { $displaystyle$ T $(n)}$ 가 $T(n)$ O $log$ n) $)$ {\ $displaystyle O{\bigl(}(\log$ n)^{k $}{\bigr}}$ 일 때 일정 $k$ }일 때 다산술 시간에 실행된다고 합니다.또 다른 $O(\log ^{k}n)$ 은 O $O(\log ^{k}n)$ ( $O(\log ^{k}n)$ k $O(\log ^{k}n)$ $O(\log ^{k}n)$ $){$ $displaystyle$ O $(\log ^{k}n$ 입니다.

예를 들어 병렬 랜덤 액세스 ^[6]머신 상에서 매트릭스 체인 순서를 다산술 시간으로 해결할 수 있으며, 그래프는 삽입/^[7]삭제 동작당 O $O(\log ^{3}n)$ 3 $)\display style$ O $(\log$ ^{ $3}n)}$ 회 $O(\log ^{3}n)$ $O(\log ^{3}n)$ 로 완전히 동적인 방법으로 평면이라고 판정할 수 있다.

준선형 시간

알고리즘은 T $T(n)=o(n)$ ( $T(n)=o(n)$ ) $=$ ( $T(n)=o(n)$ ) { $displaystyle$ T $(n$ )= $o(n$ 인 경우 준선형 시간(종종 철자 하위 선형 시간)에 실행된다고 합니다. 특히 여기에는 위에서 정의한 시간 복잡성을 갖는 알고리즘이 포함됩니다.

정확하지만 하위 선형 시간으로 실행되는 일반적인 알고리즘은 병렬 처리를 사용하거나(NC 행렬 결정식 계산과¹ 같음), 또는 입력 구조에 대한 보장된 가정(대수 시간 이진 검색 및 많은 트리 유지 관리 알고리즘과 같음)을 사용합니다.단, 문자열의 첫 $\log n$ 로그 " $\displaystyle\log$ n $"$ 비트로 나타나는 위치에 1비트가 있는 모든 문자열의 집합과 같은 형식 언어는 입력의 모든 비트에 의존할 수 있지만 선형 이하의 시간으로 계산할 수 있습니다.

특정 용어 준선형 시간 알고리즘은 통상 기존의 시리얼 머신모델에서 실행되며 입력에 ^[8]대한 사전 전제조건은 허용되지 않는다는 점에서 상기와 다른 알고리즘에 예약되어 있습니다.그러나 이러한 작업은 랜덤화할 수 있으며, 실제로 가장 사소한 작업을 제외한 모든 작업에 대해 랜덤화되어야 합니다.

이러한 알고리즘은 입력 전체를 읽지 않고 답을 제공해야 하므로, 그 세부 사항은 입력에 허용된 액세스에 크게 의존합니다.보통 바이너리 $b_{1},...,b_{k}$ $b_{1},...,b_{k}$ 1, $b_{1},...,b_{k}$ . $b_{1},...,b_{k}$ . , b $b_{1},...,b_{k}$ { $displaystyle b_{1},$ ... $b_{k}$ 로 $b_{1},...,b_{k}$ 표시되는 $O(1)$ 입력의 경우 알고리즘은 $O(1)$ O ( $O(1)$ ) $O(1)$ $displaystyle$ O(1 $)}$ 로 요구하여 임의의 $i$ 에 $b_{i}$ b $b_{i}$ i { \ $displaystyle b_{$ i $b_{i}$ }} 의 $b_{i}$ 을 얻을 수 있다고 가정합니다.

준선형 시간 알고리즘은 일반적으로 랜덤화되어 대략적인 해결책만 제공합니다.사실 0(및 1이 없음)만을 가진 이진 문자열의 특성은 (비근사) 준선형 시간 알고리즘에 의해 결정 불가능하다는 것을 쉽게 증명할 수 있다.준선형 시간 알고리즘은 특성 테스트 조사에서 자연스럽게 발생한다.

선형 시간

알고리즘은 O(n $displaystyle$ O $(n$ $)\displaystyle$ O $(n$ 인 $O(n)$ 경우 선형 시간이 $O(n)$ 합니다.공식적으로는 입력 크기에 따라 실행 시간이 최대 선형적으로 증가한다는 것을 의미합니다.보다 정확하게는 크기 $n$ 의 입력마다 실행 시간이 $최대$ $\displaystyle$ cn이 되도록 $cn$ $c$ 가 일정하다는 것을 의미합니다.예를 들어 목록의 모든 요소를 합산하는 절차에서는 추가 시간이 일정하거나 최소한 상수에 의해 제한되는 경우 목록 길이에 비례하는 시간이 필요합니다.

선형 시간은 알고리즘이 입력 전체를 순차적으로 읽어야 하는 상황에서 가능한 가장 좋은 시간 복잡도입니다.따라서 선형 시간 또는 적어도 거의 선형 시간을 나타내는 알고리즘을 발견하는 데 많은 연구가 투자되었다.이 조사에는 소프트웨어와 하드웨어의 방법이 모두 포함되어 있습니다.병렬 처리를 이용하여 이를 실현하는 하드웨어 기술이 몇 가지 있습니다.예를 들면, 컨텐츠 주소 지정이 가능한 메모리가 있습니다.이 선형 시간 개념은 Boyer-Moore 알고리즘 및 Ukkonen 알고리즘과 같은 문자열 매칭 알고리즘에서 사용됩니다.

준선형 시간

한 알고리즘 만약 T(n))O일부 긍정적인 상수 k에{T(n)=O(n\log ^{k}n)\displaystyle}(n로그 k⁡ n)유사 직선형 시간에(또한log-linear 시간이라고 표현했다.) 뛰기;[9]linearithmic 시간이 그 경우 k=1{\displaystyle k=1}.[10]이 알고리즘은 O부터(n) 부드러운 O표기법을 사용하여{\displaystyle{\t다고 한다.ilde{O $}(n$ 준선형 시간 알고리즘은 $\epsilon >0$ displaystyle \ $epsilon$ $>$ 0 $)$ 의 $\epsilon >0$ $O(n^{1+\epsilon })$ 에서 O $O(n^{1+\epsilon })$ $O(n^{1+\epsilon })$ + $)$ )(\ $displaystyle O($ n $^$ $1$ $c>1$ $epsilon$ $\epsilon >0$ })이므로 $O(n^{1+\epsilon })$ $O(n^{1+\epsilon })$ $n^{c}$ > $style 1$ $displaystyle n^{c$ })의 $c>1$ 범위를 포함하는 모든 다항 시간 알고리즘보다 빠르게 실행됩니다 $.$

준선형 시간에 실행되는 알고리즘은 다음과 같습니다.

임플레이스 머지 정렬 $O(n\log ^{2}n)$ $O(n\log ^{2}n)$ ( $O(n\log ^{2}n)$ $O(n\log ^{2}n)$ 2 $O(n\log ^{2}n)$ n $O(n\log ^{2}n)$ ) { $displaystyle$ O ( $n$ \ $log$ ^ ${2$ } n $O(n\log ^{2}n)$ }
Quicksort $O(n\log n)$ $O(n\log n)$ ( $O(n\log n)$ log $O(n\log n)$ n ) $O(n\log n)$ \ $displaystyle$ O ( $n$ \ $log$ n ) $O(n\log n)$ 、 실행시간은 O $O(n\log n)$ ( $O(n\log n)$ $O(n\log n)$ n $O(n\log n)$ ) \ $displaystyle$ O ( $n$ \ $log$ n $O(n\log n)$ )이 $O(n\log n)$ 됩니다.비랜덤화 버전은 평균 대소문자의 복잡성을 고려할 때만 O $O(n\log n)$ log $O(n\log n)$ n $)\displaystyle$ O $(n\log$ n $)$ 의 $O(n\log n)$ 실행시간을 가집니다.
Humpsort, $O(n\log n)$ ( $O(n\log n)$ log $O(n\log n)$ n $){$ $displaystyle$ O ( $n$ \ $log$ n ) $O(n\log n)$ 、 merge sort 、 introsort 、 binary tree sort 、 smooth sort 、 interience sort 、 in in in in in in in in in in 。
고속 푸리에 변환 $O(n\log n)$ $O(n\log n)$ ( $O(n\log n)$ log $O(n\log n)$ n ) { $displaystyle$ O ( $n$ \ $log$ n ) $O(n\log n)$ }
Monge 어레이 계산 $O(n\log n)$ $O(n\log n)$ ( $O(n\log n)$ log $O(n\log n)$ n $O(n\log n)$ ) { $displaystyle$ O ( $n$ \ $log$ n ) }

$O(n\log n)$ 의 경우 O $O(n\log n)$ log $O(n\log n)$ n $)\displaystyle$ O $(n\log$ n $)$ 실행 $O(n\log n)$ 시간은 단순히 $\Theta (\log n)$ n $)\displaystyle \Theta(\log$ n $)$ $연산$ 을 $\Theta (\log n)$ n회 실행한 결과입니다(표기에 대해서는 Big O 표기법 패밀리 참조).예를 들어 바이너리 트리 정렬은 n사이즈 배열의 각 요소를 하나씩 삽입하여 바이너리 트리를 만듭니다.셀프밸런싱 바이너리 검색 트리의 삽입 조작은 O $O(\log n)$ n $)$ { $displaystyle$ O $(\log$ n)}시간이 $O(\log n)$ $O(\log n)$ 때문에 알고리즘 전체가 O $O(n\log n)$ log $O(n\log n)$ n $)$ { $displaystyle$ O $(n\log$ n $)}$ 시간이 $O(n\log n)$ $O(n\log n)$ .

로그 $\log(n!)=\Theta (n\log n)$ ( $\log(n!)=\Theta (n\log n)$ log $\log(n!)=\Theta (n\log n)$ $)\$ $\log(n!)=\Theta (n\log n)$ \ $\log(n!)=\Theta (n\log n)$ ( n \ $log$ n $log$ ( n $log$ $\log(n!)=\Theta (n\log n)$ n )\ $displaystyle$ \ $log$ ( $n!)$ 이므로 $\log(n!)=\Theta (n\log n)$ 의 경우 비교 정렬에는 최소 $\Omega (n\log n)$ ( $\Omega (n\log n)$ log ⁡ n )의 비교가 $\Omega (n\log n)$ 필요합니다. $=\Theta (n\log$ n $\log(n!)=\Theta (n\log n)$ 스털링 근사치.또한 이들은 종종 반복 ${\textstyle T(n)=2T\left({\frac {n}{2}}\right)+O(n)}$ T ( ${\textstyle T(n)=2T\left({\frac {n}{2}}\right)+O(n)}$ ) ${\textstyle T(n)=2T\left({\frac {n}{2}}\right)+O(n)}$ ${\textstyle T(n)=2T\left({\frac {n}{2}}\right)+O(n)}$ ( n 2 ${\textstyle T(n)=2T\left({\frac {n}{2}}\right)+O(n)}$ ) + ${\textstyle T(n)=2T\left({\frac {n}{2}}\right)+O(n)}$ ( n ${\textstyle T(n)=2T\left({\frac {n}{2}}\right)+O(n)}$ ) { $textstyle$ T ( n ) = $2T \$ left ( { \ $frac$ { $n$ } {2 $} }$ + $O$ ( $n$ ) ${\textstyle T(n)=2T\left({\frac {n}{2}}\right)+O(n)}$ } 에서 발생합니다.

이차 시간

알고리즘은 T $T(n)=o(n^{2})$ ( $T(n)=o(n^{2})$ ) $=$ ( $T(n)=o(n^{2})$ 2) $T(n)=o(n^{2})$ { $displaystyle$ T $(n$ )= $o(n^{2$ 이면 2차 시간 이하라고 한다.

예를 들어 단순한 비교 기반 정렬 알고리즘은 2차(예: 삽입 정렬)이지만, 하위 2차(예: 셸 정렬)인 고급 알고리즘을 찾을 수 있습니다.선형 시간에 실행되는 범용 정렬은 없지만 2차에서 2차로의 변경은 실질적으로 매우 중요합니다.

다항식 시간

알고리즘은 그 실행시간이 알고리즘에 대한 입력크기의 다항식, 즉 어떤 양의 상수 ^[1]^[11]k에 대해 T(n) = O(n^k)에 의해 상한으로 제한될 경우 다항시간이라고 한다.결정론적 다항식 시간 알고리즘이 존재하는 문제는 복잡도 클래스 P에 속하며, 이것은 계산 복잡도 이론의 분야에서 중심이다.코밤의 논문은 다항식 시간이 "처리 가능", "실현 가능", "효율적" 또는 "빠른"^[12]의 동의어라고 말한다.

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

n개의 정수에 대한 선택 정렬 정렬 알고리즘은 일부 상수 A에 대해 $An^{2}$ $An^{2}$ 2 $An^{2}$ {\ $displaystyle$ An $^{2}}$ 연산을 $An^{2}$ $An^{2}$ 합니다. $O(n^{2})$ 시간 O $O(n^{2})$ 2 $)({displaystyle$ O $(n^{2})})$ 에 $O(n^{2})$ 실행되며 다항식 시간 알고리즘입니다.
모든 기본 산술 연산(더하기, 빼기, 곱하기, 나누기 및 비교)을 다항식 시간으로 수행할 수 있습니다.
그래프의 최대 일치 수는 다항식 시간으로 확인할 수 있습니다.

강약 다항식 시간

어떤 상황에서는 특히 최적화에서 강한 다항 시간과 약한 다항 시간 알고리즘을 구별한다.이 두 개념은 알고리즘에 대한 입력이 정수로 구성된 경우에만 관련이 있습니다.

강한 다항식 시간은 계산의 산술 모델에서 정의된다.이 계산 모델에서 기본 산술 연산(더하기, 빼기, 곱하기, 나눗셈 및 비교)은 피연산자의 크기에 관계없이 단위 시간 단계를 수행합니다.알고리즘은 다음과 같은 ^[13]경우 강력한 다항식 시간으로 실행됩니다.

계산의 산술 모델에서 연산 횟수는 입력 인스턴스의 정수 수에서 다항식으로 제한된다.
알고리즘에 의해 사용되는 공간은 입력 크기의 다항식으로 제한된다.

이들 2가지 특성을 가진 알고리즘은 튜링 머신 상에서 산술 연산을 실행하기 위한 적절한 알고리즘에 의해 산술 연산을 대체함으로써 다항 시간 알고리즘으로 변환할 수 있다.두 번째 조건은 엄격히 필요하다. ( $2^{n}$ 기계 모델에서 n에 비례하는 공간을 차지하는) 정수 $2^{n}$ (\ $displaystyle$ 2 $^{n})$ 이 주어지면 반복 제곱을 사용하여 n의 곱셈으로 $(\$ 2 $^{2^{n})$ 을 $2^{2^{n}}$ $2^{2^{n}}$ 할 수 있다.단, $({$ 2 $^{n})$ 을 $2^{2^{n}}$ 나타내는 데 사용되는 $2^{2^{n}}$ 은 $({$ 2 $^{n$ 에 비례하므로 입력 표현에 사용되는 공간에서는 다항식이 아니라 지수이다.따라서 튜링 기계에서는 다항식 시간에 이 계산을 수행할 수 없지만, 다항식적으로 많은 산술 연산을 통해 계산할 수 있다.

그러나 첫 번째 조건에는 이진 부호화된 입력의 길이에서 다항식으로 묶인 다수의 튜링 기계 단계에서 실행되는 알고리즘이 있지만 입력 숫자의 수에서 다항식으로 묶인 다수의 산술 연산을 취하지 않는다.두 정수의 최대공약수를 계산하는 유클리드 알고리즘이 하나의 예이다.2개의 $정수$ a $(\displaystyle$ a $)$ 와 $a$ b $O(\log a+\log b)$ $displaystyle$ b $b$ 를 지정하면 알고리즘은 O(log $O(\log a+\log b)$ + log b $)$ $O(\log a+\log b)$ 비트가 $O(\log a+\log b)$ $O(\log a+\log b)$ O(\ $displaystyle$ $O(\log a+\log b)$ a + $log$ $O(\log a+\log b)$ b $)$ 인 숫자에 대해 O $O(\log a+\log b)$ $log a$ $O(\log a+\log b)$ + $O(\log a+\log b)$ log $b$ b)의 산술 $O(\log a+\log b)$ 연산을 $O(\log a+\log b)$ 합니다.동시에 산술 연산의 수는 입력의 정수 수로 제한될 수 없습니다(이 경우 항상 2개의 정수만 있음).후자의 관측치 때문에 알고리즘은 강한 다항식 시간 내에 실행되지 않습니다.실제 실행 시간은 입력 내의 정수 수뿐만 아니라 $a$ 와 $a$ $b$ 의 $b$ $크기$ (비트 $단위$ 길이 $)$ 에 따라 로그적으로 달라집니다.

다항식 시간에 실행되지만 강한 다항식이 아닌 알고리즘은 약한 다항식 시간에 ^[14]실행된다고 합니다.약한 다항 시간 알고리즘이 알려져 있지만 강한 다항 시간 알고리즘을 인정하지 않는 문제의 잘 알려진 예는 선형 프로그래밍입니다.약 다항식 시간은 문제의 값의 크기에 선형으로 의존하며 실제로는 다항식 시간이 아닌 의사 다항식 시간과 혼동해서는 안 된다.

복잡도 클래스

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

P: 결정론적 튜링 기계에서 다항식 시간에 풀 수 있는 결정 문제의 복잡도 클래스
NP: 결정론적 튜링 기계에서 다항식 시간에 풀 수 있는 결정 문제의 복잡도 클래스
ZPP: 다항식 시간에 확률론적 튜링 기계에서 제로 에러로 해결할 수 있는 결정 문제의 복잡도 클래스
RP: 다항식 시간에 확률론적 튜링 기계에서 단측 오류로 해결할 수 있는 결정 문제의 복잡도 클래스.
BPP: 다항식 시간에 확률론적 튜링 기계에서 양면 오류로 해결할 수 있는 결정 문제의 복잡도 클래스
BQP: 양자 튜링 기계에서 다항식 시간에 양면 오차로 해결할 수 있는 결정 문제의 복잡도 클래스

P는 결정론적 기계에서 가장 작은 시간 복잡도 클래스이며 기계 모델 변경 측면에서 견고하다. (예를 들어 싱글 테이프 튜링 기계에서 멀티 테이프 기계로 변경하면 2차 속도 향상을 가져올 수 있지만, 한 모델에서 다항 시간으로 실행되는 알고리즘은 다른 모델에서도 그렇게 한다.)주어진 추상 기계는 그 기계에서 다항식 시간에 해결할 수 있는 문제에 대응하는 복잡도 클래스를 가집니다.

초다항 시간

알고리즘은 T(n)가 위의 어떤 다항식에 의해 제한되지 않을 경우 초다항 시간을 갖도록 정의된다.작은 오메가 표기법을 사용하면 모든 상수 c에 대해 µ(n^c) 시간이 됩니다.여기서 n은 입력 파라미터로 일반적으로 입력 비트수입니다.

예를 들어 크기가 n인 입력에서 두 단계 동안 실행되는ⁿ 알고리즘에는 초다항 시간(구체적으로는 지수 시간)이 필요합니다.

지수 리소스를 사용하는 알고리즘은 분명히 초다항식이지만, 일부 알고리즘은 매우 약하게만 초다항식입니다.예를 들어 Adleman – Pomerance – Rumely primality 테스트는 n비트 입력에 대해 n시간 동안 실행됩니다^{O(log log n)}. 이것은 충분히 큰 n에 대해 어떤 다항식보다 빠르게 증가하지만 입력 크기가 실제적으로 커야 작은 정도의 다항식이 지배할 수 있습니다.

초다항 시간이 필요한 알고리즘은 복잡도 클래스 P 밖에 있습니다.코밤의 논문은 이 알고리즘들이 실용적이지 않다고 가정하고 있으며, 많은 경우 현실적이다.P 대 NP 문제는 해결되지 않았기 때문에 NP-완전 문제가 초다항 시간을 필요로 하는지는 알 수 없습니다.

준다항 시간

준다항식 시간 알고리즘은 다항식 시간보다 더 오래 실행되지만 지수 시간만큼 길지는 않은 알고리즘입니다.준시간 알고리즘의 최악의 실행 시간은 $2^{O(\log ^{c}n)}$ $c>0$ c $c>0$ $2^{O(\log ^{c}n)}$ 2 $^{O(\log$ ^{ $c}n})$ 입니다 $2^{O(\log ^{c}n)}$ .일부 $c>0$ c > 0 { $displaystyle$ c > $0$ 의 경우, $c<1$ $=$ $c=1$ { $displaystyle c=$ 1 $c=1$ $c<1$ }의 경우, 서브선형 시간 알고리즘을 얻을 수 있습니다.

준다항 시간 알고리즘은 일반적으로 NP-hard 문제에서 다른 문제로 감소하면서 발생합니다.예를 들어 NP 하드 문제의 인스턴스를 예를 들어 3SAT로 변환하여 다른 문제B의 인스턴스로 변환할 수 있지만 인스턴스의 크기는 $log c n$ n $2^{O(\log ^{c}n)}$ 가 됩니다.이 경우 문제 B가 NP 하드인 것을 증명하는 것은 아닙니다.이러한 감소는 폴리 감소뿐입니다.3SAT(따라서 모든 NP)에 대한 준다항 시간 알고리즘이 없는 한 B에 대한 mial time 알고리즘.마찬가지로, 준다항 시간 알고리즘을 알고 있는 몇 가지 문제가 있지만 다항 시간 알고리즘은 알려져 있지 않다.그러한 문제는 근사 알고리즘에서 발생한다. 유명한 예는 O $O(\log ^{3}n)$ $O(\log ^{3}n)$ µ n)의 $O(\log ^{3}n)$ 계수를 달성하는 준다항식 $시간$ 근사 알고리즘( $n은$ 정점 수 $)$ 이 있지만, 그러한 다항식 ti의 존재를 보여주는 방향성 스타이너 트리 문제이다 $.$ Me 알고리즘은 해결되지 않은 문제입니다.

준다항식 시간 해법이 있지만 알려진 다항식 시간 해법이 없는 다른 계산 문제에는 집단과 랜덤 그래프의 결합에서 큰 집단성을 찾는 것이 목표인 심어진 집단 문제가 포함된다.준다항식적으로 해결이 가능하지만, 심어진 clique 문제는 다항식 시간 해답이 없다고 추측되어 왔다. 이 심어진 clique 추측은 계산 게임 이론, 속성 테스트 및 기계 ^[15]학습에서 다른 여러 문제의 어려움을 증명하기 위해 계산 경도 가정으로 사용되어 왔다.

복잡도 클래스 QP는 준다항 시간 알고리즘을 가진 모든 문제로 구성됩니다.DTIME의 관점에서 다음과 ^[16]같이 정의할 수 있습니다.

{\displaystyle\mbox{Q}P}}=\bigcup _{c\in\mathbb {N}}{\mbox{D}TIME}}\left(2^{\log^{c}n}\right)}

NP-완전 문제와의 관계

복잡도 이론에서, 해결되지 않은 P 대 NP 문제는 NP의 모든 문제가 다항식 시간 알고리즘을 가지고 있는지 여부를 묻습니다.3SAT와 같은 NP-완전 문제에 대해 가장 잘 알려진 알고리즘은 모두 기하급수적인 시간이 걸립니다.실제로, 많은 자연 NP-완전 문제에 대해 서브 지수 시간 알고리즘이 없는 것으로 추측됩니다.여기서 "sub-exponential time"은 아래에 제시된 두 번째 정의를 의미합니다.(반면, 인접 행렬에 의해 자연스러운 방식으로 표현되는 많은 그래프 문제는 단순히 입력의 크기가 정점 수의 제곱이기 때문에 sub-exponential time으로 해결할 수 있습니다.)이러한 추측(k-SAT 문제에 대한)을 지수 시간 ^[17]가설이라고 합니다.NP-완전 문제에는 준다항 시간 알고리즘이 없는 것으로 추측되기 때문에, 근사 알고리즘 분야에서 일부 비근접성 결과는 NP-완전 문제가 준다항 시간 알고리즘을 가지고 있지 않다고 가정한다.예를 들어, 세트 커버의 문제에 대해서는, 기존의 비확장성 결과를 참조해 주세요.

하위 지수 시간

하위 지수 시간이라는 용어는 일부 알고리즘의 실행 시간이 어떤 다항식보다 빠르게 증가할 수 있지만 여전히 지수보다 상당히 작다는 것을 표현하기 위해 사용됩니다.그런 의미에서, 지수 이하의 시간 알고리즘을 가지는 문제는 지수 알고리즘만을 가지는 문제보다 어느 정도 다루기 쉽다.서브 지수(sub-exponential)의 정확한 정의는 일반적으로 ^[18]합의되지 않으며, 가장 널리 사용되는 두 가지를 아래에 열거한다.

첫 번째 정의

어떤 문제는 주어진 다항식보다 로그가 작은 실행 시간 내에 해결된다면 서브 지수 시간 해결이 가능하다고 한다.보다 정확하게는, 「」> 0 마다, 시간 O(2)로^{n^ε} 문제를 해결하는 알고리즘이 존재하는 경우, 서브 지수 시간에 문제가 있는 것입니다.이러한 모든 문제의 집합이 복잡도 클래스 SUBEXP이며,^[5]^[19]^[20]^[21] 다음과 같이 DTIME으로 정의할 수 있습니다.

디스플레이 스타일SUBEXP}=\bigcapabit _{\varepsilon >0}{\text{DTIME}}\left(2^{n^{\varepsilon}}\right)}

이 서브지수 개념은 θ가 입력의 일부가 아니며 각 θ가 문제에 대한 자체 알고리즘을 가질 수 있다는 점에서 θ의 관점에서 통일되지 않습니다.

두 번째 정의

일부 저자는 서브지수 $2^{o(n)}$ 을 $2^{o(n)}$ ( $2^{o(n)}$ n $)(\$ n $2^{o(n)}$ ^[17]^[22]^[23]의 $2^{o(n)}$ 시간으로 정의합니다.이 정의를 사용하면 서브 지수 시간의 첫 번째 정의보다 더 큰 실행 시간이 허용됩니다.이러한 서브지수 시간 알고리즘의 예로는 가장 잘 알려진 정수 인수분해 알고리즘인 일반 수 필드 체가 있습니다.일반 수 필드 체는 약 $2^{{\tilde {O}}(n^{1/3})}$ ~ $2^{{\tilde {O}}(n^{1/3})}$ ( $2^{{\tilde {O}}(n^{1/3})}$ / $2^{{\tilde {O}}(n^{1/3})}$ ) $2^{{\tilde {O}}(n^{1/3})}$ { $displaystyle$ 2 $^{\tilde {O$ 의 시간으로 실행됩니다.여기서 입력의 $길이$ 는 $n입니다.$ 또 다른 예로는 1982년부터 2016년까지 가장 잘 알려진 알고리즘이 $displaystyle$ 2 $^{O\left({\sqrt {n\log$ n $}}})})$ 로 $해결$ 된 그래프 $2^{O\left({\sqrt {n\log n}}\right)}$ 동형성 $2^{O\left({\sqrt {n\log n}}\right)}$ 가 있다. 그러나 STOC 2016에서는 준다항식 시간 알고리즘이 ^[24]제시되었다.

인스턴스 크기, 정점 수 또는 에지 수에서 알고리즘이 지수 미달로 허용되는지 여부가 달라집니다.매개 변수화된 복잡도에서 이러한 차이는 결정 문제와 매개 변수 k의 쌍 $, k )$ 을 $(L,k)$ 고려함으로써 명백해진다. SUBEPT는 k에서 시간 하위 지수 및 입력 크기 ^[25]n에서 다항식으로 실행되는 모든 매개 변수화된 문제의 클래스이다.

디스플레이 스타일SUBEPT}}= 텍스트{DTIME}}\left(2^{o(k)}\cdot {text{poly}}(n)\오른쪽).}

보다 정확하게 말하면 SUBEPT는 $f\in o(k)$ 파라미터화된 문제 $(L,k)$ $(L,k)$ ) {displaystyle $(L,$ k $f\in o(k)$ { $displaystyle$ (L, $k$ $)}$ {\ $displaystyle$ f $:\$ $mathbb {N}$ \ $to$ $\$ $mathbb$ ${N})$ 의 $f:\mathbb {N} \to \mathbb {N}$ $f\in o(k)$ $f\in o(k)$ 가능한 $f:\mathbb {N} \to \mathbb {N}$ 가 있는 문제(L $、$ k )의 $(L,k)$ 클래스입니다. $ystyle$ 2 $^{f(k)}\cdot {text{poly}}(n$

지수 시간 가설

지수 시간 가설(ETH)은 절당 최대 3리터, n개의 변수를 가진 결합 정규 형식의 부울 공식의 만족도 문제인 3SAT는 시간^o(n) 2에 해결할 수 없다는 것이다.좀 더 정확히 말하면, 그 가설은 결정론적 튜링 기계에 의해 시간^cn 2에서 3SAT가 결정될 수 없는 어떤 $절대$ 상수 c > 0이 $존재$ 한다는 것이다.m이 절의 수를 나타내면 ETH는 $정수$ k ≤^[26] $3$ 에 대해 시간^o(m) 2에 kSAT를 해결할 수 없다는 가설과 같습니다.지수 시간 가설은 P np NP를 의미합니다.

지수 시간

알고리즘은 T(n)가 2로^poly(n) 상한인 경우 지수시간이라고 하며, 여기서 poly(n)는 n의 어떤 다항식이다.좀 더 형식적으로, 알고리즘은 T(n)가 어떤 상수 k에 대해^{n^k} O(2)에 의해 제한되는 경우 지수 시간이다.결정론적 튜링 기계에서 지수 시간 알고리즘을 허용하는 문제는 EXP로 알려진 복잡도 클래스를 형성합니다.

{\text{EXP}}=\bigcup_{c\in\mathbb {N}{\text{\text}DTIME}}\left(2^{n^{c}}\오른쪽)

때때로 지수 시간은 T(n) = 2인^O(n) 알고리즘을 참조하기 위해 사용되는데, 여기서 지수는 최대 n의 선형 함수이다.이로 인해 복잡도 클래스E가 발생합니다.

디스플레이 스타일E}}=\bigcup _{c\in\mathbb {N}}{\text{DTIME}}\left(2^{cn}\오른쪽)}

요인 시간

알고리즘은 T(n)가 요인 함수 n!에 의해 상한인 경우 요인 시간이라고 합니다. $n!=O\left(2^{n^{1+\epsilon }}\right)$ 시간은 지수 시간(EXP)의 하위 $n!=O\left(2^{n^{1+\epsilon }}\right)$ 입니다 $n!=O\left(2^{n^{1+\epsilon }}\right)$ n ! $n!=O\left(2^{n^{1+\epsilon }}\right)$ ( $n!=O\left(2^{n^{1+\epsilon }}\right)$ $n!=O\left(2^{n^{1+\epsilon }}\right)$ + $n!=O\left(2^{n^{1+\epsilon }}\right)$ ) $n!=O\left(2^{n^{1+\epsilon }}\right)$ { $표시 스타일$ n $!$ $\epsilon >0$ $O\left$ (2 $^{n^{$ 1+\ $epsilon$ }}}\right $)$ 는 $n!=O\left(2^{n^{1+\epsilon }}\right)$ 0 $(\displaystyle\epsilon >$ 0 $\epsilon >0$ 의 모든 $\epsilon >0$ 에 대하여. 단, E의 서브셋은 아니다.

요인 시간에 실행되는 알고리즘의 예로는 시행착오를 기반으로 한 비효율적인 정렬 알고리즘으로 악명 높은 보고소트가 있습니다.Bogosort는 목록이 정렬될 때까지 반복하여 목록을 섞어서 n개 항목의 목록을 정렬합니다.평균적인 경우 보고소트 알고리즘을 통과하는 각 경로는 n개 항목의 n! 순서 중 하나를 검사합니다.항목이 구별되는 경우 이러한 순서는 하나만 정렬됩니다.보고소트는 무한 원숭이 정리와 유산을 공유한다.

이중 지수 시간

알고리즘은 T(n)가 2로^{2^poly(n)} 상한인 경우 이중 지수 시간이라고 합니다. 여기서 poly(n)는 n의 어떤 다항식입니다.이러한 알고리즘은 복잡도 클래스 2-EXPTIME에 속합니다.

{\mbox{2-EXPTIME}}=\bigcup _{c\in\mathbb {N}{\mbox{D}TIME}}\left(2^{n^{c}}\right)

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

Presburger 산술 결정 절차
그뢰브너 베이스 계산(최악의^[27] 경우)
실제 닫힌 필드에서의 양자화 소거에는 적어도 두 배의 지수 ^[28]시간이 소요되며,^[29] 이 시간 내에 수행할 수 있습니다.

「」를 참조해 주세요.

레퍼런스

^ ^a ^b Sipser, Michael (2006). Introduction to the Theory of Computation. Course Technology Inc. ISBN 0-619-21764-2.
^ Mehlhorn, Kurt; Naher, Stefan (1990). "Bounded ordered dictionaries in $O (log log N)$ time and $O (n)$ space". Information Processing Letters. 35 (4): 183–189. doi:10.1016/0020-0190(90)90022-P.
^ Tao, Terence (2010). "1.11 The AKS primality test". An epsilon of room, II: Pages from year three of a mathematical blog. Graduate Studies in Mathematics. Vol. 117. Providence, RI: American Mathematical Society. pp. 82–86. doi:10.1090/gsm/117. ISBN 978-0-8218-5280-4. MR 2780010.
^ Lenstra, H. W. Jr.; Pomerance, Carl (2019). "Primality testing with Gaussian periods" (PDF). Journal of the European Mathematical Society. 21 (4): 1229–1269. doi:10.4171/JEMS/861. MR 3941463. S2CID 127807021.
^ ^a ^b Babai, László; Fortnow, Lance; Nisan, N.; Wigderson, Avi (1993). "BPP has subexponential time simulations unless EXPTIME has publishable proofs". Computational Complexity. Berlin, New York: Springer-Verlag. 3 (4): 307–318. doi:10.1007/BF01275486. S2CID 14802332.
^ Bradford, Phillip G.; Rawlins, Gregory J. E.; Shannon, Gregory E. (1998). "Efficient matrix chain ordering in polylog time". SIAM Journal on Computing. 27 (2): 466–490. doi:10.1137/S0097539794270698. MR 1616556.
^ Holm, Jacob; Rotenberg, Eva (2020). "Fully-dynamic planarity testing in polylogarithmic time". In Makarychev, Konstantin; Makarychev, Yury; Tulsiani, Madhur; Kamath, Gautam; Chuzhoy, Julia (eds.). 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. pp. 167–180. arXiv:1911.03449. doi:10.1145/3357713.3384249.
^ Kumar, Ravi; Rubinfeld, Ronitt (2003). "Sublinear time algorithms" (PDF). SIGACT News. 34 (4): 57–67. doi:10.1145/954092.954103. S2CID 65359.
^ Naik, Ashish V.; Regan, Kenneth W.; Sivakumar, D. (1995). "On quasilinear-time complexity theory" (PDF). Theoretical Computer Science. 148 (2): 325–349. doi:10.1016/0304-3975(95)00031-Q. MR 1355592.
^ Sedgewick, Robert; Wayne, Kevin (2011). Algorithms (4th ed.). Pearson Education. p. 186.
^ Papadimitriou, Christos H. (1994). Computational complexity. Reading, Mass.: Addison-Wesley. ISBN 0-201-53082-1.
^ Cobham, Alan (1965). "The intrinsic computational difficulty of functions". Proc. Logic, Methodology, and Philosophy of Science II. North Holland.
^ Grötschel, Martin; László Lovász; Alexander Schrijver (1988). "Complexity, Oracles, and Numerical Computation". Geometric Algorithms and Combinatorial Optimization. Springer. ISBN 0-387-13624-X.
^ Schrijver, Alexander (2003). "Preliminaries on algorithms and Complexity". Combinatorial Optimization: Polyhedra and Efficiency. Vol. 1. Springer. ISBN 3-540-44389-4.
^ Braverman, Mark; Kun-Ko, Young; Rubinstein, Aviad; Weinstein, Omri (2017). "ETH hardness for densest- $k$ -subgraph with perfect completeness". In Klein, Philip N. (ed.). 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. pp. 1326–1341. arXiv:1504.08352. doi:10.1137/1.9781611974782.86. MR 3627815.
^ 복잡성 동물원: 클래스 QP: 준다중칭 시간
^ ^a ^b Impagliazzo, Russell; Paturi, Ramamohan (2001). "On the complexity of $k$ -SAT" (PDF). Journal of Computer and System Sciences. 62 (2): 367–375. doi:10.1006/jcss.2000.1727. MR 1820597.
^ Aaronson, Scott (5 April 2009). "A not-quite-exponential dilemma". Shtetl-Optimized. Retrieved 2 December 2009.
^ 복잡성 동물원: 클래스 SUBEXP: 결정론적 하위 지수 시간
^ Moser, P. (2003). "Baire's Categories on Small Complexity Classes". In Andrzej Lingas; Bengt J. Nilsson (eds.). Fundamentals of Computation Theory: 14th International Symposium, FCT 2003, Malmö, Sweden, August 12-15, 2003, Proceedings. Lecture Notes in Computer Science. Vol. 2751. Berlin, New York: Springer-Verlag. pp. 333–342. doi:10.1007/978-3-540-45077-1_31. ISBN 978-3-540-40543-6. ISSN 0302-9743.
^ Miltersen, P.B. (2001). "Derandomizing Complexity Classes". Handbook of Randomized Computing. Combinatorial Optimization. Kluwer Academic Pub. 9: 843. doi:10.1007/978-1-4615-0013-1_19. ISBN 978-1-4613-4886-3.
^ Kuperberg, Greg (2005). "A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem". SIAM Journal on Computing. Philadelphia. 35 (1): 188. arXiv:quant-ph/0302112. doi:10.1137/s0097539703436345. ISSN 1095-7111. S2CID 15965140.
^ Oded Regev (2004). "A Subexponential Time Algorithm for the Dihedral Hidden Subgroup Problem with Polynomial Space". arXiv:quant-ph/0406151v1.
^ Grohe, Martin; Neuen, Daniel (2021). "Recent Advances on the Graph Isomorphism Problem". arXiv:2011.01366. {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)
^ Flum, Jörg; Grohe, Martin (2006). Parameterized Complexity Theory. Springer. p. 417. ISBN 978-3-540-29952-3.
^ Impagliazzo, R.; Paturi, R.; Zane, F. (2001). "Which problems have strongly exponential complexity?". Journal of Computer and System Sciences. 63 (4): 512–530. doi:10.1006/jcss.2001.1774.
^ Mayr, Ernst W.; Meyer, Albert R. (1982). "The complexity of the word problems for commutative semigroups and polynomial ideals". Advances in Mathematics. 46 (3): 305–329. doi:10.1016/0001-8708(82)90048-2. MR 0683204.
^ Davenport, James H.; Heintz, Joos (1988). "Real quantifier elimination is doubly exponential". Journal of Symbolic Computation. 5 (1–2): 29–35. doi:10.1016/S0747-7171(88)80004-X. MR 0949111.
^ Collins, George E. (1975). "Quantifier elimination for real closed fields by cylindrical algebraic decomposition". In Brakhage, H. (ed.). Automata Theory and Formal Languages: 2nd GI Conference, Kaiserslautern, May 20–23, 1975. Lecture Notes in Computer Science. Vol. 33. Springer. pp. 134–183. doi:10.1007/3-540-07407-4_17. MR 0403962.

[Sipser-1] Sipser, Michael (2006). Introduction to the Theory of Computation. Course Technology Inc. ISBN 0-619-21764-2.

[2] Mehlhorn, Kurt; Naher, Stefan (1990). "Bounded ordered dictionaries in $O (log log N)$ time and $O (n)$ space". Information Processing Letters. 35 (4): 183–189. doi:10.1016/0020-0190(90)90022-P.

[tao-aks-3] Tao, Terence (2010). "1.11 The AKS primality test". An epsilon of room, II: Pages from year three of a mathematical blog. Graduate Studies in Mathematics. Vol. 117. Providence, RI: American Mathematical Society. pp. 82–86. doi:10.1090/gsm/117. ISBN 978-0-8218-5280-4. MR 2780010.

[4] Lenstra, H. W. Jr.; Pomerance, Carl (2019). "Primality testing with Gaussian periods" (PDF). Journal of the European Mathematical Society. 21 (4): 1229–1269. doi:10.4171/JEMS/861. MR 3941463. S2CID 127807021.

[bpp-5] Babai, László; Fortnow, Lance; Nisan, N.; Wigderson, Avi (1993). "BPP has subexponential time simulations unless EXPTIME has publishable proofs". Computational Complexity. Berlin, New York: Springer-Verlag. 3 (4): 307–318. doi:10.1007/BF01275486. S2CID 14802332.

[6] Bradford, Phillip G.; Rawlins, Gregory J. E.; Shannon, Gregory E. (1998). "Efficient matrix chain ordering in polylog time". SIAM Journal on Computing. 27 (2): 466–490. doi:10.1137/S0097539794270698. MR 1616556.

[7] Holm, Jacob; Rotenberg, Eva (2020). "Fully-dynamic planarity testing in polylogarithmic time". In Makarychev, Konstantin; Makarychev, Yury; Tulsiani, Madhur; Kamath, Gautam; Chuzhoy, Julia (eds.). 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. pp. 167–180. arXiv:1911.03449. doi:10.1145/3357713.3384249.

[8] Kumar, Ravi; Rubinfeld, Ronitt (2003). "Sublinear time algorithms" (PDF). SIGACT News. 34 (4): 57–67. doi:10.1145/954092.954103. S2CID 65359.

[9] Naik, Ashish V.; Regan, Kenneth W.; Sivakumar, D. (1995). "On quasilinear-time complexity theory" (PDF). Theoretical Computer Science. 148 (2): 325–349. doi:10.1016/0304-3975(95)00031-Q. MR 1355592.

[10] Sedgewick, Robert; Wayne, Kevin (2011). Algorithms (4th ed.). Pearson Education. p. 186.

[11] Papadimitriou, Christos H. (1994). Computational complexity. Reading, Mass.: Addison-Wesley. ISBN 0-201-53082-1.

[12] Cobham, Alan (1965). "The intrinsic computational difficulty of functions". Proc. Logic, Methodology, and Philosophy of Science II. North Holland.

[13] Grötschel, Martin; László Lovász; Alexander Schrijver (1988). "Complexity, Oracles, and Numerical Computation". Geometric Algorithms and Combinatorial Optimization. Springer. ISBN 0-387-13624-X.

[14] Schrijver, Alexander (2003). "Preliminaries on algorithms and Complexity". Combinatorial Optimization: Polyhedra and Efficiency. Vol. 1. Springer. ISBN 3-540-44389-4.

[15] Braverman, Mark; Kun-Ko, Young; Rubinstein, Aviad; Weinstein, Omri (2017). "ETH hardness for densest- $k$ -subgraph with perfect completeness". In Klein, Philip N. (ed.). 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. pp. 1326–1341. arXiv:1504.08352. doi:10.1137/1.9781611974782.86. MR 3627815.

[16] 복잡성 동물원: 클래스 QP: 준다중칭 시간

[ETH-17] Impagliazzo, Russell; Paturi, Ramamohan (2001). "On the complexity of $k$ -SAT" (PDF). Journal of Computer and System Sciences. 62 (2): 367–375. doi:10.1006/jcss.2000.1727. MR 1820597.

[18] Aaronson, Scott (5 April 2009). "A not-quite-exponential dilemma". Shtetl-Optimized. Retrieved 2 December 2009.

[19] 복잡성 동물원: 클래스 SUBEXP: 결정론적 하위 지수 시간

[20] Moser, P. (2003). "Baire's Categories on Small Complexity Classes". In Andrzej Lingas; Bengt J. Nilsson (eds.). Fundamentals of Computation Theory: 14th International Symposium, FCT 2003, Malmö, Sweden, August 12-15, 2003, Proceedings. Lecture Notes in Computer Science. Vol. 2751. Berlin, New York: Springer-Verlag. pp. 333–342. doi:10.1007/978-3-540-45077-1_31. ISBN 978-3-540-40543-6. ISSN 0302-9743.

[21] Miltersen, P.B. (2001). "Derandomizing Complexity Classes". Handbook of Randomized Computing. Combinatorial Optimization. Kluwer Academic Pub. 9: 843. doi:10.1007/978-1-4615-0013-1_19. ISBN 978-1-4613-4886-3.

[22] Kuperberg, Greg (2005). "A Subexponential-Time Quantum Algorithm for the Dihedral Hidden Subgroup Problem". SIAM Journal on Computing. Philadelphia. 35 (1): 188. arXiv:quant-ph/0302112. doi:10.1137/s0097539703436345. ISSN 1095-7111. S2CID 15965140.

[23] Oded Regev (2004). "A Subexponential Time Algorithm for the Dihedral Hidden Subgroup Problem with Polynomial Space". arXiv:quant-ph/0406151v1.

[24] Grohe, Martin; Neuen, Daniel (2021). "Recent Advances on the Graph Isomorphism Problem". arXiv:2011.01366. {{cite journal}}:Cite 저널 요구 사항 journal=(도움말)

[25] Flum, Jörg; Grohe, Martin (2006). Parameterized Complexity Theory. Springer. p. 417. ISBN 978-3-540-29952-3.

[26] Impagliazzo, R.; Paturi, R.; Zane, F. (2001). "Which problems have strongly exponential complexity?". Journal of Computer and System Sciences. 63 (4): 512–530. doi:10.1006/jcss.2001.1774.

[27] Mayr, Ernst W.; Meyer, Albert R. (1982). "The complexity of the word problems for commutative semigroups and polynomial ideals". Advances in Mathematics. 46 (3): 305–329. doi:10.1016/0001-8708(82)90048-2. MR 0683204.

[28] Davenport, James H.; Heintz, Joos (1988). "Real quantifier elimination is doubly exponential". Journal of Symbolic Computation. 5 (1–2): 29–35. doi:10.1016/S0747-7171(88)80004-X. MR 0949111.

[29] Collins, George E. (1975). "Quantifier elimination for real closed fields by cylindrical algebraic decomposition". In Brakhage, H. (ed.). Automata Theory and Formal Languages: 2nd GI Conference, Kaiserslautern, May 20–23, 1975. Lecture Notes in Computer Science. Vol. 33. Springer. pp. 134–183. doi:10.1007/3-540-07407-4_17. MR 0403962.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

Search

시간의 복잡성

네임스페이스

더

목차

일반적인 시간 복잡도 표

일정한 시간

로그 시간

다산수 시간

준선형 시간

선형 시간

준선형 시간

이차 시간