계산의 복잡성

컴퓨터 과학에서 알고리즘의 계산 복잡도 또는 단순 복잡도는 알고리즘을 실행하는 데 필요한 자원의 양입니다.특히 시간과 메모리 요건에 중점을 두고 있습니다.문제의 복잡성은 문제를 해결할 수 있는 최적의 알고리즘의 복잡성입니다.

명시적으로 주어진 알고리즘의 복잡성에 대한 연구는 알고리즘의 분석이라고 불리는 반면, 문제의 복잡성에 대한 연구는 계산 복잡성 이론이라고 불립니다.알고리즘의 복잡성은 항상 이 알고리즘에 의해 해결되는 문제의 복잡성의 상한이기 때문에 두 영역 모두 높은 관련성을 가지고 있습니다.게다가 효율적인 알고리즘을 설계하기 위해서는 특정 알고리즘의 복잡성과 해결해야 할 문제의 복잡성을 비교하는 것이 종종 기본이다.또한 대부분의 경우 문제의 복잡성에 대해 알려진 유일한 것은 가장 효율적인 알고리즘의 복잡도보다 낮다는 것입니다.따라서 알고리즘의 분석과 복잡성 이론 사이에는 큰 중복이 있다.

알고리즘 실행에 필요한 자원의 양은 일반적으로 입력의 크기에 따라 다르므로, 복잡도는 일반적으로 $함수$ n → $f (n)$ 로 표현된다. $여기$ 서 n은 입력의 $크기$ 이고 f $(n)$ 는 최악의 경우 복잡도(n $크기$ 의 모든 입력에 걸쳐 필요한 자원의 최대치) 또는 평균 경우 완료이다.xity( $크기$ n의 모든 입력에 대한 자원 양의 평균).시간 복잡도는 일반적으로 $크기$ n의 입력에 필요한 기본 연산의 수로 표현되며, 여기서 기본 연산은 주어진 컴퓨터에서 일정한 시간이 걸리고 다른 컴퓨터에서 실행될 때 일정한 계수에 의해서만 변경된다고 가정한다.공간 복잡도는 일반적으로 $크기$ n의 입력에 대해 알고리즘이 필요로 하는 메모리 양으로 표현된다.

자원.

시간을

가장 일반적으로 고려되는 자원은 시간입니다.조건 없이 "복잡성"을 사용할 경우 일반적으로 시간이 복잡함을 의미합니다.

통상적인 시간 단위(초, 분 등)는 특정 컴퓨터의 선택과 기술의 진화에 너무 의존하기 때문에 복잡성 이론에서는 사용되지 않습니다.예를 들어, 오늘날 컴퓨터는 1960년대 컴퓨터보다 훨씬 더 빠르게 알고리즘을 실행할 수 있다. 그러나 이것은 알고리즘의 본질적인 특징이 아니라 컴퓨터 하드웨어의 기술적 진보의 결과이다.복잡도 이론은 알고리즘의 본질적인 시간 요건, 즉 알고리즘이 컴퓨터에 가하는 기본적인 시간 제약을 정량화하는 것을 추구합니다.이는 계산 중에 실행되는 기본 연산 수를 카운트함으로써 달성됩니다.이러한 조작은, 소정의 머신상에서 일정한 시간(즉, 입력의 크기에 영향을 받지 않는 것)이 걸리는 것을 전제로 해, 스텝이라고 불리는 경우가 있습니다.

비트의 복잡성

형식적으로 비트의 복잡도는 알고리즘을 실행하기 위해 필요한 비트의 연산 수를 나타냅니다.대부분의 계산 모델에서 이 값은 일정 요인까지의 시간 복잡도와 동일합니다.시스템에서 필요한 기계어에 대한 작업 수도 비트의 복잡도에 비례합니다.따라서 실제 계산 모델의 경우 시간 복잡도와 비트 복잡도는 동일합니다.

공간

또 다른 중요한 리소스는 알고리즘을 실행하는 데 필요한 시스템 메모리의 크기입니다.

의사소통

일반적으로 여러 당사자에 의해 실행되는 분산 알고리즘의 클래스에서 가장 관심 있는 자원은 통신의 복잡성입니다.실행 당사자 간에 필요한 통신량입니다.

다른이들

산술 연산의 수는 일반적으로 사용되는 또 다른 리소스입니다.이 경우 산술적 복잡성에 대해 이야기한다.계산 중에 발생하는 숫자의 이진수 표현 크기에 대한 상한을 알고 있는 경우, 일반적으로 시간 복잡도는 상수 인수에 의한 산술 복잡도의 곱입니다.

많은 알고리즘에서 계산 중에 사용되는 정수의 크기는 경계가 없으며, 산술 연산이 일정한 시간이 걸린다고 고려하는 것은 현실적이지 않습니다.따라서 이 맥락에서 일반적으로 비트 복잡도라고 불리는 시간 복잡도는 산술 복잡도보다 훨씬 클 수 있습니다. $예$ 를 들어 n $\times$ n 정수행렬의 행렬식 계산의 산술복잡도는 통상 알고리즘(가우스 소거)의 경우 O $O(n^{3})$ 3 $)$ { $displaystyle$ O $(n^{3})}$ 이다 $O(n^{3})$ .계산 중에 계수의 크기가 기하급수적으로 증가할 수 있기 때문에 동일한 알고리즘의 비트 복잡도는 n $단위$ 로 지수화됩니다.한편, 이러한 알고리즘이 멀티 모듈식 산술과 결합되어 있으면, 비트 복잡도는 $O($ n)까지^~⁴ 저하할 수 있다.

정렬 및 검색에서 일반적으로 고려되는 리소스는 항목 비교 수입니다.데이터가 적절히 정리되어 있는 경우, 이것은 일반적으로 시간의 복잡성을 측정하는 좋은 지표입니다.

입력 크기의 함수로서의 복잡성

가능한 모든 입력에 대해 알고리즘의 단계 수를 셀 수는 없습니다.일반적으로 입력의 크기에 따라 복잡도가 증가하므로 복잡도는 일반적으로 입력의 $크기$ n(비트 단위)의 함수로 표현되며, 따라서 $복잡도$ 는 n의 함수이다.그러나 알고리즘의 복잡도는 같은 크기의 입력마다 크게 다를 수 있습니다.따라서 몇 가지 복잡도 함수가 일반적으로 사용됩니다.

최악의 경우 복잡도는 $크기$ n의 모든 입력에 대한 복잡도의 최대값이며, 평균적인 경우 복잡도는 $크기$ n의 모든 입력에 대한 복잡도의 평균이다(이것은 주어진 크기의 가능한 입력 수가 유한하기 때문에 타당하다).일반적으로 "복잡성"이 더 이상 지정되지 않고 사용될 경우, 이는 고려되는 최악의 시간 복잡성입니다.

점근 복잡도

일반적으로 최악의 경우 및 평균적인 경우의 복잡성을 정확하게 계산하는 것은 어렵습니다.또한 이러한 정확한 값은 컴퓨터나 계산 모델을 변경하면 복잡성이 다소 변경되기 때문에 실용적으로 거의 적용되지 않습니다.게다가 자원 사용은 작은 값 $n$ 에 대해서는 중요하지 않으며, 작은 $값$ n에 대해서는 일반적으로 구현의 용이성이 낮은 복잡도보다 더 흥미롭다.

이러한 이유로, $사람들$ 은 일반적으로 큰 n에 대한 복잡성의 거동, 즉 n이 무한대에 대한 경향이 $있을$ 때 점근적 거동에 초점을 맞춘다.따라서 복잡도는 일반적으로 큰 O 표기를 사용하여 표현됩니다.

예를 들어, 정수 곱셈의 통상의 알고리즘의 복잡도는 O $O(n^{2}),$ 2 $),$ { $displaystyle$ O $(n$ $^{$ $2})$ 입니다 $O(n^{2}),$ .즉, $({$ $u})$ 가 $c_{u}$ $c_{u}$ 존재함을 의미합니다.이것에 $의해$ , 최대 n자리수의 2개의 정수의 곱셈은 $2$ 보다 $c_{u}n^{2}.$ 시간에 $행해집니다.$ $.}$ 이 $c_{u}n^{2}.$ 경계는 최악의 복잡도와 평균적인 복잡도가 $\Omega (n^{2}),$ ( $n$ 2) $\Omega (n^{2}),$ , $\Omega (n^{2}),$ {displaystyle $\Omega (n$ 즉 c $c_{l}$ l { $displaystyle c_$ ${l$ $}$ 이므로 $c_{l}$ 이러한 $c_{l}n^{2}.$ 가 c $c_{l}n^{2}.$ $c_{l}n^{2}.$ . $c_{l}n^{2}.$ { $style c_l}$ 보다 $.$ $c_{l}n^{2}.$ 기수를 변경하면 $(\$ }) 및 $.$ l.(\ $displaystyle c_{$ $c_{u}$ }) 상수만 변경되므로 기수는 이러한 복잡성에는 표시되지 않습니다. $}$

계산 모델

복잡성의 평가는 계산 모델의 선택에 의존하며, 계산 모델은 시간 단위로 수행되는 기본 연산을 정의하는 것으로 구성됩니다.계산 모델이 명시적으로 지정되지 않은 경우, 이는 일반적으로 멀티테이프 튜링 기계로 간주됩니다.

결정론적 모형

결정론적 계산모델은 기계의 연속상태와 실행되어야 할 연산이 선행상태에 의해 완전히 결정되는 계산모델이다.역사적으로, 첫 번째 결정론적 모형은 재귀 함수, 람다 미적분, 튜링 기계였다.랜덤 액세스 머신(RAM 머신이라고도 불린다)의 모델도, 실제의 컴퓨터에 가까운 모델로서 널리 사용되고 있습니다.

계산 모델이 지정되지 않은 경우, 일반적으로 멀티테이프 튜링 기계로 가정됩니다.대부분의 알고리즘에서 시간 복잡도는 RAM 머신과 같은 멀티테이프 튜링 머신에서 동일하지만, 이 동등성을 얻기 위해서는 데이터가 메모리에 저장되는 방법에 약간의 주의가 필요할 수 있습니다.

비결정론적 계산

비결정론적 튜링 기계와 같은 비결정론적 계산 모델에서, 몇 가지 선택은 계산의 몇 가지 단계에서 이루어질 수 있다.복잡성 이론에서는 모든 가능한 선택지를 동시에 고려하며, 비결정론적 시간 복잡성은 최선의 선택이 항상 이루어질 때 필요한 시간이다.즉, 계산은 필요한 수만큼 (동일한) 프로세서에서 동시에 이루어지며, 비결정론적 계산 시간은 계산을 완료한 첫 번째 프로세서가 소비하는 시간이라고 간주합니다.이 병렬은 특정 양자 알고리즘을 실행할 때 중첩된 얽힌 상태를 통해 양자 컴퓨팅에 부분적으로 적응할 수 있다.아직 작은 정수에 대한 쇼어의 인수분해(2018년 3월^[update] 기준: 21 = 3 × 7).

이러한 계산 모델이 아직 현실적이지 않은 경우에도, 이론적으로 중요한데, 대부분 P = NP 문제와 관련이 있으며, 이는 "수분 시간"과 "비수분론적 다항식 시간"을 최소한 상한을 취함으로써 형성된 복잡도 클래스의 동일성에 의문을 제기한다.결정론적 컴퓨터에서 NP 알고리즘을 시뮬레이션하는 데는 보통 "지수적 시간"이 소요됩니다.비결정론적 기계에서 다항식 시간에 해결할 수 있는 문제는 복잡도 클래스 NP에 있습니다.대략적으로 말하면 NP에 있고 다른 NP 문제보다 쉽지 않은 경우 문제는 NP-완전입니다.Knapsack 문제, 출장 세일즈맨 문제, 부울 만족도 문제 등 많은 조합 문제는 NP-완전입니다.이러한 모든 문제에 대해 가장 잘 알려진 알고리즘은 기하급수적으로 복잡합니다.1 이러한 문제들 중 다항 시간에 결정론적 기계에 해결될 수 있다면, 모든 NP문제도 다항 시간에, P는 NP을 것이다. 2017[업데이트]하자 일반적으로 했던 것으로 추측 해결될 수 있을 것이 P≠ 사진 없음과 함께 실용적인 의미는 최악의 사례의 NP문제는 본질적으로 어려운를 해결하기 위해서, 즉,가지고 가다대상 입력 길이에 대해 적절한 시간 범위(시간 범위)보다 깁니다(시간 범위(시간 범위)가 길어집니다.

병렬 및 분산 계산

병렬 컴퓨팅과 분산 컴퓨팅은 여러 프로세서에서 동시에 작동하는 분할 컴퓨팅으로 구성됩니다.다른 모델의 차이는 주로 프로세서 간의 정보 전송 방식에 있습니다.일반적으로 병렬 컴퓨팅에서는 프로세서 간의 데이터 전송 속도가 매우 빠른 반면 분산 컴퓨팅에서는 네트워크를 통해 데이터 전송 속도가 훨씬 느립니다.

N 프로세서의 $계산$ 에 필요한 시간은 적어도 단일 프로세서가 필요로 하는 시간의 $N$ 의 몫입니다.실제로 이론적으로 최적의 한계에는 도달할 수 없습니다.일부 서브태스크는 병렬화할 수 없고 일부 프로세서는 다른 프로세서에서 결과를 기다려야 할 수 있기 때문입니다.

따라서 가장 복잡한 문제는 프로세서 수에 의한 연산 시간의 곱이 단일 프로세서에서 동일한 연산에 필요한 시간에 최대한 근접하도록 알고리즘을 설계하는 것입니다.

양자 컴퓨팅

양자 컴퓨터는 양자역학에 기초한 계산 모델을 가진 컴퓨터이다.처치-튜링 논문은 양자 컴퓨터에 적용된다. 즉, 양자 컴퓨터로 해결할 수 있는 모든 문제는 튜링 기계로도 해결할 수 있다.그러나, 이론적으로 어떤 문제들은 고전적인 컴퓨터보다는 양자 컴퓨터를 사용하여 훨씬 더 낮은 시간 복잡도로 해결될 수 있다.이것은, 현재로서는, 아무도 효율적인 양자 컴퓨터를 만드는 방법을 모르기 때문에, 순전히 이론적인 것입니다.

양자 복잡도 이론은 양자 컴퓨터를 사용하여 해결된 문제의 복잡도 클래스를 연구하기 위해 개발되었습니다.양자컴퓨터의 공격에 강한 암호화 프로토콜을 설계하는 포스트 퀀텀 암호화에 사용됩니다.

문제의 복잡성(하한)

문제의 복잡성은 알려지지 않은 알고리즘을 포함하여 문제를 해결할 수 있는 알고리즘의 복잡성의 최소값입니다.따라서 문제의 복잡성은 문제를 해결하는 알고리즘의 복잡성보다 크지 않습니다.

따라서 빅 O 표기법으로 표현되는 모든 복잡도는 알고리즘과 대응하는 문제의 복잡도입니다.

한편, 일반적으로 문제의 복잡성에 대해 중요하지 않은 하한을 구하는 것은 어렵고, 그러한 하한을 구하는 방법은 거의 없다.

대부분의 문제를 해결하려면 모든 입력 데이터를 읽어야 하며, 일반적으로 데이터 크기에 비례하는 시간이 필요합니다.따라서 이러한 문제에는 적어도 선형적인 복잡성이 있습니다.즉, 큰 오메가 표기법을 사용하면 복잡도 $\Omega (n).$ ( $),$ \ $displaystyle \Omega(n)$ 입니다. $}$

일반적으로 컴퓨터 대수학과 계산 대수 기하학에서 일부 문제의 해답은 매우 클 수 있다.이 경우 출력이 기록되어야 하므로 복잡도는 출력의 최대 크기에 따라 낮아집니다.예를 들어, n개의 $불확정차수$ d의 다항식 시스템은 해수가 유한하다면 최대 $(\$ d $^{n})$ 의 $d^n$ 복소해를 가질 수 있다(이것은 베주트의 정리이다).이러한 해결 방법을 적어 둘 필요가 있기 때문에 이 문제의 복잡도는 $\Omega (d^{n}).$ ( $).\$ $displaystyle \ Omega$ ( $d^{n})$ 입니다.} 이 $\Omega (d^{n}).$ 문제에 대해서는 $d^{O(n)}$ d $d^{O(n)}$ ( $d^{O(n)}$ ) { $displaystyle$ d^{ $O($ n $d^{O(n)}$ )}}의 알고리즘이 알려져 있으며, 따라서 점근적으로 준최적이라고 볼 수 있다 $.$

정렬 알고리즘에 필요한 비교 횟수는 비선형 $\Omega (n\log n)$ 인 $($ $\Omega (n\log n)$ n )(\ $displaystyle \Omega(n\$ log n))로 $\Omega (n\log n)$ 알려져 있습니다.따라서 그 복잡도는 $O(n\log n).$ O(n $O(n\log n).$ n $).\displaystyle$ O $(n\log$ n $)$ 이므로 최적의 정렬 알고리즘이 됩니다.} 이 $O(n\log n).$ 하한은 n개의 객체를 정렬하는 $방법$ 이있기 때문에 발생합니다 $.$ 각 비교가 이 $일련$ 의 n $!$ 순서 두 부분으로 분할될 때, 모든 순서를 구별하는 데 필요한 비교 N의 $수$ 는 $2^{N}>n!,$ N $2^{N}>n!,$ > $2^{N}>n!,$ ! $2^{N}>n!,$ , { $style$ 2 $^{N}$ > $n!,$ 즉 N $Ω$ ( n log $N=\Omega (n\log n),$ ) , $N=\Omega (n\log n),$ \ $displaystyle$ N = \ Omega ( $n$ \ $log$ n )를 $2^{N}>n!,$ $N=\Omega (n\log n),$ 스털링 공식으로 $N=\Omega (n\log n),$ 해야 합니다.

복잡도 하한을 구하는 표준 방법은 문제를 다른 문제로 줄이는 것입니다.보다 정확하게는 $크기$ n의 $문제$ A를 $문제$ B의 $크기$ f $(n)$ 의 하위 문제로 부호화할 수 있으며, $A$ 의 복잡도는 $\Omega (g(n)).$ ( $\Omega (g(n)).$ ( $\Omega (g(n)).$ ) $\Omega (g(n)).$ . \ $displaystyle \ Omega$ ( $g$ ( $n$ ) }일반성의 $\Omega (g(n)).$ 손실 없이 $함수$ $f$ 가 증가하여 $역함수$ 를 갖는다고 가정합니다. $다음$ 으로 문제 B의 복잡도는 $\Omega (g(h(n))).$ ( $\Omega (g(h(n))).$ ( $\Omega (g(h(n))).$ ( $\Omega (g(h(n))).$ ) $).\$ $displaystyle \ Omega$ ( $g$ ( $h ($ ) )입니다.} P $\Omega (g(h(n))).$ np NP(미해결 추측)일 경우, 모든 NP-완전 문제의 복잡도가 양의 $정수$ k마다 $\Omega (n^{k}),$ k $),$ \ $displaystyle$ \ $Omega(n$ ^{k $})$ 임을 $\Omega (n^{k}),$ 증명하기 위해 사용하는 방법이다 $.$

알고리즘 설계에 사용

알고리즘의 복잡도를 평가하는 것은 알고리즘 설계의 중요한 부분입니다.이는 예상되는 성능에 대한 유용한 정보를 제공하기 때문입니다.

알고리즘의 복잡성에 대한 평가는 현대 컴퓨터의 힘의 기하급수적인 성장을 전제로 하는 무어의 법칙의 결과로 덜 중요해질 것이라는 것은 흔한 오해이다.이 전력 증강에 의해 대량의 입력 데이터(빅 데이터)를 사용할 수 있기 때문에 이는 잘못된 것입니다.예를 들어, 책의 목록과 같이 수백 개의 항목의 목록을 알파벳 순으로 정렬하고 싶다면, 어떤 알고리즘도 1초 이내에 잘 작동해야 합니다.한편, 100만 개의 엔트리 리스트(예를 들면, 대도시 전화번호)의 경우, O $O(n^{2})$ 2 $)(\displaystyle$ O $(n^{2})$ 비교가 $O(n^{2})$ $O(n^{2})$ 한 기초 알고리즘은 1조 개의 비교를 실시해야 하며, 초당 1,000만 개의 비교 속도로 약 3시간이 소요됩니다.한편, QuickSort와 Marge Sort의 $n\log _{2}n$ $n\log _{2}n$ 2 ${\n(전자$ 의 경우 평균적인 복잡도, 후자의 경우 최악의 복잡도)만 $n\log _{2}n$ 비교하면 됩니다.n $=$ 1, $000,000$ 의 $경우$ , 이는 약 30,000,000의 비교를 제공하며, 초당 1,000만 비교에서 3초 밖에 걸리지 않습니다.

따라서 복잡성을 평가함으로써 구현 전에 비효율적인 알고리즘을 많이 제거할 수 있습니다.또한 모든 변형을 테스트하지 않고 복잡한 알고리즘을 조정하는 경우에도 사용할 수 있습니다.복잡도 연구는 복잡한 알고리즘의 가장 비용이 많이 드는 단계를 결정함으로써 구현의 효율성을 개선하기 위한 노력에 초점을 맞출 수 있습니다.

「」를 참조해 주세요.

레퍼런스

Arora, Sanjeev; Barak, Boaz (2009), Computational Complexity: A Modern Approach, Cambridge, ISBN 978-0-521-42426-4, Zbl 1193.68112
Du, Ding-Zhu; Ko, Ker-I (2000), Theory of Computational Complexity, John Wiley & Sons, ISBN 978-0-471-34506-0
Garey, Michael R.; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, ISBN 0-7167-1045-5
Goldreich, Oded (2008), Computational Complexity: A Conceptual Perspective, Cambridge University Press
van Leeuwen, Jan, ed. (1990), Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, ISBN 978-0-444-88071-0
Papadimitriou, Christos (1994), Computational Complexity (1st ed.), Addison Wesley, ISBN 0-201-53082-1
Sipser, Michael (2006), Introduction to the Theory of Computation (2nd ed.), USA: Thomson Course Technology, ISBN 0-534-95097-3

Search

계산의 복잡성

네임스페이스

더

목차

자원.

시간을

비트의 복잡성

공간

의사소통

다른이들

입력 크기의 함수로서의 복잡성

점근 복잡도

계산 모델

결정론적 모형

비결정론적 계산

병렬 및 분산 계산

양자 컴퓨팅

문제의 복잡성(하한)

알고리즘 설계에 사용

「」를 참조해 주세요.

레퍼런스

Search

계산의 복잡성

자원.

시간을

비트의 복잡성

공간

의사소통

다른이들

입력 크기의 함수로서의 복잡성

점근 복잡도

계산 모델

결정론적 모형

비결정론적 계산

병렬 및 분산 계산

양자 컴퓨팅

문제의 복잡성(하한)

알고리즘 설계에 사용

「 」를 참조해 주세요.

레퍼런스

「」를 참조해 주세요.