EITC/IS/CCTF 계산 복잡도 이론 기초

알고리즘을 실행하는 데 필요한 리소스의 양이 입력의 크기에 따라 다르기 때문에 복잡도는 일반적으로 함수 f(n)으로 표현됩니다. 여기서 n은 입력 크기이고 f(n)은 최악의 경우 복잡도( 크기 n의 모든 입력에 필요한 최대 리소스 양) 또는 평균 케이스 복잡성(크기 n의 모든 입력에 대한 리소스 양의 평균). 크기 n의 입력에 필요한 기본 연산의 수는 일반적으로 시간 복잡도라고 합니다. 여기서 기본 연산은 특정 컴퓨터에서 일정한 시간이 걸리고 다른 기계에서 실행될 때 일정한 요소에 의해서만 변경되는 것으로 믿어집니다. 크기가 n인 입력에 대해 알고리즘에 필요한 메모리 양을 공간 복잡도라고 합니다.

시간은 가장 일반적으로 고려되는 자원입니다. "복잡성"이라는 용어가 수식어 없이 사용될 때 일반적으로 시간의 복잡성을 나타냅니다.

전통적인 시간 단위(초, 분 등)는 선택한 컴퓨터와 기술 발전에 너무 의존하기 때문에 복잡성 이론에서 사용되지 않습니다. 예를 들어, 오늘날의 컴퓨터는 1960년대의 컴퓨터보다 훨씬 더 빠르게 알고리즘을 실행할 수 있지만, 이는 알고리즘의 고유한 품질보다는 컴퓨터 하드웨어의 기술적 혁신 때문입니다. 복잡성 이론의 목표는 알고리즘의 고유한 시간 요구 사항 또는 알고리즘이 모든 컴퓨터에 부과하는 기본적인 시간 제한을 수량화하는 것입니다. 이것은 계산 중에 수행되는 기본 작업의 수를 세어 수행됩니다. 이러한 절차는 특정 기계에서 일정한 시간이 소요되는 것으로 간주되기 때문에 일반적으로 단계라고 합니다(즉, 입력의 양에 영향을 받지 않음).

또 다른 중요한 리소스는 알고리즘을 수행하는 데 필요한 컴퓨터 메모리의 양입니다.

자주 사용되는 또 다른 리소스는 산술 연산의 양입니다. 이 시나리오에서는 "산술 복잡도"라는 용어가 사용됩니다. 시간 복잡도는 일반적으로 계산 중에 발생하는 숫자의 이진 표현 크기에 대한 상한 제약이 알려진 경우 상수 인수에 의한 산술 복잡도의 곱입니다.

계산 중에 사용되는 정수의 크기는 많은 방법에서 제한되지 않으며 산술 연산에 고정된 시간이 필요하다고 가정하는 것은 비현실적입니다. 결과적으로 비트 복잡도라고도 하는 시간 복잡도는 산술 복잡도보다 훨씬 더 높을 수 있습니다. 예를 들어, nn 정수 행렬의 행렬식을 계산하는 산술 난이도는 표준 기술(가우스 제거)의 경우 O(n^3)입니다. 계수의 크기는 계산 중에 기하급수적으로 확장될 수 있기 때문에 동일한 방법의 비트 복잡도는 n에서 기하급수적입니다. 이러한 기술을 다중 모듈식 산술과 함께 사용하면 비트 복잡도를 O(n^4)로 줄일 수 있습니다.

형식적인 용어로 비트 복잡도는 알고리즘을 실행하는 데 필요한 비트 연산 수를 나타냅니다. 그것은 대부분의 계산 패러다임에서 일정한 요소까지 시간적 복잡성과 같습니다. 컴퓨터가 요구하는 기계어 연산의 수는 비트 복잡도에 비례합니다. 따라서 실제 계산 모델의 경우 시간 복잡도와 비트 복잡도는 동일합니다.

정렬 및 검색에서 자주 고려되는 리소스는 항목 비교의 양입니다. 데이터가 잘 정렬되어 있으면 시간 복잡도를 나타내는 좋은 지표가 됩니다.

모든 잠재적 입력에서 알고리즘의 단계 수를 계산하는 것은 불가능합니다. 입력의 복잡성은 크기와 함께 증가하기 때문에 일반적으로 입력의 크기 n(비트 단위)의 함수로 표현되므로 복잡성은 n의 함수입니다. 그러나 동일한 크기의 입력에 대해 알고리즘의 복잡성은 상당히 다를 수 있습니다. 결과적으로 다양한 복잡성 함수가 일상적으로 사용됩니다.

최악의 복잡도는 모든 크기 n 입력에 대한 모든 복잡도의 합이고 평균 경우 복잡도는 모든 크기 n 입력에 대한 모든 복잡도의 합입니다(주어진 크기의 가능한 입력 수가 한정된). "복잡도"라는 용어가 더 이상 정의되지 않고 사용될 때, 최악의 시간 복잡도가 고려된다.

최악의 경우와 평균적인 경우의 복잡성은 올바르게 계산하기가 매우 어렵습니다. 게다가 이러한 정확한 값은 기계 또는 계산 패러다임이 변경되면 복잡성이 약간 달라지기 때문에 실제 적용이 거의 없습니다. 또한, n 값이 작을 경우 리소스 사용이 중요하지 않으므로 n 값이 작을 경우 구현 용이성이 낮은 복잡성보다 더 매력적입니다.

이러한 이유로 인해 높은 n에 대한 복잡성의 동작, 즉 n이 무한대에 접근할 때의 점근적 동작에 대부분의 주의를 기울입니다. 결과적으로 복잡성을 나타내는 데 큰 O 표기법이 일반적으로 사용됩니다.

계산 모델

단위 시간에 수행되는 필수 작업을 지정하는 계산 모델의 선택은 복잡성을 결정하는 데 중요합니다. 계산 패러다임이 구체적으로 설명되지 않은 경우 이를 멀티테이프 튜링 머신이라고 부르기도 합니다.

결정론적 계산 모델은 기계의 후속 상태와 수행할 작업이 이전 상태에 의해 완전히 정의되는 모델입니다. 재귀 함수, 람다 미적분학, 튜링 기계는 최초의 결정론적 모델이었습니다. 랜덤 액세스 머신(RAM 머신이라고도 함)은 실제 컴퓨터를 시뮬레이션하는 데 널리 사용되는 패러다임입니다.

계산 모델이 정의되지 않은 경우 일반적으로 다중 테이프 튜링 기계가 가정됩니다. 멀티테이프 튜링 머신에서 시간 복잡성은 대부분의 알고리즘에 대한 RAM 머신과 동일하지만 데이터가 메모리에 저장되는 방식에 상당한 주의가 요구될 수 있습니다.

비결정적 튜링 기계와 같은 비결정적 컴퓨팅 모델에서 계산의 일부 단계에서 다양한 선택이 이루어질 수 있습니다. 복잡도 이론에서는 가능한 모든 옵션이 동시에 고려되며, 비결정적 시간 복잡도는 항상 최상의 선택이 이루어질 때 필요한 시간입니다. 다시 말해서, 계산은 필요한 만큼 (동일한) 프로세서에서 동시에 수행되며, 비결정적 계산 시간은 첫 번째 프로세서가 계산을 완료하는 데 걸리는 시간입니다. 이 병렬 처리는 Shor의 작은 정수 인수분해와 같은 특수 양자 알고리즘을 실행할 때 중첩된 얽힌 상태를 사용하여 양자 컴퓨팅에서 사용할 수 있습니다.

그러한 계산 모델이 현재 실행 가능하지 않더라도, 특히 "다항식 시간"과 "비결정론적 다항식 시간"을 사용하여 생성된 복잡도 클래스가 최소 상한으로 경계는 동일합니다. 결정론적 컴퓨터에서 NP 알고리즘을 시뮬레이션하려면 "지수 시간"이 필요합니다. 비결정적 시스템에서 다항식 시간 내에 작업을 해결할 수 있는 경우 해당 작업은 NP 난이도 등급에 속합니다. 문제가 NP에 있고 다른 NP 문제보다 쉽지 않은 경우 NP-완전이라고 합니다. 배낭 문제, 여행하는 세일즈맨 문제, 부울 만족 문제는 모두 NP-완전 조합 문제입니다. 가장 잘 알려진 알고리즘은 이러한 모든 문제에 대해 기하급수적으로 복잡합니다. 이러한 문제 중 하나라도 결정론적 기계에서 다항식 시간에 풀릴 수 있다면 모든 NP 문제도 다항식 시간에 풀릴 수 있으며 P = NP가 설정됩니다. 2017년 현재, NP 문제의 최악의 상황은 근본적으로 해결하기 어렵다는 것을 의미하는 P NP가 널리 가정됩니다. 즉, 흥미로운 입력 길이가 주어지면 가능한 시간 범위(수십 년)보다 훨씬 더 오래 걸립니다.

병렬 및 분산 컴퓨팅

병렬 및 분산 컴퓨팅에는 모두 동시에 작동하는 여러 프로세서에 처리를 분할하는 작업이 포함됩니다. 다양한 모델 간의 근본적인 차이점은 프로세서 간에 데이터를 전송하는 방법입니다. 프로세서 간의 데이터 전송은 일반적으로 병렬 컴퓨팅에서 매우 빠른 반면, 분산 컴퓨팅의 프로세서 간의 데이터 전송은 네트워크를 통해 이루어지므로 상당히 느립니다.

N개의 프로세서에 대한 계산은 단일 프로세서에 걸리는 시간의 N만큼 몫 이상을 차지합니다. 실제로 일부 하위 작업은 병렬 처리할 수 없고 일부 프로세서는 다른 프로세서의 결과를 기다려야 할 수 있으므로 이론적으로 이상적인 이 경계는 결코 달성되지 않습니다.

따라서 주요 복잡성 문제는 프로세서 수에 따른 계산 시간의 곱이 단일 프로세서에서 동일한 계산을 수행하는 데 필요한 시간에 최대한 근접하도록 알고리즘을 개발하는 것입니다.

양자 계산

양자 컴퓨터는 양자 역학 기반 계산 모델을 갖춘 컴퓨터입니다. Church–Turing 테제는 양자 컴퓨터에 적용되며, 양자 컴퓨터가 해결할 수 있는 모든 문제는 튜링 기계로도 해결할 수 있음을 의미합니다. 그러나 일부 작업은 이론적으로 시간 복잡성이 현저히 낮은 고전 컴퓨터 대신 양자 컴퓨터를 사용하여 해결할 수 있습니다. 당분간은 실용적인 양자 컴퓨터를 개발하는 방법을 아무도 모르기 때문에 이것은 엄밀히 이론적인 것입니다.

양자 복잡도 이론은 양자 컴퓨터로 해결할 수 있는 다양한 유형의 문제를 조사하기 위해 만들어졌습니다. 양자 컴퓨터 공격에 저항하는 암호화 프로토콜을 생성하는 프로세스인 포스트 양자 암호화에 활용됩니다.

문제의 복잡성(하한)

발견되지 않은 기술을 포함하여 문제를 해결할 수 있는 알고리즘의 복잡성 중 가장 낮은 것은 문제의 복잡성입니다. 결과적으로 문제의 복잡성은 문제를 해결하는 알고리즘의 복잡성과 같습니다.

결과적으로 큰 O 표기법으로 주어진 복잡성은 알고리즘과 수반되는 문제의 복잡성을 나타냅니다.

반면에 문제 복잡성에 대한 중요하지 않은 하한을 얻는 것은 종종 어렵고 이를 위한 전략은 거의 없습니다.

대부분의 문제를 해결하려면 모든 입력 데이터를 읽어야 하며 데이터의 크기에 비례하는 시간이 걸립니다. 결과적으로 이러한 문제는 선형 복잡도 또는 큰 오메가 표기법에서 Ω(n)의 복잡도를 갖습니다.

컴퓨터 대수학 및 계산 대수 기하학의 문제와 같은 일부 문제는 매우 큰 솔루션을 가지고 있습니다. 출력을 작성해야 하기 때문에 복잡성은 출력의 최대 크기로 제한됩니다.

정렬 알고리즘에 필요한 비교 횟수는 Ω(nlogn)의 비선형 하한을 갖습니다. 결과적으로 최상의 정렬 알고리즘은 복잡성이 O(nlogn)이므로 가장 효율적입니다. n이 있다는 사실! n개를 구성하는 방법은 이 하한으로 이어집니다. 각 비교가 n!의 컬렉션을 나누기 때문입니다! 차수를 두 조각으로 나누려면 모든 차수를 구별하는 데 필요한 N 비교 수는 2N > n!이어야 하며, 이는 스털링 공식에 의해 O(nlogn)을 의미합니다.

문제를 다른 문제로 줄이는 것은 복잡성 제약 조건을 줄이기 위한 일반적인 전략입니다.

알고리즘 개발

알고리즘의 복잡성을 평가하는 것은 예상되는 성능에 대한 유용한 정보를 제공하기 때문에 설계 프로세스의 중요한 요소입니다.

현대 컴퓨터 성능의 기하급수적인 성장을 예측하는 무어의 법칙의 결과로 알고리즘의 복잡성을 평가하는 것이 덜 중요해질 것이라는 것은 흔히 오해입니다. 증가된 전력으로 인해 방대한 양의 데이터(빅 데이터)를 처리할 수 있기 때문에 이는 옳지 않습니다. 예를 들어, 어떤 알고리즘이든 책의 참고 문헌과 같이 수백 개의 항목 목록을 알파벳순으로 정렬할 때 2초 이내에 잘 작동해야 합니다. 반면에 백만 개의 항목(예: 대도시의 전화번호)에 대해 O(n10) 비교가 필요한 기본 알고리즘은 30,000,000조의 비교를 수행해야 하며 1,000,000의 속도로 3시간이 걸립니다. 초당 백만 비교. 반면에 Quicksort 및 merge sort는 nlogn 비교만 필요합니다(전자의 경우 평균 복잡성, 후자의 경우 최악의 복잡성). 이것은 n = 10에 대해 약 XNUMX번의 비교를 생성하며, 이는 초당 XNUMX만번의 비교에서 XNUMX초밖에 걸리지 않습니다.

결과적으로 복잡성을 평가하면 구현 전에 많은 비효율적인 알고리즘을 제거할 수 있습니다. 또한 가능한 모든 변형을 테스트하지 않고도 복잡한 알고리즘을 미세 조정하는 데 사용할 수 있습니다. 복잡성에 대한 연구를 통해 복잡한 알고리즘의 가장 비용이 많이 드는 단계를 결정하여 구현의 효율성을 높이는 노력을 집중할 수 있습니다.