계산 복잡성 추정. 알고리즘의 시간 복잡도

알고리즘의 복잡성 결정

점근적 분석에서 얻은 복잡도 함수의 추정치를 알고리즘의 복잡도라고 합니다.

알고리즘의 복잡성에 대한 몇 가지 추정치가 있음을 염두에 두어야 합니다.

복잡도 함수의 점근적 동작은 연산 복잡도입니다. 그 외에도 다음과 같은 유형의 어려움을 지정할 수 있습니다.

일시적인복잡성 - 길이의 입력 데이터에 대한 알고리즘 실행 시간의 점근적 추정 피.분명히, 계산 절차의 병렬화가 없는 경우 알고리즘의 실행 시간은 수행된 작업 수에 따라 고유하게 결정됩니다. 연산 기간을 나타내는 상수 계수는 시간 복잡도의 순서에 영향을 미치지 않으므로 연산 공식과 시간 복잡도 공식이 일치하는 경우가 많습니다.

용량 성복잡성 - 길이의 입력 데이터에 대해 알고리즘을 실행할 때 동시에 존재하는 스칼라 수의 점근적 추정치 피.

구조적복잡성 - 알고리즘의 제어 구조 수와 상대적 위치의 특성.

인지복잡성 - 응용 분야의 전문가가 이해할 수 있는 알고리즘 가용성의 특성.

점근선의 유형과 표기법

알고리즘의 점근적 분석에서 수학적 점근적 분석의 표기법을 사용하는 것이 일반적입니다. 이 경우 알고리즘의 복잡성에 대한 세 가지 추정값(점근법)이 고려되며 다음과 같이 표시됩니다.

• 1) /(i) = 오^(n))- 복잡도 함수 /(«)의 점근적으로 정확한 추정 또는 알고리즘의 연산 복잡도
• 2) /(n) = 0(§(n)) -복잡도 함수의 점근적으로 정확한 상한 추정치 /( 피);
• 3) /(l) = ?2(#(l)) - 노동 투입 함수의 점근적으로 정확한 하한 추정치 /( 피).

지정 대신 C1^(n))매우 자주 간단한 o(^("))가 "o" 소문자 필기체와 함께 사용됩니다.

예를 사용하여 공식의 의미를 설명하겠습니다. 만약 /(n) = 0 (^2(n))이라고 쓰여지면, THEN THIS는 다음을 의미합니다. g(n)=og2 (N)복잡도 함수 /(«)의 점근적으로 정확한 추정값입니다. 사실, 주장 형태의 두 가지 입장 정의가 있습니다.

f(n)인 경우= @(log2(")),

모 g(n)\u003d 로그 2(l) - f(n)의 점근적으로 정확한 추정.

상수 인자는 알고리즘의 복잡도 차수에 영향을 미치지 않으므로 대수 복잡도를 지정할 때 대수의 밑이 생략되고 단순히 f(l) = @(lо§(l))로 작성합니다. 즉, 로그는 1보다 큰 임의의 밑을 가집니다.

점근선의 형식적 정의

노동 투입 함수의 점근적으로 정확한 추정치와 함께, 와 함께 2 , l 0 , l>l 0 에 대해 함수 /(l)은 상수 요인까지 함수와 다르지 않습니다. g( k), 함수 지(n)함수 /(k)의 점근적으로 정확한 추정이라고 합니다.

• 3 s ] , s 2 e그리고, x와 함께 > 0, 2 > 0:
  • (3 l 0 e K, l 0 > 0: (/l e K, l > l 0:0 g(n) /(l) = 0(?(l)),

여기서 9^, N은 각각 모든 실수와 자연수의 집합입니다.

복잡성 함수에 대한 점근적으로 정확한 상한다음과 같이 구두로 정의됩니다: 양수가 있는 경우 와 함께및 l 0 , l>l 0에 대해 함수 /(l)은 함수보다 더 빠르게 성장하지 않습니다. 지(n)상수 인자 c까지, 그 다음 함수 지(n)함수에 대한 점근적으로 정확한 상한이라고 합니다. 아).

보다 정확한 형식 정의는 다음과 같은 형식을 갖습니다.

• 3 와 함께이자형 %s > 0:
  • (3 l 0 e X, l 0 > 0: (/l e K, l > l 0:0 s? #(l))) 0(g(n))

복잡성 함수에 대한 점근적으로 정확한 하한다음과 같이 구두로 정의됩니다: 양수가 있는 경우 와 함께및 l 0 , l>l 0에 대해 함수 /(l)은 함수보다 느리게 성장하지 않습니다. 지(n)일정한 요소까지 와 함께,그러면 함수?(k)는 함수에 대한 점근적으로 정확한 하한이라고 합니다.

보다 정확한 형식 정의는 다음과 같은 형식을 갖습니다.

• 3 와 함께전자 9^, 와 함께 > 0:
  • (3 i 0 e X, i 0 > 0: (/i e K, i > 나 0: 0초? 지(n)

/(나) = 0.^(n))

다음에 유의하십시오.

• 1) 일반적으로 점근선의 형식적 정의에 표시된 부등식은 하나가 아니라 특정 함수 집합에 의해 충족될 수 있으며 종종 셀 수 없는 항 집합으로 충족될 수 있으므로 구성 Q(g(n)), 0^(n))그리고 0.^(n))상징하다 기능 세트, 노동 투입 /(i)의 조사된 기능이 비교됩니다. 이 때문에 /(n) = 0(?(n)), /(/0 = 0(?max(n)), Dn) = ?2(?m1n(n) 형식의 점근법 표기법에서 )) "= » 기호 대신 "e" 기호를 사용하는 것이 더 합리적입니다.
• 2) 디자인 (d^(n)), 0^(n))그리고 ?1^(n)),특정 수량에 대한 기호로 사용되는 경우 다음과 같이 읽어야 합니다. 동일한 기능, 더 빠르게 증가하지 않고 더 느리게 증가하지 않는 기능 지(n).

점근선의 일치와 차이점

다음 사실에 주의합시다. 추정치 /(s) = 0(?(s))는 /(s)에 대한 상한 및 하한 추정치를 모두 설정합니다. 그 정의는 관계의 유효성을 가정하기 때문입니다. c g g(n)

점근선의 다음 속성은 매우 분명합니다. φ(n) = ©^(n))존재하면 평등 /( 피) = 0(^(n)) 및 /(n) = ?2(#(n)), 즉 노동 강도의 상한 및 하한 추정치는 서로 일치합니다. /(i) = 0(? 최대(i))인 경우 및 φ(n) = C1^ mn(n)), 그리고 g 최대 (n)Фg m 1n(i), 함수가 없습니다 g(n),/(i) = 0(?(i))입니다.

다음과 같은 경우 노동 강도의 상한 및 하한 추정치가 일치할 수 있습니다.

• 1) 입력 길이의 모든 값에 대한 복잡도 함수는 결정적(비무작위) 함수입니다. 수행되는 작업의 수는 초기 데이터 값의 세부 사항에 의존하지 않습니다. 예를 들어, IS 확장 방법으로 선형 대수 방정식 시스템을 풀기 위한 알고리즘에서 알 수 없는 양의 수에 대한 곱셈 및 나눗셈 연산 수의 종속 함수입니다.
• 2) 노동 집약도 함수는 랜덤 함수입니다. 수행되는 작업의 수는 초기 데이터의 세부 사항 및(또는) 도착 순서에 따라 다르며 함수 / m |을 지정할 수 있습니다. 같은 주문.

운영 복잡성의 순서를 추정할 때 염두에 두어야 할 세 가지 중요한 규칙이 있습니다.

• 1) 상수 요소는 복잡성의 순서를 결정하는 데 중요하지 않습니다. 0 (k?g(n)) = 0(g(")) ;
• 2) 평등이 참이기 때문에 두 함수 곱의 복잡성 차수는 복잡성의 곱과 같습니다.
• 0(gl(i) §2(i)) = 0 (?| (i)) 0 (#2(i)) ;
• 3) 함수 합계의 복잡성 순서는 항의 지배적인 순서와 같습니다. 예: 0(i e + n 2 + n) = 0(i 5).

위의 규칙은 단 하나의 점근선 0(") 기호를 사용하지만 모든 점근선 추정치에 대해 유효합니다. 0( ) , 그리고 &.{ ).

기본 기능 세트에서 기능 우위 목록을 지정할 수 있습니다. 가 변수인 경우 에이, ㄴ-숫자 상수이면 다음 진술이 참입니다. 아"; 아" Zj를 지배"하는 경우 > 피지배하다 피 b, 만약 ㅏ> 1 비전자 9? ; 나지배하다/만약 > ㄴ i는 로그 q(i)를 지배합니다. ㅏ > 1.

평균 노동 집약도 추정

실무에서 다시 대부분의 경우 /(n)은 랜덤 함수이기 때문에 중요한 계산은 M의 복잡성에 대한 수학적 기대치의 추정치 /(n)입니다. 그러나 무작위 /(n) 알고리즘에 대한 실험적 연구 과정에서 M의 신뢰할 수 있는 추정치를 위한 시행 횟수 선택과 같은 추가 문제가 발생합니다. 이 문제를 극복하는 것이 의 중심 작업입니다. 제안된 솔루션은 /(n)을 근사하기 위한 베타 분포의 사용을 기반으로 합니다. 이것은 매우 건설적이고 다재다능한 기술입니다. 그러나 현대의 조건에서는 컴퓨터 성능이 상당히 높을 때 값의 현재 변동성을 모니터링하는 것을 기반으로 테스트 범위를 선택하는 더 간단한 방법을 사용할 수 있는 경우가 많습니다. f(n) -값은 추정치의 분산이 지정된 오류보다 작아질 때까지 추정됩니다.

알고리즘의 연산 복잡성 추정

알고리즘의 복잡성은 제어 구조의 분석을 기반으로 결정할 수 있습니다. 루프와 재귀 호출이 없는 알고리즘은 항상 복잡합니다. 따라서 알고리즘의 복잡성에 대한 정의는 주로 순환 및 재귀 호출 분석으로 축소됩니다.

삭제 알고리즘 고려 에게-크기의 배열에서 요소 피, 배열의 요소를 에서 이동하는 것으로 구성 (+로 1) - 일 피- 배열의 시작 부분으로 한 위치 뒤로 이동하여 요소 수 감소 피유닛 당. 배열 처리 루프의 복잡성은 다음과 같습니다. 오 (p-k),루프 본문(이동 작업)이 실행되기 때문에 PC시간이고 루프 본문의 복잡성은 0(1)입니다. 상수입니다.

고려 중인 예에서 복잡성은 점근법 0(")으로 특징지어집니다. 이 알고리즘에서 수행되는 연산의 수가 데이터 값의 세부 사항에 의존하지 않기 때문입니다. 복잡성 함수는 결정적이며 모든 종류의 점근선이 서로 일치합니다. f(n) = Q(n-k), f(n) = 0(n-k)그리고 f(n) = Q(n-에서). 이 사실은 정확히 ©( )의 표시에 의해 입증됩니다. 이러한 점근선이 다른 경우에만 0(*) 및/또는?2(*)를 사용하십시오.

루프 유형(for, while, repeat)은 복잡성에 영향을 미치지 않습니다. 하나의 루프가 다른 루프 내에 중첩되어 있고 두 루프가 동일한 변수의 크기에 의존하는 경우 전체 구성은 2차 복잡성을 특징으로 합니다. 반복의 중첩은 복잡성 증가의 주요 요인입니다. 예를 들어, 크기 배열에 대해 잘 알려진 검색 및 정렬 알고리즘의 복잡성을 제시합니다. 피:

• 순차 검색에서 비교 연산의 수: 0(n);
• 이진 검색의 비교 연산 수: 0(log 2 피);
• 단순 교환 방식(버블 정렬)의 비교 연산 횟수: 0(n 2);
• 버블 정렬의 순열 연산 수: 0(n 2);

단순 교환 방법에서 비교 연산의 수는 점근적 0(n 2) 순열 연산의 수는 두 가지 다른 점근법을 가집니다. 0(2쪽)및 ?2(0), 비교 횟수는 정렬된 데이터 값의 특이성에 의존하지 않는 반면 순열의 개수는 이 특이성에 의해 결정되기 때문입니다. 데이터 배열이 처음에 올바르게 정렬되었거나 순열 수가 최대일 수 있는 경우 순열이 전혀 수행되지 않을 수 있습니다. 피 2 , - 정렬된 배열이 처음에 반대 방향으로 정렬된 경우.

기능 이름 지(n)점근법에서 /(x) = @(x(x)) 및 /(a) = 0(g(n))복잡성 함수 /(«)는 알고리즘을 특성화하는 데 사용됩니다. 따라서 다항식, 지수, 로그 등의 복잡성 알고리즘에 대해 이야기합니다.

확실히 당신은 O(log n)와 같은 표기법을 접하거나 알고리즘과 관련하여 "대수 계산 복잡성"과 같은 문구를 들었습니다. 그리고 이것이 의미하는 바를 여전히 이해하지 못한다면 이 기사는 당신을 위한 것입니다.

난이도

알고리즘의 복잡성은 일반적으로 실행 시간이나 사용된 메모리로 추정됩니다. 두 경우 모두 복잡성은 입력 데이터의 크기에 따라 다릅니다. 100개의 요소로 구성된 배열은 1000개의 유사한 요소보다 빠르게 처리됩니다. 동시에 정확한 시간에 대해 신경 쓰는 사람은 거의 없습니다. 프로세서에 따라 다릅니다. 데이터 유형, 프로그래밍 언어 및 기타 여러 매개변수. 점근적 복잡도만 중요합니다. 즉, 입력 크기가 무한대가 되는 경향이 있는 복잡도입니다.

어떤 알고리즘이 n개의 입력 데이터 요소를 처리하기 위해 4n 3 + 7n 조건부 연산을 실행해야 한다고 가정해 봅시다. n이 증가함에 따라 총 실행 시간은 4를 곱하거나 7n을 추가하는 것보다 n을 큐브로 올리는 것이 훨씬 더 큰 영향을 받습니다. 그런 다음 우리는 이 알고리즘의 시간 복잡도가 O(n 3) 과 같다고 말합니다. 즉, 입력 데이터의 크기에 3차로 의존합니다.

대문자 O(또는 소위 O 표기법)의 사용은 함수의 점근적 동작을 비교하는 데 사용되는 수학에서 유래했습니다. 공식적으로 O(f(n)) 은 알고리즘의 실행 시간(또는 점유된 메모리 양)이 f(n) 을 곱한 상수보다 빠르지 않은 입력 데이터 양에 따라 증가한다는 것을 의미합니다.

예

O(n) - 선형 복잡성

예를 들어 이러한 복잡성에는 정렬되지 않은 배열에서 가장 큰 요소를 찾는 알고리즘이 있습니다. 어느 것이 가장 큰지 알아내기 위해 배열의 모든 n개 요소를 살펴봐야 합니다.

O(log n) - 로그 복잡성

가장 간단한 예는 이진 검색입니다. 배열이 정렬되면 이등분하여 특정 값이 포함되어 있는지 확인할 수 있습니다. 중간 요소를 확인하고 원하는 것보다 크면 배열의 후반부를 버릴 것입니다. 분명히 존재하지 않습니다. 적으면 그 반대도 마찬가지입니다. 처음 절반을 버립니다. 그래서 우리는 계속해서 반으로 나눌 것이고 결과적으로 log n개의 요소를 확인할 것입니다.

O(n 2) - 2차 복잡도

이러한 복잡성에는 예를 들어 삽입 정렬 알고리즘이 있습니다. 표준 구현에서는 두 개의 중첩 루프로 구성됩니다. 하나는 전체 배열을 살펴보고 다른 하나는 이미 정렬된 부분에서 다음 요소의 위치를 ​​찾는 것입니다. 따라서 작업 수는 배열의 크기에 따라 n * n , 즉 n 2 입니다.

다른 난이도 등급이 있지만 모두 동일한 원리를 기반으로 합니다.

또한 알고리즘의 실행 시간이 입력 데이터의 크기에 전혀 의존하지 않는 경우도 발생합니다. 그런 다음 복잡성은 O(1) 로 표시됩니다. 예를 들어, 배열의 세 번째 요소 값을 결정하기 위해 요소를 기억하거나 여러 번 반복할 필요가 없습니다. 항상 입력 데이터 스트림의 세 번째 요소를 기다려야 하며 이것이 결과가 되며 데이터 양에 관계없이 계산하는 데 같은 시간이 걸립니다.

마찬가지로 평가는 중요할 때 메모리에서 수행됩니다. 그러나 알고리즘은 다른 것보다 입력 데이터의 크기를 늘릴 때 훨씬 더 많은 메모리를 사용할 수 있지만 여전히 더 빠르게 실행됩니다. 그 반대. 이것은 현재 조건과 요구 사항을 기반으로 문제를 해결하는 가장 좋은 방법을 선택하는 데 도움이 됩니다.

마감일 이전에는 다른 프로젝트 참가자가 기사를 편집해서는 안 됩니다. 웹사이트. 마지막으로 모든 참가자는 자신의 재량에 따라 이 기사를 수정하고 템플릿((작업))을 사용하여 표시되는 이 경고를 삭제할 권리가 있습니다.

또한보십시오 지침리소스 사용에 대해 웹사이트교육 과정에서.

계산 복잡도 이론계산 문제를 해결하는 데 필요한 작업량을 연구하는 계산 이론의 한 분야.

문제 해결에 사용된 알고리즘에 관계없이 문제 해결에 많은 리소스가 필요한 경우 작업이 어려운 것으로 간주됩니다. 이론은 이러한 문제를 연구하고 시간 및 메모리 사용량과 같은 문제를 해결하는 데 필요한 리소스의 양을 수량화하기 위해 계산의 수학적 모델을 도입함으로써 이 직관적인 개념을 공식화합니다. 메시지 수(통신 복잡성), 기능 요소 회로의 요소 수(회로 복잡성) 및 프로세서 수와 같은 다른 복잡성 측정이 가능합니다. 특히, 계산 복잡도 이론은 컴퓨터가 할 수 있는 것과 할 수 없는 것에 대한 실질적인 한계를 정의합니다.

계산 복잡도 이론과 밀접하게 관련된 것은 알고리즘 분석과 계산 가능성 이론입니다. 계산 복잡도 이론과 알고리즘 분석의 주요 차이점은 후자는 문제를 해결하기 위해 특정 알고리즘이 필요로 하는 리소스의 양에 대한 분석을 다루는 반면 전자는 문제 해결에 사용할 수 있는 모든 가능한 알고리즘에 대해 보다 일반적인 질문을 한다는 것입니다. 같은 문제를 해결하십시오. 더 정확하게 말하면, 계산 복잡도 이론은 적절한 양의 제한된 자원으로 해결될 수도 있고 해결되지 않을 수도 있는 문제를 분류하려고 시도합니다. 차례로, 사용 가능한 자원에 대한 제한의 부과는 계산 복잡성 이론을 계산 가능성 이론과 구별하는 것입니다. 후자는 계산 자원을 제한하지 않고 원칙적으로 알고리즘적으로 어떤 문제를 해결할 수 있는지 묻습니다.

계산 문제

태스크 인스턴스

계산 문제(문제)는 무한한 쌍의 집합으로 볼 수 있습니다. (문제 사례, 주어진 사례에 대한 솔루션). 계산 문제에 대한 입력 문자열은 문제 인스턴스를 설명하는 문자열입니다. 계산 문제에 대한 출력 문자열은 입력 문자열에 의해 설명된 문제 인스턴스에 대한 솔루션에 대한 설명입니다. 예를 들어, 숫자의 소수를 인식하는 문제: 문제의 인스턴스는 소수인지 여부를 결정해야 하는 숫자이고, 이 숫자가 소수이면 솔루션은 문자열 "yes"이고 "no " 그렇지 않으면. 계산 복잡도 이론은 거대한 문제만 고려합니다. 작업 인스턴스 집합이 무한해야 한다는 요구 사항은 필수입니다.

작업 보기

계산 문제를 고려할 때 문제 인스턴스에 대한 설명은 알파벳 위의 문자열입니다. 일반적으로 알파벳은 이진법으로 간주됩니다(즉, 집합 (0,1)). 이에 따라 다양한 수학적 객체가 인코딩되어야 합니다. 따라서 예를 들어 정수는 이진법으로 표시될 수 있고 그래프는 인접 행렬을 통해 직접 또는 이진법으로 인접 목록을 인코딩하여 인코딩할 수 있습니다.

인식 작업

인식의 문제는 계산 복잡성 이론에서 연구의 중심 대상 중 하나입니다. 인식 문제는 "예" 또는 "아니오"(1 또는 0)로 답하는 특수한 유형의 계산 문제입니다. 인식 문제는 입력 문자열이 모든 입력 문자열 집합의 특정 하위 집합(언어)에 속하는지 여부의 문제로 공식화될 수 있습니다. 문제의 입력 문자열은 이 문자열에 대한 대답이 "예"인 경우에만 해당 언어에 속합니다. 따라서 인식 작업은 입력 문자열이 특정 언어에 속해 있음을 인식하는 작업입니다.

인식 문제의 예. 입력 문자열: 임의의 그래프에 대한 설명입니다. 문제는 주어진 그래프가 연결되어 있는지 여부를 결정하는 것입니다. 연결된 그래프의 언어는 연결된 모든 그래프에 대한 설명의 집합입니다. 이 언어의 정확한 정의를 얻으려면 그래프가 이진 문자열로 인코딩되는 방법을 결정해야 합니다.

작업 검색

검색 작업은 인식 작업보다 출력 값이 더 복잡한 계산 작업입니다(즉, "예" 또는 "아니오"가 아님).

탐색 문제의 예는 여행하는 세일즈맨 문제입니다. 여행 판매원 문제(여행 판매원)는 가장 유명한 조합 최적화 문제 중 하나입니다. 임무는 지정된 도시를 한 번 이상 통과한 다음 원래 도시로 돌아가는 가장 수익성 있는 경로를 찾는 것입니다. 문제의 조건에서는 경로 수익성 기준(최단, 가장 저렴한, 누적 기준 등)과 거리, 비용 등의 해당 행렬이 표시되며, 일반적으로 경로가 통과해야 함을 표시합니다. 각 도시는 한 번만 - 이 경우 Hamiltonian 주기 중에서 선택합니다. 입력 문자열: 가중치(가장자리에 숫자 표시 포함) 그래프에 대한 설명. 출력 문자열은 최적의 출장 판매원 경로에 대한 설명입니다.

인식 작업과 검색 작업 사이에는 쌍 관계가 있습니다. 탐색 문제는 인식 문제로 공식화할 수 있습니다. 예를 들어, "두 수의 곱하기" 검색 문제의 경우 해당 쌍 인식 문제는 A × B = C의 관계를 만족하는 트리플(A, B, C)의 집합으로 나타낼 수 있습니다.

측정난이도

계산 복잡도 이론은 알고리즘의 속도를 비교하고 입력과 출력의 크기에 따라 알고리즘의 동작(실행 시간, 필요한 메모리 양 등)을 명확하게 설명해야 할 필요성에서 나왔습니다.

문제의 특정 인스턴스를 해결하기 위해 알고리즘이 사용하는 기본 작업의 수는 입력 데이터의 크기뿐만 아니라 데이터 자체에도 따라 달라집니다. 예를 들어, 입력 데이터가 이미 정렬되어 있는 경우 삽입 정렬 알고리즘의 작업 수는 훨씬 적습니다. 이러한 어려움을 피하기 위해 최악의 경우 알고리즘의 시간 복잡도 개념을 고려하십시오.

알고리즘의 시간 복잡도(최악의 경우)는 입력 및 출력 데이터 크기의 함수로, 지정된 크기의 문제 인스턴스를 해결하기 위해 알고리즘이 수행하는 기본 연산의 최대 수와 같습니다. 출력 크기가 입력 크기를 초과하지 않거나 비례하는 문제에서 시간 복잡도는 입력 데이터 크기의 함수로만 생각할 수 있습니다.

최악의 경우의 시간복잡도 개념과 유사하게 최선의 경우 알고리즘의 시간복잡도 개념을 정의한다. 또한 알고리즘의 평균 시간 개념, 즉 알고리즘 시간의 수학적 기대치를 고려하십시오. 때로는 "알고리즘의 시간 복잡도" 또는 "알고리즘의 시간"으로 간단히 말하며 최악의 경우, 최상의 경우 또는 평균적인 경우(컨텍스트에 따라 다름) 알고리즘의 시간 복잡도를 나타냅니다.

시간 복잡도와 유추하여 알고리즘의 공간 복잡도를 결정합니다. 여기서만 기본 작업 수가 아니라 사용된 메모리 양에 대해 이야기하고 있습니다.

알고리즘의 시간복잡도 함수는 어떤 경우에는 정확히 결정될 수 있음에도 불구하고 대부분의 경우 정확한 값을 찾는 것은 의미가 없습니다. 요점은 첫째, 시간 복잡도의 정확한 값은 기본 연산의 정의(예: 복잡도는 산술 연산 또는 Turing 기계에서 연산의 수로 측정될 수 있음)에 따라 다르며, 둘째, 입력 데이터가 증가하면 정확한 작동 시간에 대한 표현식에 나타나는 상수 요인과 낮은 차수의 항의 기여가 극히 미미해집니다.

큰 입력 데이터를 고려하고 알고리즘 실행 시간의 증가 순서를 추정하면 알고리즘의 점근적 복잡성 개념이 나옵니다. 동시에 작은 크기의 데이터를 제외하고는 점근적 복잡성이 덜한 알고리즘이 모든 입력 데이터에 대해 더 효율적입니다.

복잡성은 계산이 수행되는 계산 모델을 기반으로 결정됩니다.

계산 모델

Post machine, Minsky machine, lambda calculus, partial recursive functions, normal Markov algorithm, machines with random access to memory (RAM machines) 등 다양한 계산 모델이 있습니다. 가장 인기 있는 계산 모델인 Turing만 언급하겠습니다. 기계.

튜링 머신

튜링 머신(MT)은 추상 실행기(추상 컴퓨터)입니다. 알고리즘의 개념을 공식화하기 위해 1936년 Alan Turing이 제안했습니다.

튜링 기계는 유한 자동 장치의 확장이며 Church-Turing 테제에 따르면 단계별 계산 프로세스를 어떻게든 구현하는 다른 모든 실행자를 모방할 수 있습니다(전환 규칙 설정). 단계는 아주 기초적입니다.

Turing 기계의 구성은 양방향으로 무한한 테이프(무한한 테이프가 여러 개 있는 Turing 기계가 가능), 셀로 분할된 테이프 및 여러 상태 중 하나에 있을 수 있는 제어 장치로 구성됩니다. 제어 장치의 가능한 상태의 수는 유한하고 정확하게 주어집니다.

제어 장치는 테이프를 따라 왼쪽과 오른쪽으로 이동할 수 있고 테이프 셀에 유한 알파벳의 문자를 읽고 쓸 수 있습니다. 특수 빈 기호가 할당되어 입력 데이터가 기록되는 셀(유한한 수)을 제외하고 테이프의 모든 셀을 채웁니다.

제어 장치는 이 튜링 기계에 의해 구현된 알고리즘을 나타내는 전환 규칙에 따라 작동합니다. 각 전환 규칙은 현재 상태와 현재 셀에서 관찰된 기호에 따라 이 셀에 새 기호를 쓰고 새 상태로 이동하고 한 셀을 왼쪽 또는 오른쪽으로 이동하도록 기계에 지시합니다. Turing 기계의 일부 상태는 터미널로 표시될 수 있으며 그 중 하나로의 전환은 작업의 끝, 알고리즘의 중지를 의미합니다.

튜링 기계는 테이블의 상태와 리본 기호의 각 조합이 최대 하나의 규칙에 해당하는 경우 결정적이라고 합니다. 2개 이상의 명령이 있는 쌍(테이프 기호 - 상태)이 있는 경우 이러한 튜링 기계를 비결정적이라고 합니다.

Turing 기계 모델은 다양한 확장을 허용합니다. 임의의 수의 테이프와 다른 제약 조건을 가진 다차원 테이프가 있는 튜링 기계를 고려할 수 있습니다. 임의성의 소스를 사용하는 기계.

튜링 머신은 복잡성 이론에서 계산의 주요 모델 중 하나입니다.

난이도 클래스

복잡성 클래스는 계산 복잡성 측면에서 거의 동일한 계산 문제 집합입니다. 언어 복잡도 클래스와 기능 복잡도 클래스가 있습니다. 언어의 복잡성 클래스는 계산에 거의 동일한 양의 리소스를 사용하는 술어 세트(단어를 입력으로 사용하고 0 또는 1의 응답을 반환하는 함수)입니다. 기능적 복잡성 클래스의 개념은 술어의 집합이 아니라 함수의 집합이라는 점을 제외하면 유사합니다. 복잡성 이론에서 기본적으로 복잡성 클래스는 언어의 복잡성 클래스입니다. 복잡도 클래스의 일반적인 정의는 다음과 같습니다.

복잡도 클래스 X는 튜링 기계에서 계산할 수 있고 계산을 위해 O(f(n)) 리소스를 사용하는 술어 P(x)의 집합입니다. 여기서 n은 단어 x의 길이입니다.

자원으로는 일반적으로 계산 시간(튜링 기계의 작업 주기 수) 또는 작업 영역(작업 중에 사용되는 테이프의 셀 수)이 사용됩니다. 특정 클래스의 술어로 인식되는 언어(즉, 술어가 1을 반환하는 단어 집합)도 같은 클래스에 속한다고 합니다.

또한 많은 수업을 수학적 논리나 게임 이론으로 설명할 수도 있습니다.

클래스는 일반적으로 대문자로 표시됩니다. 클래스 C에 대한 보완(즉, 보완이 C에 속하는 언어 클래스)은 co-C로 표시됩니다.

각 클래스에는 "가장 어려운" 작업 범주가 있습니다. 즉, 클래스의 모든 작업은 이러한 작업으로 축소되고 작업 자체는 클래스에 있습니다. 이러한 문제를 주어진 클래스에 대한 완전한 문제라고 합니다.

클래스 P

클래스 P(영어 다항식에서) - 입력 길이에 대한 다항식 시간에 결정론적 튜링 기계에서 해결할 수 있는 일련의 인식 문제. 유사하게, 검색 문제의 경우 클래스 FP(영어 기능 다항식에서)가 정의됩니다.

보다 형식적으로, 입력 알파벳에서 입력 테이프의 단어가 주어지면 답을 계산하는 결정론적 튜링 기계를 고려하십시오. 고정 입력 단어에 대한 튜링 머신의 실행 시간 엑스튜링 기계의 시작부터 정지까지의 작동 주기 수입니다. 일부 튜링 기계에 의해 계산된 함수의 복잡성은 입력 단어의 길이에 의존하는 함수이며 고정 길이의 모든 입력 단어에 대한 기계의 최대 실행 시간과 같습니다.

기능에 대한 경우 에프튜링 기계가 있다 중어떤 숫자에 대해 씨그리고 충분히 크다 N, 그러면 FP 클래스에 속하거나 시간이 다항식이라고 말합니다.

P 클래스는 계산 복잡성 이론의 기본 클래스 중 하나입니다.

NP 클래스

NP 클래스(영어 비결정적 다항식에서)는 인식 문제 세트로, 해결 시간은 입력 데이터의 크기에 크게 의존합니다. 동시에 입력 값에 대한 설명과 함께 일부 추가 정보(해법에 대한 증인)를 수신한 후 충분히 신속하게(데이터 크기의 다항식을 초과하지 않는 시간에) 해결할 수 있는 알고리즘이 있습니다. 문제.

더 공식적으로, 언어 L은 클래스 P(즉, 다항식 시간에 계산 가능)에서 2자리 술어 R(x, y)이 있고 다항식 p가 다음과 같은 다항식 p가 있는 경우 클래스 NP에 속한다고 합니다. 길이 n의 x 조건 "x는 L에 속한다"는 "R(x, y)가 참이 되도록 길이가 p(n)보다 작은 y가 있다"는 조건과 동일합니다. 단어 y는 x가 언어 L에 속하는 증인이라고 합니다. 따라서 언어에 속하는 단어와 제한된 길이의 다른 증인 단어(찾기가 어려울 수 있음)가 있는 경우 신속하게 다음을 확인할 수 있습니다. x는 실제로 L에 속합니다. NP에 속하는 모든 문제는 p(n)보다 작은 길이의 가능한 모든 증인을 열거함으로써 지수 시간으로 해결할 수 있습니다.

NP 문제의 예: 인식 문제 "선형 부등식 시스템에 대한 정수 솔루션의 존재". 증인은 불평등 체계의 해결책입니다. 증인 솔루션이 맞는 다항식 시간을 확인하는 것은 쉽습니다.

NP 클래스에는 P 클래스가 포함됩니다.

열린 문제

계산 복잡성 이론에는 해결되지 않은 많은 문제가 있으며 주로 특정 복잡성 클래스의 분리 또는 중첩 문제와 관련됩니다. 이러한 질문 중 하나는 클래스 P와 NP의 평등 문제입니다.

클래스 P와 NP의 평등 문제

궁극적으로 클래스 P와 NP의 동등성 문제는 다음과 같습니다. 어떤 질문에 대한 긍정적인 대답을 빠르게 확인할 수 있다면(다항식 시간), 이 질문에 대한 답을 빨리 찾을 수 있다는 것이 사실입니까(다항식 시간 )?

클래스 P 및 NP의 정의에서 바로 다음과 같은 결과가 나옵니다. 그러나 이 포함의 엄격성에 대해서는 지금까지 알려진 바가 없습니다. NP에는 있지만 P에는 없는 알고리즘이 있는지 여부. 그러한 알고리즘이 없는 경우 클래스 NP에 속하는 모든 문제는 다항식 시간에 해결될 수 있으며, 이는 엄청난 계산상의 이점을 약속합니다. 이제 가장 어려운 NP 문제(소위 NP 완전 문제)를 지수 시간 내에 해결할 수 있으며, 이는 거의 항상 허용되지 않습니다.

이 두 클래스의 평등에 대한 문제는 이론적 컴퓨터 과학 분야에서 가장 어려운 공개 문제 중 하나로 간주됩니다. 현재 대부분의 수학자들은 이러한 클래스가 동일하지 않다고 생각합니다. Clay Mathematics Institute는 이 문제를 Millennium Problems 목록에 포함시켰고 이 문제를 해결하면 백만 달러의 보상을 제공합니다.

문학

1. Gehry M., Johnson D. 컴퓨터 및 해결하기 어려운 문제. 1982년 미르출판사. - 420p. 미국 과학자들의 논문은 이산 최적화, 수학 프로그래밍, 대수학, 자동 이론에서 발생하는 복잡한(NP-하드 포함) 조합 문제를 예제와 함께 해결하는 데 전념합니다.
2. Kormen, Thomas H.; Leizerson, Charles I.; Rivest, Ronald L.; Stein, Clifford 알고리즘: 구성 및 분석, 2판 = 알고리즘 소개 2판. - M.: "Williams", 2005. -

우리는 이미 정확성이 좋은 프로그램이 갖추어야 할 유일한 품질과는 거리가 멀다는 것을 알고 있습니다. 가장 중요한 것 중 하나는 효율성입니다. 리드 타임다양한 입력 데이터(파라미터)를 위한 프로그램.

특정 프로그램에 대한 정확한 종속성을 찾는 것은 다소 어려운 작업입니다. 이러한 이유로 일반적으로 제한적입니다. 점근적 추정치이 함수, 즉 매개변수의 큰 값에 대한 대략적인 동작에 대한 설명입니다. 때때로 점근적 추정을 위해 두 함수 사이의 전통적인 관계("Big O"로 읽음)가 사용됩니다. , 더 일반적으로 사용되지만 수학 분석에 관한 모든 교과서에서 그 정의를 찾을 수 있습니다. 등가 관계("세타 빅"을 읽으십시오). 그것의 공식적인 정의는 예를 들어 책에 나와 있지만 지금은 이 문제를 일반적인 용어로 이해하는 것으로 충분할 것입니다.

첫 번째 예로서, 숫자의 계승을 찾기 위해 방금 고려했던 프로그램으로 돌아가 보겠습니다. 계승을 찾기 위해 수행해야 하는 연산의 수를 쉽게 알 수 있습니다! 첫 번째 근사값의 수는 이 수에 정비례합니다. 이 프로그램에서 주기(반복)의 반복 횟수가 와 같기 때문입니다. 그러한 상황에서 프로그램(또는 알고리즘)이 선형 복잡성(복잡성 또는).

계승을 더 빠르게 계산할 수 있습니까? 그것은 예로 밝혀졌습니다. 반복이나 재귀를 사용하지 않고 위의 모든 프로그램이 수행하는 동일한 값에 대해 올바른 결과를 제공하는 프로그램을 작성할 수 있습니다. 복잡성은 , 실제로 순환 및 재귀 호출을 사용하지 않고 일부 공식에 따라 계산 구성을 의미합니다!

덜 흥미로운 것은 th 피보나치 수를 계산하는 예입니다. 연구 과정에서 사실 이미 그 복잡성이 지수및 같음 . 이러한 프로그램은 실제로 적용되지 않습니다. 이것은 40번째 피보나치 수를 계산하려고 하면 매우 쉽게 확인할 수 있습니다. 이러한 이유로 다음 문제는 매우 관련이 있습니다.

작업 5.4 선형 복잡성.

다음은 변수 j와 k가 두 개의 연속적인 피보나치 수의 값을 포함하는 이 문제에 대한 솔루션입니다.

프로그램 텍스트

public class FibIv1 ( public static void main(String args) 예외 발생 ( int n = Xterm.inputInt("Enter n ->< 0) { Xterm.print(" не определено\n"); } else if (n < 2) { Xterm.println(" = " + n); } else { long i = 0; long j = 1; long k; int m = n; while (--m >0) ( k = j; j += i; i = k; ) Xterm.println(" = " + j); ) ) )

다음 질문은 매우 자연스럽습니다. 피보나치 수를 더 빨리 찾을 수 있습니까?

수학의 특정 섹션을 공부한 후에 -th 피보나치 수에 대한 다음 공식을 유도하는 것은 매우 간단합니다. 이는 작은 값을 확인하기 쉽습니다.

이를 기반으로 반복이나 재귀를 사용하지 않는 복잡한 프로그램을 작성하는 것이 쉬워 보일 수 있습니다.

프로그램 텍스트

공용 클래스 FibIv2(공용 정적 무효 메인(문자열 인수)는 예외를 발생시킵니다( int n = Xterm.inputInt("Enter n -> "); double f = (1.0 + Math.sqrt(5.)) / 2.0; int j = (int)(Math.pow(f,n) / Math.sqrt(5.) + 0.5); Xterm.println("f(" + n + ") = " + j); ) )

실제로 이 프로그램은 지수 함수( Math.pow(f,n) )에 대한 호출을 사용합니다. 이 함수는 대수 시간()보다 빠르게 구현할 수 없습니다. 연산 수가 대략 비례하는 알고리즘(컴퓨터 과학에서는 이진 로그의 밑을 표시하지 않는 것이 일반적임)에 대해 다음과 같이 말합니다. 로그 복잡도 ().

th 피보나치 수를 계산하기 위해 그러한 알고리즘이 있습니다. 소프트웨어 구현은 추가 설명 없이 제공됩니다. 그렇지 않으면 너무 많이 설명해야 합니다(피보나치 수와 2차의 특정 행렬의 거듭제곱, 클래스 사용 행렬 작업, 행렬을 빠르게 거듭제곱하는 알고리즘) .

작업 5.5. 다음을 갖는 -번째 피보나치 수를 출력하는 프로그램을 작성하십시오. 로그 복잡도.

프로그램 텍스트

public class FibIv3 ( public static void main(String args) throws Exception ( int n = Xterm.inputInt("Enter n -> "); Xterm.print("f(" + n + ")"), if (n< 0) { Xterm.println(" не определено"); } else if (n < 2) { Xterm.println(" = " + n); } else { Matrix b = new Matrix(1, 0, 0, 1); Matrix c = new Matrix(1, 1, 1, 0); while (n>0) ( if ((n&1) == 0) ( n >>>= 1; c.square(); ) else ( n -= 1; b.mul(c); ) ) Xterm.println(" = " +b.fib()); ) ) ) 클래스 Matrix ( private long a, b, c, d; public Matrix(long a, long b, long c, long d) ( this.a = a; this.b = b; this.c = c; this.d = d; ) 공개 무효 mul(행렬 m) ( long a1 = a*m.a+b*m.c; long b1 = a*m.b+b*m.d; long c1 = c*m.a+ d *m.c, long d1 = c*m.b+d*m.d, a = a1, b = b1, c = c1, d = d1, ) public void square() ( mul(this); ) public long fib( ) ( 리턴 b; ) )

이 프로그램과 이전 프로그램을 사용하여 천만 번째 피보나치 수를 계산하려고 하면 계산 시간의 차이가 확연할 것입니다. 불행히도 long 유형의 제한된 수로 인해 결과가 부정확합니다(두 경우 모두).

결론적으로, 복잡도가 다른 알고리즘의 실행시간을 비교표로 제시하고, 컴퓨터 속도가 증가함에 따라 빠른 알고리즘 사용의 중요성이 크게 증가하는 이유를 설명한다.

복잡성이 있는 동일한 문제를 해결하기 위한 4가지 알고리즘을 각각 고려하십시오. 이 알고리즘 중 두 번째 알고리즘이 매개변수 값을 사용하여 일부 컴퓨터에서 실행되는 데 정확히 1분이 필요하다고 가정합니다. 그런 다음 매개 변수 값이 다른 동일한 컴퓨터에서 이 네 가지 알고리즘 모두의 실행 시간은 10,300,000년과 거의 같습니다.

초보 프로그래머가 프로그램을 테스트할 때 의존하는 매개변수의 값은 일반적으로 작습니다. 따라서 프로그램을 작성할 때 비효율적인 알고리즘을 적용하더라도 눈에 띄지 않을 수 있습니다. 그러나 이러한 프로그램을 실제 상황에 적용하려고 하면 실제적인 부적합이 즉시 드러날 것입니다.

컴퓨터 속도가 증가함에 따라 하나 또는 다른 알고리즘의 작업이 허용되는 시간 내에 완료되는 매개 변수의 값도 증가합니다. 따라서 값의 평균값이 증가하고 결과적으로 빠른 알고리즘과 느린 알고리즘의 실행 시간 비율 값이 증가합니다. 컴퓨터가 빠를수록 나쁜 알고리즘을 사용할 때 상대적 손실이 커집니다.!

알고리즘을 비교하기 위해 효율성이라는 일반화된 특성을 사용하는 것이 일반적입니다. 알고리즘 L은, 더 효율적인연산 2,알고리즘 L이 더 짧은 시간에 실행되고 (또는) 더 적은 컴퓨터 리소스(RAM, 디스크 공간, 네트워크 트래픽 등)가 필요한 경우.

효율적인 알고리즘은 섹션 1.1에서 이미 언급한 것처럼 허용 가능한 실행 시간과 합리적인 리소스 소비의 요구 사항을 충족해야 합니다. 이러한 특성의 조합이 알고리즘의 복잡성 개념입니다. 알고리즘 및(또는) 관련된 리소스의 실행 시간이 증가하면 복잡성이 증가합니다. 따라서 효율성과 복잡성의 개념은 서로 반대입니다.

구현에 소요된 시간을 반영하는 알고리즘의 특성을 시간 복잡도.구현의 컴퓨터 리소스 비용을 반영하는 알고리즘의 특성을 용량 복잡성.

복잡성 결정과 관련된 알고리즘의 양적 및 질적 평가에서는 실용적이고 이론적 인 두 가지 접근 방식이 사용됩니다.

실용적인 접근특정 물리적 장치에서 실제로 실행 중인 알고리즘과 관련이 있습니다. 측정하고 고정할 수 있는 매개변수가 특징입니다. 이 접근 방식의 시간 복잡도는 시간 단위(예: 밀리초) 또는 알고리즘을 실행하는 데 필요한 프로세서 주기 수로 표현될 수 있습니다. 용량 복잡도는 비트(또는 기타 정보 단위), 알고리즘을 실행하는 데 필요한 최소 하드웨어 요구 사항 등으로 표현할 수 있습니다.

실용 점수는 알고리즘 성능의 절대적인 척도가 아닙니다. 이 접근 방식으로 얻은 정량적 값은 다음과 같은 많은 요인에 따라 달라집니다.

• 컴퓨팅 시스템을 구성하는 구성 요소의 기술적 특성. 따라서 프로세서의 클록 주파수가 높을수록 단위 시간당 더 많은 기본 작업을 수행할 수 있습니다.
• 소프트웨어 환경의 특성(실행 중인 프로세스의 수, 작업 스케줄러의 알고리즘, 운영 체제의 기능 등);
• 알고리즘 구현을 위해 선택한 프로그래밍 언어. 고급 언어로 작성된 프로그램은 하드웨어 리소스에 직접 액세스할 수 있는 저급 언어로 작성된 프로그램보다 실행 속도가 느리고 더 많은 리소스가 필요할 수 있습니다.
• 알고리즘을 구현한 프로그래머의 경험. 대부분의 경우 초보 프로그래머는 숙련된 프로그래머보다 덜 효율적인 프로그램을 작성할 것입니다.

따라서 동일한 입력 데이터에 대해 동일한 컴퓨터 시스템에서 실행되는 알고리즘은 다른 시간에 다른 점수를 가질 수 있습니다. 따라서 복잡성의 정의에 대한 이론적 접근이 더 중요합니다.

이론적 복잡성특정 하드웨어, 소프트웨어 및 구현 도구를 참조하지 않고 알고리즘을 특성화합니다. 이 경우 시간 복잡도는 연산 횟수, 튜링 기계의 주기 등으로 표현됩니다. 용량성 복잡도는 데이터의 양(입력, 중간, 출력), Tyoring 기계의 테이프에 있는 관련 셀 수 등에 의해 결정됩니다.

효율성 평가에 대한 이론적 접근에서는 알고리즘이 일부에서 실행되는 것으로 간주됩니다. 이상적인 컴퓨터, 각 작업 유형의 실행 시간이 알려져 있고 일정합니다. 또한 그러한 컴퓨터의 자원은 무한하므로 용량성 복잡성은 일반적으로 이론적인 접근 방식에서 결정되지 않습니다. 복잡성의 시간 특성으로 이상적인 컴퓨터에서 수행되는 명령(작업)의 수를 선택합니다.

이론적 접근에서 얻은 정량적 추정치는 다음과 같은 여러 요인에 따라 달라질 수도 있습니다.

• 입력 데이터의 양. 크기가 클수록 알고리즘을 실행하는 데 더 많은 시간이 걸립니다.
• 문제를 해결하기 위해 선택한 방법. 예를 들어, 많은 양의 입력 데이터에 대해 퀵 정렬 알고리즘은 동일한 결과를 가져오지만 버블 정렬 알고리즘보다 더 효율적입니다.

알고리즘의 실행 시간은 일반적으로 해결되는 문제의 차원으로 이해되는 입력 데이터의 양(입력 크기)에 따라 다릅니다. 따라서 값 집합을 정렬할 때 데이터의 양은 이 집합의 요소 수입니다. 문자열을 처리할 때 입력 데이터의 크기는 문자열의 길이입니다.

허락하다 피 -일부 알고리즘에 대한 입력 데이터의 양. 로 나타내다 티(p)알고리즘을 실행하는 동안 이상적인 컴퓨터에서 실행되는 명령의 수로, 연산량이 최대일 때 "최악의 경우"로 결정됩니다.

"최악의 경우"의 개념은 예를 들어 설명할 수 있습니다. 어떤 숫자 집합(배열)에 숫자 요소가 있는지 확인하는 알고리즘을 고려합니다. 이 집합을 오름차순으로 정렬하면 일반적으로 원하는 것보다 큰 첫 번째 요소 뒤에 있는 요소를 확인하는 것이 의미가 없습니다. 이 경우 티(p)명사. 그러나 최악의 경우(임의의 정렬되지 않은 집합의 경우) 집합의 모든 요소를 ​​살펴봐야 합니다. 분명히 여기 T(n) = n.

일반적으로 말하면, 티(p)입력 데이터 크기의 일부 함수입니다. 피.많은 경우에 티(p)다항식, 거듭제곱 또는 로그 함수로 표현 피.

가치 행동 티(p)배율에 따라 피~라고 불리는 점근적 복잡성연산. 그들은 말한다 T(n) 있다 복잡도 차수 0(J(n))(읽다 "영형큰 출발/출발 피")일부 알고리즘의 경우 상수가 있는 경우 와 함께및 데이터 볼륨 슈그런 엔 > n 0그리고 불평등이 있다 T(n) s/(n).

이 사실은 다음과 같이 기록됩니다. T(n) = 0(J(n))기능에 대한 의미 티(p)그런 기능이 있다 f(n)그리고 일정한 с, 어떤 것에서 시작하여 n 0 ,의미 티(p)초과하지 않는다 참조(명).

기능 f(n)함수 값의 상한을 나타냅니다. 티(n).예를 들어, T(n) = 2피에이 + n 2 .가치를 선택함으로써 n 0= 0 및 c = 5, 모든 n > n 0우리는 T(n) = 2피에이 + 2쪽 T(n)의 차수는 i 4 입니다.

기능 T(n)는 특정 알고리즘과 관련이 있으므로 종종 복잡성의 순서라고합니다. 0(/(n))알고리즘이 있습니다.

그들은 말한다 티(p)그것은 가지고있다 하한 Q(g(n))("오메가 빅 오프 g from /r") 상수 c와 데이터 양이 있는 경우 n 0그런 /피그리고 불평등이 있다 T(n) > cg(n).

이 사실은 다음과 같이 기록됩니다. T(n) = Q(g(n)).예를 들어, T(n) =두 번째 4+ n 2 .값 선택 c = 1, 모든 피우리는 티(p)= 두 번째 4 + n 2 > cn A >따라서, T(n) 는 하한 i 4 를 가집니다.

어떤 함수에 대해 차수와 하한이 고유하지 않음을 쉽게 알 수 있습니다. 티(n).위의 예에서 /(i)를 i 5 , i 6 ,... 및 다음과 같이 선택할 수 있습니다. g(n) - i 3 , i 2 ,.... 일반적으로 최소 차수를 갖는 함수는 /(i)로 선택되며, 지(n)- 최대로.

복잡도 0(/(i)) 및 하한 Q(g(rc))의 순서는 함수 클래스입니다. 직관적으로 Q(g"(n))은 최소한 다음과 같이 빠르게 성장하는 함수 클래스로 이해될 수 있습니다. 티(n).마찬가지로 직관적으로 0(에프(n))다음보다 빠르게 성장하지 않는 함수 클래스로 이해될 수 있습니다. 티(n). 에서실용적인 관점에서 알고리즘의 복잡성을 추정할 때 가장 중요한 것은 바로 함수의 클래스입니다. 0(f(n)).함수의 유형 결정 /(i) 및 계산의 주요 임무알고리즘의 이론적 복잡성.

모든 알고리즘에 대해 성장 정도를 결정할 때 0(/(n))의 다음 속성을 사용할 수 있습니다.

1) 0(kf(ji))= 0(/(i)), 여기서 케이= 상수 따라서 함수의 상수 인자는 성장률에 영향을 미치지 않습니다. 예를 들어,

2) 0(J(ri)"g(n)) = 0(J(n))"0(g(ri)).따라서 두 함수의 곱의 차수는 복잡도의 곱과 같습니다. 예를 들어,

때때로 이 속성은 다음과 같이 작성됩니다.

3) 0(/(p) + 지(n))같음 우성(최대 차수의 함수) f(n) 및 지(n).예를 들어,

알고리즘의 복잡성 이론에서 다음과 같은 복잡성 함수 클래스가 구별됩니다.

• 1) 일정한 복잡성 0(1). 알고리즘의 실행 시간과 사용되는 리소스는 입력 데이터의 양에 의존하지 않습니다. 일반적으로 순환 및 재귀 호출을 포함하지 않는 알고리즘에는 이러한 복잡성이 있습니다.
• 2) 선형 복잡도 0(n).일반적으로 이러한 복잡성의 문제는 입력 데이터의 각 요소가 다른 요소의 처리 횟수와 어떤 식으로든 관련되지 않은 특정 횟수만큼 처리되어야 하는 문제입니다.
• 3) 대수 복잡도 0(log 2 w), 0(nog 2n).로그의 다른 밑이 때때로 사용됩니다.
• 4) 다항식 복잡도 0(i 2), 0(i 3), 0(i 4),...;
• 5) 기하급수적 복잡성 2p, 3",....

입력 크기가 증가함에 따라 각 후속 함수 유형의 복잡성은 이전 함수 유형보다 빠르게 증가합니다(0(log 2 /?) 제외). 충분히 많은 양의 입력 데이터의 경우 덜 복잡한 알고리즘을 사용하는 것이 좋습니다.

복잡성을 정량적으로 계산할 때 작업 또는 작업 그룹이 처음에 선택되며 이는 이 알고리즘에 중요합니다(기본 구성). 일반적으로 비교 및 ​​산술 연산입니다. 비교 작업에는 두 수량(보다 작음, 보다 큼, 같음, 작거나 같음, 크거나 같음, 같지 않음)의 값 확인이 포함됩니다. 실행 시간 면에서 동등한 것으로 간주됩니다. 산술 연산은 차례로 다음과 같이 나뉩니다. 첨가물그리고 곱셈.첫 번째(종종 단순히 덧셈)카운터 값 추가, 빼기, 감소 또는 감소가 포함됩니다. 두 번째로(간단히 곱셈)곱셈, 나눗셈을 포함하고 나머지는 모듈로 취합니다.

덧셈은 곱셈보다 빠르므로 곱셈의 감소량에 비례하여 덧셈의 수가 증가하더라도 곱셈이 적은 알고리즘이 선호됩니다.

정수 곱셈 또는 2의 거듭제곱으로 나누는 연산은 메모리 셀로 작업할 때 덧셈 연산과 동일한 시프트로 축소되기 때문에 가산 연산으로 분류됩니다.

중요한 거래를 선택한 후 두 가지 범주로 나뉩니다.

• 1) 알고리즘의 복잡성에 직접적인 영향을 미치는 작업
• 2) 알고리즘을 실행할 때 "오버헤드 비용"을 구성하는 작업(예: 중간 데이터를 저장하기 위한 메모리 할당).

수행된 작업 수를 직접 계산하거나 추정하면 다음을 평가할 수 있습니다. 티(n).

복잡성의 순서를 추정하기 위해 알고리즘을 구현하는 프로그램 코드의 분석을 사용할 수 있습니다. 여기서:

• 루프와 재귀 호출이 없는 알고리즘은 0(1) 정도의 복잡성을 갖습니다. 따라서 할당 작업, 데이터 입력 및 출력, 조건부 구성은 항상 복잡합니다.
• 프로그램 코드의 두 부분에 복잡성이 있는 경우 0(J((리))그리고 0(J2(n)),순차 실행은 복잡함

• 루프의 본문이 입력 데이터의 각 요소에 대해 한 번 실행되는 경우 루프 실행의 복잡성은 다음과 같습니다. 0(p)0( 1) = 0(n);
• 중첩 루프를 실행하는 복잡성의 순서는 제품 규칙에 의해 계산됩니다. 0(J×(n)f2(n)) = 0(/,(/?))- 0(J2(리)).각각의 주문 복잡도가 있는 경우 0(n),중첩 루프의 실행에는 순서 복잡성이 있습니다. 0(n 2).

실시예 1.3

언어에서 프로그램 알고리즘의 복잡성 순서 결정

Listing 1.2에 표시된 Pascal. 프로그램 라인은 주석으로 번호가 매겨집니다(단락 2.6 참조).

목록 1.2

(01) for i:=l to n do

(02) 시작하다

(03) write("배열 요소를 입력하세요.

인덱스 ",i,": ");

(04) Readln(MyArray[i]);

(05) 끝;

(06) for i:=l to n do

(07) j:=1부터 n까지

(08) 시작하다

(09) write("배열 요소를 입력하세요.

인덱스 ", i, ",", j, " : ");

(10) Readln(MyDArray);

(11) 끝;

해결책

라인 02, 05, 08, 11에는 실행 가능한 문이 포함되어 있지 않으므로 순서를 결정할 때 고려되지 않습니다.

라인 03과 04의 순서는 0(1)입니다. 이들의 순차 실행은 0(1) + 0(1) = 0(1) 순서입니다. 유사하게, 라인 09와 10의 순차 실행은 복잡도 0(1)을 갖습니다.

라인 01-05의 루프에는 순서 복잡성이 있습니다. 에), 06-11행의 중첩 루프 - 순서 0(n 2).알고리즘의 최종 복잡성은 다음과 같습니다.

시간과 리소스 모두에서 알고리즘의 복잡성을 추정하면 알고리즘의 최대 및 평균 실행 시간을 결정할 수 있습니다. 이것은 특히 아래에서 설명하는 정렬 및 검색 작업에서 많은 양의 정보를 처리할 때 매우 중요합니다.